프로그래밍

이분 탐색(Binary Search)이분 탐색이란 정렬된 배열에서 범위를 반씩 줄여나가면서 원하는 값을 탐색하는 방법으로, 분할 정복(Divide and Conquer)을 사용하는 대표적인 알고리즘 중 하나이다.이분 탐색이라는 단어를 모르더라도, 업-다운 게임을 해봤다면 한 번쯤 써본적이 있는 기법일 것이다.  위 그림은 파란색 표시된 값 9를 이분 탐색으로 찾는 과정이다.각 상황에서의 중앙값과 찾고자 하는 값을 비교하며 범위를 줄여나간다. 구현해보기(코드)두 변수 $low$와 $high$를 이용해 탐색 범위를 관리할 것이다.초기 범위를 0 ~ (배열의 길이 - 1)로 두고 범위를 점점 좁혀나가면 된다.def binarySearch(arr, target): low, high = 0, len(arr)..

CCW(Counter-clockwise) 알고리즘 CCW 평면에서 세 점의 방향 관계를 구하는 알고리즘이다. 세 점 A, B, C가 순서대로 반시계 방향이면 양수, 직선 방향이면 0, 시계 방향이면 음수를 반환하게 된다. CCW의 원리: 벡터의 외적 위의 표에서 반시계 방향인 경우를 벡터로 표시해보았다. 두 벡터를 외적하여 생긴 벡터의 크기는 아래와 같다. $$ | \vec{AB} \times \vec{AC} | = |\vec{AB}||\vec{AC}|sin\theta $$ 위 식에서 $|\vec{AB}|$와 $|\vec{AC}|$는 양수이므로, $sin\theta$에 따라 값이 결정된다. 즉, 외적한 벡터의 크기는 $\theta$가 0° 초과 180° 미만인 경우 양수, 180° 초과 360° 미만인..

길이가 $N$인 수열 ${a_n}$에서 연속되는 $K$개의 원소의 합 중 가장 큰 값을 구하여라. 보기에는 간단해 보이는 이 문제, 어떻게 해결할 수 있을까? 방법1: 모두 계산해보기 가장 먼저 떠오르는 방법은 반복문을 이용해 모두 다 계산해보는 방법이다. 가능한 모든 범위에 대해 합을 구한 후, 최댓값을 출력하면 정답이 나오게 된다. answer = -float('inf') for i in range(N - K + 1): answer = max(answer, sum(a[i:i+K])) print(answer) 위 방식의 시간 복잡도는 $O(NK)$이다. 방법2: 불필요한 연산 줄이기 (슬라이딩 윈도우) 방법1의 방법을 표로 나타내면 아래와 같다. $i = 0$에서 $i = 1$로 갈 때, 식에서 $a[..

'좌표 압축 기법'이란? 여러분은 배열 $A_n$을 이용해 문제를 해결하고자 한다. 그런데 배열의 수의 범위($Min(A_n)$ ~ $Max(A_n)$)가 너무 커서 주어진 제한 시간을 맞추기 힘들다. 수의 값과 무관하게 숫자 간의 대소 관계만 필요하다면, 수의 범위를 줄일 수 있을까? $A_n$의 길이가 수의 범위보다 작다면, 좌표 압축 기법을 이용해 수의 범위를 줄일 수 있다. 어렵게 생각할 필요 없이, 숫자를 크기 순으로 정렬해 각각의 수에 0부터 숫자를 하나씩 매겨주면 된다. 예를 들어, $[-7, 100000, 876]$이 있다고 해보자. 크기 순으로 숫자를 매겨주면 $[0, 2, 1]$이 된다. 이렇게 수의 범위를 줄이는 테크닉을 좌표 압축이라고 한다. 구현해보기 좌표 압축은 아래와 같은 단계..

길이가 N인 수열 $\left\{ a_n \right\}$에서 아래의 연산을 $M$번 수행하시오. • 두 정수 $i$, $j$($i \leq j$)를 입력 받아 $\sum_{k=i}^{j}a_k$ ($=a_i + a_{i+1} + ... + a_j$)를 구하여라. 방법1: 매번 다 더해보기 문제에서 요구하는 연산은 $a_i$부터 $a_j$까지 다 더하면 되는 것으로, 구현하기 어렵지 않다. 바로 아래와 같이 코드를 짜볼 수 있겠다. for _ in range(M): i, j = map(int, input().split()) answer = 0 for k in range(i, j + 1): answer += a[k - 1] print(answer) 첫째 항인 $a_1$이 리스트 a에서는 a[0]이므로. $..