병합 정렬 (Merge Sort)

병합 정렬 (Merge Sort)는 고오급 정렬 알고리즘에 속한다 그 중 분할 정복 알고리즘에 속한다 (그 이유는 정렬을 하는 방법을 보면 쉽게 와닿는다!) 정렬 알고리즘은 다음과 같다 1. 배열의 반을 뚝 하고 자른다 2. 배열의 원소 수가 1개 이하가 될때까지 1을 반복한다 3. 배열의 원소 수가 1개 이하가 되면 정렬된 것으로 간주한다 (하나밖에 없으니까!) 4. 분할되었던 2개의 배열을 합치며 양 배열의 순서에 맞는 값을 집어넣으며 분할되었던 모든 배열을 합친다 5. 정렬 끝! 따라서 병합 정렬은 재귀함수를 통해 구현하게 된다 이를 간단하게 그림으로 표현하자면 이렇게 된다 실제로는 동시에 진행되지 않고, 잘게 쪼개서 부분 하나하나씩 정렬해 갈 것이다 이를 코드로 구현하면 다음과 같다 // 이 함수..

2023.02.10

삽입 정렬 (Insertion Sort)

마지막으로 구현하기 쉽고 이해하기 쉬운 알고리즘중 삽입 정렬(Insertion Sort)이 있다 정렬되지 않은 원소를 순회하며 이미 앞의 정렬된 부분과 비교하고, 자신이 들어갈 공간을 찾아 들어가는 정렬이다 즉 n개의 원소를 정렬할 때 8번째 원소는 이미 정렬된 0 ~ 7번째 원소와 비교해 삽입하는 정렬 알고리즘이다 따라서 첫번째 정렬은 두번째 원소부터 시작하게 된다 이를 코드로 구현하면 다음과 같다 // 이 함수는 인자로 배열의 시작 주소와 배열의 크기를 받도록 한다 void InsertionSort(int* start, int size) { // size가 2보다 작다면 정렬할 필요가 없으므로 return 한다 if (size < 2) return; // 모든 배열을 순회하고, 0번 인덱스는 포함하지..

2023.02.08

특정 수의 모든 약수를 구하기

어떤 숫자 n의 약수를 구할 때 어떤 방법을 사용할 수 있을까? 가장 간단한 방법으로는 1~n까지의 모든 수로 n을 나눠 나머지가 0인지 확인하는 것이다 이렇게 한다면 10000의 모든 약수를 구하기 위해서는 1~10000까지 나눠봐야 하므로 10000번의 연산이 필요할 것이다 하지만 이건 생각하기에 간단한 방법이지 컴퓨터가 실행하기에 간단한 방법은 전혀 아니다 만약 100,000,000의 약수를 모두 구한다면 1억번의 연산이 필요할것이기 때문이다 이런 방법으로 코드를 짠다면 다음과 같이 될 것이다 int main() { vector divisors; // 자릿수를 구분하기 위해 '를 넣었다 // '는 주석과 같이 컴파일러 수준에서 무시된다 int num = 100'000'000; // i가 0이면 nu..

2023.02.08

선택 정렬 (Selection Sort)

버블 정렬과 비슷하게 구현하기 쉽고 이해하기 쉬운 정렬 알고리즘중 선택 정렬 (Selection Sort)가 있다 선택 정렬은 자료에서 현재 위치에 맞는 배열을 찾아, 그 값을 현재 인덱스의 값과 교환한다 만약 오름차순 정렬을 한다면 전체 배열 내 가장 작은 값을 찾아 0번 인덱스에 두고, 다음 루프에서 1번 인덱스를 찾고.. 이렇게 배열 전체를 반복하면 모든 정렬이 끝나게 된다 버블정렬과 마찬가지로 비효율적인 알고리즘이기 때문에 자주 쓰이는 정렬 알고리즘은 아니다 선택 정렬은 현재 인덱스에 맞는 값을 찾기 위해 항상 배열 전체를 순회해야 하므로 정렬 여부와 상관없이 동일한 시간이 걸리게 된다 선택 정렬을 코드로 구현하면 다음과 같다 // 이 함수는 인자로 배열의 시작 주소와 배열의 크기를 받도록 한다 ..

2023.02.08

버블 정렬 (Bubble Sort)

컴퓨터의 정렬 알고리즘에는 굉장히 많은 종류가 있다 그 중 가장 구현하기 쉽고, 이해하기 쉬운 bubble sort 알고리즘에 대해 써본다 bubble sort의 원리는 간단하다 만약 오름차순으로 정렬하고 싶다면, 가장 큰 값이 맨 마지막으로 가야 할 것이다 따라서 붙어있는 두개의 값을 비교해, 만약 왼쪽의 값이 더 크다면 오른쪽과 값을 바꾸어 주는것이다 이를 모든 정렬이 완료될때까지 반복한다 한번 순회할 때 마다 마지막 원소 1개는 무조건 오른쪽 끝으로 가게 되어있다 그 모습이 마치 거품이 올라오는 것 같다고 bubble sort라는 이름이 붙었다고 한다 구현도 어렵지 않고 이해도 어렵지 않지만, 정렬 알고리즘중 대부분 케이스에서 최악의 효율을 자랑한다 따라서 실제로 이걸 만들어서 적용하게 될 경우는 ..

2023.02.08

최대공약수와 최대공배수 (유클리드 호제법)

코딩테스트의 문제를 풀다보면 종종 공배수, 공약수를 구해야 하는 문제가 나온다 공배수와 공약수가 실제로 어떤곳에 쓰이는지는 아직 잘 모르겠지만 이를 구하는 알고리즘인 유클리드 호제법이 존재한다 유클리드 호제법은 인류 최초의 알고리즘이라는 말도 있고.. 골자와 방식은 다음과 같다 두 양의 정수 a, b (a > b)에 대해 a = bq + r (0 a) { int temp = a; a = b; b = a; } // 2. r의 값을 구해 이 수가 0인지 구한다 int r = a % b; // 3. r이 0인지 확인하고, 0이 아니라면 r이 0이 될때까지 반복문을 돈다 while (r) { // 4. GCD(a, b) == GCD(b, r) 이므로 a = b, b = r로 대입 후 나머지를 계속 구한다 a =..

2023.02.08