병합 정렬의 개념 병합 정렬이란? 하나의 리스트를 두 개의 균등한 크기로 최대한 분할하고 분할된 부분 리스트를 순서대로 합하는 방식이다. 분할된 리스트를 순서대로 합쳐서 담기 위한 자료구조가 추가적으로 필요하다. 가장 작은 단위로 절반씩 쪼갠 후 가장 작은 단위부터 다시 합쳐나가는데 이 합쳐나가는 과정에서 데이터가 정렬이 된다. Divide and Conquer Merge Sort의 해결 전략 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 Divide and Conquer 방식은 대개 재귀 호출을 이용하여 구현함 동작 방식과 구현 1. 데이터들을 절반으로 나눈다. (분할) 2. 데이터를 가장 작은 단위로 분해한 후 맨 밑에서 부터 차례대로 합병을 진행..

다익스트라 알고리즘의 개념 다익스트라 알고리즘이란? 하나의 정점에서 모든 정점으로의 최단 경로를 계산하는 것을 목표로 하는 알고리즘 Single source shortest paths problem 로직 모든 정점들은 처음에 무한대 값을 갖는다. 정점 A에서 정점 B가 이어지면 정점 A까지의 최단거리 + A에서 B까지의 거리를 계산한다. 만약 B가 가지고 있는 값(즉, A에서 B로 이어지는 다른 경로에 의한 값)과 2번에서 계산한 값과 비교하여 후자가 더 작다면 갱신한다. 가장 작은 값을 가지고 있는 정점부터 이어서 반복한다. (가장 작은 값을 가지고 있는 정점부터 시작하는 이유는 작지 않은 값부터 시작되면 쓸모없는 연산이 진행되기 때문이며, 올바른 결과를 얻어낼 수 없다.) 작은 값으로 갱신이 되어야 ..

선택 정렬의 개념 선택 정렬이란? 넣을 위치는 이미 정해져 있고, 그 위치에 어떠한 데이터를 넣을지 선택하는 알고리즘이다. 동작 방식 1. 리스트 길이(n)의 -1 만큼 반복한다. (앞에서부터 위치를 정하게 되면 마지막 값은 자동으로 위치가 정해진다) 1-2. 선택된 최솟값과 최솟값이 들어갈 위치의 값과 교체한다. 1-1. 값이 들어갈 위치부터 마지막 값까지 최솟값을 찾는다. void sort() { int min; // 1. 값이 들어갈 위치를 선택하는 반복문 for(int i=0; i

외판원 문제란? 가장 유명한 최적화 문제 중 하나로 Traveling Sales-man Problem (TSP)라고 불리는 문제이다. 어떤 나라에 n(2

삽입 정렬의 개념 삽입 정렬이란? 선택 정렬과 다르게 데이터의 삽입할 위치를 찾는 정렬이다. 현재 Key 앞에 위치하는 데이터들은 이미 정렬된 데이터들이며, 정렬이 완료된 데이터들 사이에 Key의 위치를 찾는 것이 삽입정렬이다. 이미 정렬된 데이터일 경우 모든 데이터가 비교를 단 한번만 수행하기 때문에 최선의 경우 O(N)의 성능을 보여준다. 동작 방식 리스트 길이(n)의 -1 만큼 반복한다. (맨 앞의 데이터는 제외한다.) 1-2. 해당 위치에 선택된 데이터를 삽입한다. 1-1. 현재 선택된 데이터와 앞에 위치한 정렬된 값들을 비교하며 삽입할 위치를 찾는다. void sort(int[] numbers) { // 1. for(int i=1; i=0 && numbers[j] > temp; j--) { nu..