홍카나의 공부방

최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 일반적으로 그래프에서 지점을 노드(Node)로 표현하고, 노드간 연결된 선은 간선(Edge)으로 표현한다. 대표적인 최단 경로 알고리즘으로 다익스트라 알고리즘이 존재한다. 다익스트라 최단 경로 알고리즘 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 알고리즘은 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. (그래서 그리디 알고리즘으로 분류하기도 한다.) 알고리즘의 동작 과정은 다음과 같다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 ..

이진 탐색(Binary Search)은 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법이다. 언어에 상관없이 이진 탐색은 시작점, 중간점, 끝점을 이용하여 데이터를 탐색한다. 리스트에 데이터가 다음과 같이 정렬된 상태로 있다고 가정하자. 0 3 6 9 12 15 18 21 24 27 30 시작점인 list[0]의 값은 0일꺼고, 끝점인 list[-1]의 값은 30일 것이다. 그리고 중간 지점은 (시작점 + 끝점 // 2)로 계산하면 5로, list[5]인 15이 될 것이다. ( 소수점은 없앤다. ) 그리고 찾고자 하는 값이 9라고 가정하자. 먼저 중간 지점인 list[5]의 값인 15과 비교한다. 찾는 값인 9는 중간 지점의 값인 15보다 작다. 그러면 중간점인 list[5]부터 ..

그리디 알고리즘(Greedy Algorithm)은 '탐욕(Greedy)'이라는 이름에 알맞게 지금 당장 가질 수 있는 최고의 이익을 따라가는 알고리즘을 의미한다. 모든 경우 최적해를 보장하지는 못하지만, 드물게 최적해를 결과로 내는 경우도 있다. 합리적인 시간 내로 최적에 가까운 해답을 찾을 수 있다는 점에서 유용한 알고리즘이다. 그리디 알고리즘이 잘 작동하는 문제들은 이전의 선택이 이후의 선택에 영향을 주지 않는 문제들이 많다. 물론 꼭 그렇지 않더라도 괜찮은 정답을 찾을 수 있는 알고리즘이다. 다이나믹 프로그래밍(DP)과는 최적 부분 구조 문제를 푼다는 점에서 약간 다른데, DP가 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 찾는 것이라면 그리디는 각 단계마다 지역 ..