목록Algorithm (111)
S E P H ' S
BOJ 2750, 2751 수 정렬 문제를 풀면서 여러 정렬 알고리즘에 대해 알아둘 필요를 느끼게 되었습니다. 이번 포스트에서는 2751에서 사용된 정렬 알고리즘에 대해 학습하고 여러 정렬 알고리즘에 대해서는 이어질 다음 포스트에서 자세히 다루겠습니다. 문제 원인 파악 2750 문제와 달리 2751은 Java의 Arrays.sort() 를 사용하면 시간초과가 날 수 있습니다. Arrays.sort()의 경우 dual-pivot Quicksort 알고리즘을 사용한다고 합니다. 이 알고리즘은 평균 시간복잡도가 \(O(nlogn)\)으로 매우 빠른 알고리즘이지만 최악의 경우는 \(O(n^2)\)이기 때문에 주의해야 합니다. 그렇기 때문에 최악의 경우에도 \(O(nlogn)\) 혹은 \(O(n)\) 에 가까운 ..
정의 정렬되어 있는 리스트에서 어떠한 데이터를 찾을 때, 순차 탐색과 같이 모든 값을 대조하여 찾는 것이 아니라 탐색 범위를 절반씩 줄여가면서 찾는 방법입니다. 작동원리 예를 들어서 1,2,3,4,5,6 가 들어있는 배열에서 찾으려고 하는 값이 6이라고 한다면 배열의 중간 값(= mid)인 3과 6을 비교합니다. 6은 3보다 크기 때문에 3보다 작은 값들과는 비교할 필요가 없으므로 3보다 큰 값들인 4,5,6 중에서 대조를 합니다. 다시 이 중의 중간 값인 5와 6을 비교하고 6은 5보다 크므로 5보다 작은 값들과는 비교할 필요가 없습니다. 이제 5보다 큰 값과 비교하면 되는데 5보다 큰 값은 이제 6밖에 없으므로 결과를 찾은 것입니다.
2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 풀이 최대공약수 : 두 수의 약수 중에서 가장 큰 수. 유클리드 호제법에 의해 쉽게 구할 수 있다. 최소공배수 : 두 수의 공통된 배수 중에서 가장 작은 수. 주어진 두 수의 곱에서 두 수의 최대공약수를 나눈 값과 같다. def GCD(a, b): while b: a, b = b, a % b return a def LCM(a, b): return a * b // GCD(a, b) a, b = map(int, input().split()) print(GCD(a, b)) print(LCM(a, b))
코딩테스트 연습 - n^2 배열 자르기 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부 programmers.co.kr 풀이 지문 2에서 '1행 1열 부터 i행 i열까지의 영역 내의 모든 빈 칸 숫자 i로 채웁니다'라고 되어있다. 즉, 행과 열에 하나라도 2가 있으면 그 곳은 2, 3이 있으면 3이 되는 것. 그래서 n이 3이라 가정할 때, 2차원 배열은 다음과 같다. 1 (0,0) 2 (0,1) 3 (0,2) 2 (1,0) 2 (1,1) 3 (1,2) 3 (2,0) 3 (2,1) 3 (2,2) 3번에 따라서 이를 행마다..