Growth Diary

1. 백준 1916번 문제2. 다익스트라 알고리즘(Dijkstra’s Algorithm)1. 백준 1916번 문제 오늘도 알고리즘 공부를 위해 백준 문제에 도전했는데, 1916번 문제인 "최소비용 구하기"에 도전했습니다. 처음에는 간단하게 DFS를 이용하려 했지만, 최대 도시의 수가 100,000개로 주어지고 시간 제한이 0.5초라는 점을 고려하니 다른 접근 방식이 필요하다고 느꼈습니다. 문제에서 어떤 간선에는 큰 값이 들어갈 수도 있고 작은 값이 들어갈 수도 있다는 점을 고려하면, 결국에는 모든 경우를 탐색해야 한다고 생각했습니다. 그러나 시간 제한이 짧기 때문에 조건을 걸어주어 조기에 탐색을 종료할 수 있도록 백트래킹을 이용하여 코드를 작성했습니다. import syssys.setrecursionli..

1. 이진 탐색 개념 2. 이진 탐색 동작과정 3. 백준 10815번 4. 번외 (list vs set) 1. 이진 탐색 개념 이진 탐색은 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 내가 찾고자 하는 값이 선택될 때까지 탐색하는 알고리즘입니다. 또한, 이진 탐색 알고리즘은 입력 데이터가 많거나(1000만 단위 이상) 탐색 범위의 크기가 매우 넓을 때 효과적으로 문제를 해결 할 수 있습니다. (반드시 정렬이 되어 있어야합니다.) 2. 이진 탐색 동작 과정 다음과 같이 오름차순으로 정렬 되어있는 배열이 있다고 가정해 보겠습니다. 이진 탐색은 배열을 반복해서 반으로 나누기 때문에 초기값, 끝값, 중간값이 필요합니다. 이 값들을 그림에 표시해보면 이런식으로 나타낼 수 있습니다. 배열의 초기 인덱스와 마..

백준 2751번 문제를 풀다가 시간초과가 나와서, 알고보니 여러 정렬 방법 중 시간 복잡도가 O(nlogn)인 방법을 사용해야 풀 수 있다는 것을 뒤늦게 알게 되었습니다. 그래서 그 중 하나인 병합 정렬에 대해 설명하려 합니다. 먼저 2751번의 문제는 다음과 같습니다. 문제 자체는 상당히 간단합니다. 문제 하단에 제시된 힌트도 있었습니다. 파이썬을 사용하시는 분들은 이 문제를 라이브러리를 사용해서 아주 간단하게 풀 수 있습니다. N = int(input()) arr=[] for i in range(N): x=int(input()) arr.append(x) arr.sort() for i in arr: print(i) 이런식으로 손 쉽게 문제를 해결할 수 있습니다. 하지만 저는 내장된 정렬 함수가 아니라 ..