Category: Algorithm

0

기초 DP알고리즘 문제

배낭 알고리즘(a.k.a Knapsack problem)배낭 알고리즘은 쪼갤 수 없는 물건이 제한된 가방에 최대한의 가치로 담는 문제이다. Fractional Knapsack 문제는 탐욕 알고리즘으로 풀 수 있었지만, 조건에서 쪼갤 수 있어서 가능했다. 앞서 쪼갤 수 없는 물건을 최대한의 가치를 가지며 담기 위해서는 DP를 통해서 해결하게 된다. 알고리즘

0

Merge sort algorithm

합병 정렬(merge sort)합병 정렬은 분할정복 알고리즘이며 길이가 N인 리스트를 길이가 1인 리스트로 쪼개고 다시 쪼개진 각각의 리스트를 정렬하며 합병해 최종적으로 정렬된 리스트를 가지게 된다. 함수의 구조를 보면 알겠지만, 중앙 위치를 찾고 중앙 위치를 기준으로 좌측, 우측을 나눠 재귀 호출된다. 재귀 종료 조건은 start < end의 조건에

0

Quick sort algorithm

퀵 정렬 알고리즘퀵 정렬은 피벗을 기준으로 좌/우에 자신보다 큰/작은 값을 몰고, 문제를 조금씩 나눠가며 정렬을 하게 된다. 최악의 경우(항상 피벗이 모든 값 중 가장 작은 경우) O(n^2)를 가지는 상황이 나올 수 있지만, 확률적으로 그럴 일은 적기에 평균적으로 O(NlogN)의 시간복잡도를 가진다. 구현123456789101112131415161718

0

Dijkstra Algorithm

다익스트라 알고리즘Dijkstra algorithm(이하 다익스트라 알고리즘)은 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 가장 짧은 거리를 구하는 알고리즘 중 하나이다. 선형구조로 구현된 다익스트라 알고리즘은 O(N^2)의 시간복잡도를 가지지만 힙을 이용해 구현하게 되면 O(NlogN)의 시간복잡도를 가지게 된다. 최단 거리를 구하는