최단 경로 (다익스트라) 최단 경로를 찾는 문제는, 한 정점으로부터 다른 모든 정점으로 가는데 걸리는 최단 경로를 통해 결국은 원하는 지점으로 최단경로를 찾는 방법이다. 다익스트라는 여기서 첫 점을 기준으로 정점들을 추가하며 거리를 갱신시킨다. D(z)를 x에서 z까지의 최단 경로라 한다면 $D(z) = Min(D(z) , D(y) + c(y,z))$ 의 식을 계속 진행하여 전체 경로에 대한 최단 경로를 알아낸다. //최단 경로 수도 코드 //입력 : 가중치 그래프 G //출력 : distance 배열, distance[u]는 v에서 u까지의 최단 거리 shortest_path(G,v) S = v; for(G의 각 정점 w) do distance[w] = weight[v][w]; while 모든 정점이 ..

합병 정렬 폰 노이만에 의해 만들어진 정렬 방법이다. 분할 정복(Divide and Conquer)를 이용한 정렬 방법으로, 문제를 작은 문제로 나누고 각각을 해결한 다음, 그 결과로 큰 문제를 해결하는 방법이다. 합병 정렬(Merge Sort)은 3가지 과정으로 구성된다. 분할(Divide) = 배열을 같은 크기의 배열 두개로 분할한다 정복(Conquer) = 이 두 개의 배열을 정렬한다. (크기가 아직 크면 순환 호출로 다시 분할) 결합(Combine) = 배열들을 다시 합치면서 원래의 정렬된 배열로 만든다. 코드 //머지소트 c++ 코드 void MergeSort(int sort[], int data[], int first, int last) { int mid; //1개 남았을때는 멈추게 if (f..

삽입 정렬 모든 요소를 앞에서부터 차례대로 정렬된 부분과 비교하여 위치를 찾아 삽입하는 방법. void InsertionSort(int[] data){//삽입정렬 for (int i = 1; i = 0; j--) { //앞에 정렬되어 있는 부분에서 해당하는 위치를 찾아 삽입 if (data[j] > key) { data[j + 1] = data[j]; //한칸 옆으로 이동 } else { break; } } data[j + 1] = key; } } 시간복잡도 BestCase : 이미 정렬된 경우 -> 이동 없이 각각 1번의 비교씩 $O(N)$ WorstCase : 입력 자료가 역순인 경우 등 (마지막이 4 3..

문제 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1초 256 MB 2373 545 412 21.950% 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈를 반드시 하고 싶은 용사는 T시간 내에 반드시 공주님이 있는 곳으로 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 ..