본문 바로가기

CS38

정렬 #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.
임계 영역의 문제 해결 (1) 임계 영역의 통제, 즉 임계 영역에 대한 문제를 해결하기 위해서는 아래의 세 요구사항들을 충족시켜야 한다. 1. 상호 배제 (Mutual exclusion) 한 프로세스가 임계 영역에서 실행되고 있다면 다른 프로세스들은 임계 영역에 진입할 수 없다는 뜻이다. 다르게 말하면, 두 개 이상의 프로세스가 동시에 임계 영역에 존재해서는 안 된다는 뜻으로 이는 경쟁 상태(Race condition)를 방지하기 위해, 프로세스의 동기화를 위해 반드시 필요한 기본 조건이다. 2. 진행 (Progress) 임계 영역이 비어 있을 때, 임계 영역에 진입하고자 하는 프로세스가 존재한다면 그 진입은 반드시 이루어져야 한다는 뜻이다. 만약 진입이 영원히 이루어지지 않는다면 다른 프로세스에도 영향을 끼쳐 교착 상태(Deadlo.. 2022. 9. 8.
경쟁 상태와 임계 영역(Critical section) 경쟁 상태에 대해서는 이전 게시글에서도 설명했다. 경쟁 상태(Race condition)의 간단한 예시 전역 변수 count = 5에 대하여 각각의 스레드가 count++, count--를 한 번씩 수행하도록 했다. 그렇다면 두 스레드가 모두 Join되었을 때 count는 5를 그대로 유지하고 있을까? ... 만약 그렇다고 생각했다 sete3683.tistory.com 경쟁 상태는 여러 프로세스(혹은 스레드)가 동시에 공유 자원에 접근하기 때문에 발생한다. 그래서 우리는 공유 자원에 대하여 한 번에 하나의 프로세스만이 이에 접근할 수 있도록 통제해야 하는데, 그러한 통제가 필요한 영역을 임계 영역(Critical section)이라고 부른다. 임계 영역은 입장 영역(Entry section)과 퇴장 영역.. 2022. 9. 6.
빠른 거듭제곱 알고리즘 (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.
경쟁 상태(Race condition)의 간단한 예시 전역 변수 count = 5에 대하여 각각의 스레드가 count++, count--를 한 번씩 수행하도록 했다. 그렇다면 두 스레드가 모두 Join되었을 때 count는 5를 그대로 유지하고 있을까? ... 만약 그렇다고 생각했다면 아래의 설명을 읽어보자. count++는 Low level에서 아래와 같이 동작한다. 그래서 count++를 수행하는 도중에도, 드물긴 하지만 Preemptive 스케쥴러에 의해 Context switch가 발생할 수 있고 이는 count의 일관성을 해치는 결과를 낳는다. 아래는 그 과정이다. 스레드 1에서 count++를 수행하던 도중 Context switch가 발생한 경우다. 원래대로라면 스레드 2는 count = 6을 레지스터로 가져와 연산을 진행했어야 하는데, 문제는.. 2022. 8. 25.

티스토리툴바