다익스트라 알고리즘은 최단 경로를 구하는 데 사용되는 그리디 알고리즘으로 처음 출발 노드부터 각 노드까지의 최단 거리를 무한 초기화되며, 출발 노드 거리를 0으로 설정합니다. 그 후 출발 노드로부터 인접 노드에 대한 최단 거리를 계산하여 더 짧은 경로로 거쳐가는 노드로 값을 경신합니다. 이 과정을 모든 노드에 반복함으로써 최단거리를 구합니다. 그래프 방향의 유무는 상관없으나, 간선들 중 단 하나라도 가중치가 음수가 있으면 이 알고리즘을 사용할 수 없다. 다익스트라 알고리즘 주요 특징 하나의 출발 노드에서 다른 모든 노드로부터의 최단 경로를 구합니다. 음의 가중치를 가진 간선이 없는 경우에만 정상 작동합니다. 그리디 알고리즘으로 항상 최단 거리를 보장하지만, 음의 가중치가 있는 경우 정확한 결과를 보장하지..
재귀함수란 자기 자신을 호출하는 특성을 가진 함수를 말합니다. 즉 함수 내에서 자신을 반복하여 호출하여 문제 해결 방식을 말합니다. 재귀함수는 수학적 귀납법과 유사 구조를 가지고 있으며, 문제를 작은 부분 나누면서 간단한 경우를 해결하고 다시 큰 문제로 확장하는 방식으로 작동됩니다. 재귀함수에 사용되는 경우 문제를 작은 부분 문제로 분할하여 해결해야 하는 경우 (분할 정복 알고리즘) 데이터 구조를 탐색 및 순회해야 하는 경우( 트리, 그래프 등) 점화식으로 표현된 수학적 문제 해결이 필요한 경우 모든 가능한 경우의 조함을 생성해야 하는 경우(순열, 조합 등) 재귀함수 작성 시, 반드시 종료조건이 명확하게 있어야 합니다. 종료 조건이 없는 재귀함수는 무한히 자기 자신을 반복 호출하게 되어 무한 루프에 빠지..
완전 탐색 알고리즘이란 컴퓨터 과학 문제 해결 방법으로, 모든 경우의 수를 탐색하여 해를 찾는 알고리즘으로 이 방법은 문제가 작은 경우 유용할 수 있지만, 문제의 크기가 커질수록 실행 시간이 증가됨으로, 큰 규모의 문제에서는 비효율적인 알고리즘입니다. 이처럼 완전 탐색 알고리즘에 대한 특징 및 코드 예시를 통해 완전탐색 알고리즘이 무엇인지 알아보도록 합시다. 완전탐색 알고리즘 특징 가능한 모든 경우의 수 확인: 문제의 가능한 모든 해를 확인함으로써 최적의 해를 찾습니다. 무조건적인 방법: 제약이나 특정조건에 고려하지 않고 모든 경우를 따집니다. 정확성 : 가능한 모든 경우를 탐색하기에 최적의 해를 찾게 됩니다. 시간 복잡도 : 문제의 크기에 따라 기하급수적으로 증가할 수 있어 큰 규모의 문제에서는 사용하..
그리디 알고리즘은 다른 말로는 탐욕알고리즘이라고도 합니다. 그리디 알고리즘이란 최적해를 구하는 데 사용하여 최적해의 근삿값을 구하는 데 사용되는 방법입니다. 여러 경우 중 하나를 선택할 때마다 최적이라고 생각되는 것을 선택하여 최종적인 해답을 찾아 됩니다. 하지만 순간마다 하는 선택은 그 순간에는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서 그것이 최적이라고 보장할 수는 없습니다. 하지만 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들입니다. 그리디 알고리즘이 잘 적용된 문제는 대부분 탐욕적인 선택 조건과 최적 부분 구조 조건 두 가지를 모두 만족하게 됩니다. 탐욕스러운 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 점입..
합병 정렬 또는 병합 정렬은 일반적인 방법으로 구현했을 시 안정 정렬에 속하는 분할 정복 알고리즘의 하나입니다. 평균 시간복잡도는 일반적으로 O(n log n)이며, 최악의 시간복잡도 역시 O(n log n) 시간 복작도가 걸립니다. 병합 정렬의 공간 복잡도는 O(n)이 걸립니다. 병합 정렬 알고리즘 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할합니다. 부분리스트가 하나만 남았을 때까지 반복해서 병합하여 정렬된 부분 리스트를 생성합니다. 마지막에 남은 부분 리스트가 정렬된 리스트입니다. 흔히 사용하는 하향식 2-way 병합 정렬 방법 리스트의 길이가 1 이하면 이미 정렬된 것이라고 봅니다 분할(divide): 정렬되지 않은 리스트를 절반으로 자른 후 비슷한 크기의 두 부분 ..
