이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준 11404번문제 난이도: 골드 4혼자의 힘으로 풀었는가?: X문제를 처음 봤을 때는 그래프 탐색 문제라고 생각했다.그래서 단순히 bfs를 사용해서 문제를 풀어봤다.그러나 한 가지 간과한 것이 있었는데 이 문제의 논점은 각 점으로 가는 최단 경로를 찾는 것이다. bfs는 가중치가 모두 동일한 경우에는 최단 경로를 보장하기 때문에 bfs는 해당 문제에 맞는 알고리즘이 아니다.가중치가 존재하는 그래프 문제는 일반적으로 플로이드-워셜, 다익스트라, 벨만-포드 알고리즘 등을 사용해야 한다.나는 플로이드-워셜, 다익스트라 알고리즘을 각각 사용해서 2번 풀었는데 각각의 시간 복잡도는 아래와 같다.시간 복잡도플로이드-워셜: O(n^3)다익스트라: O((..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기백준 11444번문제 난이도: 골드 2혼자의 힘으로 풀었는가?: X해당 문제를 처음 본 순간 떠오른 풀이 방식은 단순 피보나치 수열을 구현해서 푸는 방식이었다.당연하게도 n 이기 때문에 시간 복잡도에서 막힌다.dp로 풀어야하는지.. 어떻게 풀어야할지 한참을 고민하다가 스스로 정해둔 제한 시간 30분을 넘겼기 때문에 알고리즘 분류를 참고했다.알고리즘 분류를 확인해보니 분할 정복이라고 한다.분할 정복이란?분할 정복이 무엇인지는 이해했는데 이걸 어떻게 피보나치 수열에 적용할지가 고민이었다.이에 대한 GPT의 대답은 아래와 같다.상상도 못했던 풀이 방법이었다. 행렬식을 사용할 생각을 왜 못했을까..선형대수학의 중요성과 생각의 폭의 중요성을 깨달았다.이..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기📌 추상 자료형(Abstract Data Type)이란?기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열하는 것을 추상 자료형이라고 한다.예를 들면, 제품의 사용 설명서와 같다. 선풍기의 사용 설명서를 생각해보자.선풍기의 사용 설명서에는 정지, 실행, 회전, 미풍, 약풍, 강풍 버튼의 기능 설명과 사용 방법이 나와있다.하지만 버튼을 눌렀을 때 선풍기 내부 회로에서 어떤 일이 발생하는지에 대해서는 전혀 나와있지 않다.있어도 안본다.추상 자료형은 선풍기의 사용 설명서와 같다. 그저 기능이 무엇인지, 사용 방법은 무엇인지 정의한 것이 추상 자료형이다.✔︎ 추상 자료형의 필요성추상 자료형은 구현자와 사용자를 분리한다. 라이브러리를 가져다..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기⭐️ 자료 구조란?자료 구조란 데이터 값의 모임이다. 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다.예를 들어 한정된 크기의 책장이 있고, 넣어야 될 책들이 있다고 하자.빈 책장책장에 가장 많은 책을 넣는 방법은 아무런 규칙 없이 책을 모두 꽂아 넣는 것이다. 그렇다면 당장은 이 책장의 공간을 효율적으로 사용하는 것처럼 보일 수 있다.그러나 이후 책을 찾을 때 문제가 발생한다.규칙 없이 책을 꽂아 넣었기 때문에 책을 찾을 때도 규칙 없이 책장의 모든 범위를 찾아야한다.이번에는 '책을 제목의 오름차순'으로 꽂아 넣는다는 규칙을 세워보자.책을 제목의 오름차순으로 꽂..