전체 글

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]이므로. $..

N+1개의 물건을 N개의 상자에 넣으면, 적어도 하나의 상자에는 두 개 이상의 물건이 들어간다. 오늘은 당연하면서도 다양한 곳에 적용할 수 있는 비둘기집 원리에 대해 알아보겠다. 증명 N+1개의 물건과 N개의 상자가 있을 때, 각 상자에는 한 개 이하의 물건만 들어가있다고 가정해보자. 각 상자에는 최대 1개의 물건이 있을 것이므로, 총 물건의 수는 많아야 N개이다. 그런데 N+1개의 물건이 있으므로, 이는 모순이다. 따라서 N+1개의 물건과 N개의 상자가 있을 때, 적어도 하나의 상자에는 두 개 이상의 물건이 들어간다. 귀류법을 이용해 쉽게 증명하였다. 귀류법이란 명제의 결론이 부정임을 가정했을 때 모순 발생함을 보여 명제가 참임을 증명하는 방법이다. 예시 한 반에 13명 이상의 학생이 있다면, 최소 2..