본문 바로가기

CS/알고리즘7

다익스트라 알고리즘의 증명 알고리즘에 대한 설명은 생략하겠다. 이 글에서는 다익스트라 알고리즘의 증명만, 그것도 최대한 간단하게 설명할 것이다. 증명은 귀류법으로 진행된다. 1. 다익스트라 알고리즘이 정당하다면, 한번 결정된 최단거리가 갱신되는 일은 없어야 한다. 만약 갱신된다면 그것은 '진짜' 최단거리가 아니기 때문이다. 2. 증명을 위해, 다익스트라 알고리즘이 정당하지 않다고 가정하자. 이는 최단거리가 갱신될 수 있다는 뜻이다. 3. 다익스트라 알고리즘에 의하면, 한 노드의 최단거리가 결정되는 시점은 해당 노드를 방문할 때가 된다. 따라서 최단거리의 갱신은 그 이후에, 즉 아직 방문하지 않은 노드에 의해서만 이루어질 수 있다. 4. 그러나 이는 불가능하다. 다익스트라 알고리즘은 매 반복마다 가장 가까운 노드를 방문하는데, 어떻.. 2022. 10. 14.
정렬 #3) 삽입 정렬 삽입 정렬은 말그대로 이미 정렬되어 있는 배열에 새로운 원소를 삽입하는 것이다. 아래는 오름차순 정렬에 대한 예시이다. 삽입하고자 하는 값을 key라고 하자. key를 배열의 2번째 원소부터 시작하여 3번째, 4번째... 로 설정하게 되면, key보다 왼쪽에 있는 원소들은 이미 정렬이 되어 있는 상태가 된다. 따라서 우리는 key가 삽입될 위치를 찾기만 하면 된다. 찾는 방법은 간단하다. 왼쪽으로 계속 이동하다가 key 값보다 작거나 같은 값이 나올 때 멈추면 된다. 물론 이동이라고 해서 swap으로 구현하면 안 된다. key 값은 따로 저장해두고, 배열을 한 칸씩 shift시키다가 자리를 찾으면 그 때 swap하는 편이 낫다. 시간 복잡도는 버블 정렬, 선택 정렬과 동일한 O(n^2)이지만 최선의 경우.. 2022. 10. 4.
정렬 #2) 선택 정렬 선택 정렬은 말그대로 배열에서 최솟값을 선택해 이를 앞으로 이동시키는 행위를 반복하는 것이다. (내림차순을 원하면 다르게 구현해도 된다. 최댓값을 선택해도 되고, 앞이 아닌 뒤로 이동시켜도 된다.) 위 그림처럼 최솟값을 선택하고, 이를 i번째 위치로 이동시키는 작업을 반복한다. 굉장히 단순하지만 그만큼 시간 복잡도도 상당하다. O(n^2)이다. 왜냐하면, 최솟값을 구하기 위한 비교 작업이 각 회차마다 (n - 1), (n - 2), ... 1번씩 이루어지는데 이를 모두 더하면 n * (n - 1) / 2 가 된다. 따라서 O(n^2)이다. int[] num = { 6, 3, 4, 1, 5, 7, 2 }; int minIndex; for (int i = 0; i < num.Length; i++) { min.. 2022. 10. 4.
정렬 #1) 버블 정렬 버블 정렬은 아래의 과정으로 이루어진다. 노란색으로 칠해진 칸은 비교중인 두 수를 의미한다. 수열 4, 3, 2, 1 을 오름차순으로 정렬하는 과정이다. 인접한 두 수를 반복해서 비교하며 가장 큰 수를 뒤로 이동시킨다. 버블 정렬이라는 이름이 붙게 된 이유가, 이러한 과정이 마치 거품이 수면 위로 올라오는 모습과도 같아서라는데 어찌보면 그럴듯하다. 큰 수들이 하나씩 올라오는 모습을 거품이 올라오는 것처럼 생각했을 수도 있겠다. 버블 정렬의 시간 복잡도는 O(n^2)이다. 이유는 위 그림을 통해 알 수 있는데, 길이가 4인 수열에서의 비교는 3 + 2 + 1 = 6번 이루어지는 것을 확인할 수 있다. 만약 길이가 n이라면? 분명 (n - 1) + (n - 2) + ... + 1번 이루어질 것이다. 이는 충.. 2022. 10. 4.
빠른 거듭제곱 알고리즘 (C#) 대부분의 언어에는 이미 거듭제곱 함수가 내장되어 있지만, 가끔씩 내가 직접 만들어야 하는 상황이 생긴다. 예를 들어 Mod 연산이 필요한 문제라든가... 그래도 구현이 어렵진 않기 때문에 한번 외워두면 두고두고 써먹을 수 있다. 거듭제곱의 계산은 (1)반복문 과 (2)재귀 로 구현할 수 있다. 각자 편한 방식을 택하자. (1) 반복문 여기서는 간단하게 느낌만 설명하겠다. 3^13을 예로 들어보자. 지수 13을 이진수로 바꿔서 생각하면, 우리는 3^13을 아래와 같이 표현할 수 있다. 지수법칙에 의해 3개의 항으로 나누어졌다. 반복문에서 행해지는 작업은 위 항들을 구하는 것이다. public static int pow(int a, int b) { int result = 1; while (b > 0) { i.. 2022. 8. 29.
정수의 각 자릿수를 다루는 방법 (C#) 정수 x의 각 자릿수를 순서대로 출력하는 코드는 아래와 같다. public static void Print(int x) { if (x / 10 > 0) Print(x / 10); Console.Write(x % 10); } 만약 거꾸로 1의 자리부터 출력하고 싶다면 재귀가 아닌 반복문으로도 충분하다. public static void PrintReverse(int x) { while (x > 0) { Console.Write(x % 10); x /= 10; } } 거꾸로 된 출력이 아니라 값을 원한다면 아래의 방법을 사용하면 된다. public static int Reverse(int x) { int result = 0; while (x > 0) { result = result * 10 + x % 10;.. 2022. 8. 28.
매개 변수 탐색(parametric search, 파라메트릭 서치) 매개 변수 탐색은 최적화 문제를 결정 문제로 바꾸어 풀 수 있게 해주는 기법이라고 한다. 최적화 문제란 말그대로 어떠한 함수값을 최적화시키는 변수를 찾는 문제, 그리고 결정 문제는 예-아니오의 형태로 답안이 나오는 문제를 말한다. 매개 변수 탐색의 기저는 이분 탐색인데, 이것을 결정 문제로 바꾼다고 해서 mid가 가리키는 값이 정답인지 바로 알 수 있는건 아니다. 다만 그 값이 정답이 될 수 있는지 정도는 바로 알 수 있다. 매개 변수 탐색은 그 결과를 이용해 탐색 범위를 좁혀가며 답을 찾는 기법이다. 마치 스무고개와도 같다. 문제를 통해 이해해보자. 아래 문제는 백준 단계별을 따라갔을 때 처음으로 만날 수 있는 매개 변수 탐색 문제이다. 문제에 대한 설명은 생략하겠다. 하지만 아래 풀이를 이해하기 위해.. 2022. 8. 9.

티스토리툴바