♣ 애드훅 라틴어로 'for this particular purpose'라는 뜻으로, 특정 상황에서만 정답이 되고 일반화될 수 없는 해답을 의미한다. 정형화된 방법론이 아니라 그 문제를 풀기 위한 창의적인 아이디어를 떠올려야 하는 경우를 애드훅 문제라고 한다. 따라서 코드를 재사용하는 것이 거의 불가능하다. 최적의 선택이 아니므로 개발 기간이 촉박할 때 급하게 요구 사항을 맞추는 데 사용된다. ♣ 백준 알고리즘 31631번 ♣ 문제 이해 빌딩의 숫자가 주어졌을 때, 빌딩 위로 가지를 날리는데 가지의 방향을 가장 많이 바꿀 수 있는 경우를 구하는 문제이다. 가지는 1번 건물에서부터 오른쪽으로 날아가기 때문에 맨 오른쪽 건물이 가장 높아야 한다. 그리고 나서 왼쪽과 오른쪽에 번갈아서 큰 건물을 넣는다. 1 ..

♣ 문제 이해하기 ♣ 문제 풀이 당연히 DP를 사용하는 문제이다. 포도주 세 잔을 연달아 마실 수 없을 때, 최대로 포도주를 마실 수 있는 방법을 찾아야 한다. 각 포도주 잔이 가진 양을 나타내는 배열을 drinks, 앞에서부터 마신 포도주를 적립한 양을 나타낸 배열을 dp라고 한다. 포도주를 마실 때마다 다음과 같이 선택할 수 있다. 1. i번째 포도주를 마실 때 1-1. i-1 번째 포도주를 마시지 않았을 때 i번째 포도주는 마시면서 i-1번째 포도주는 마시지 않았을 때, 최댓값을 구하려면 i-3번째 포도주와 i-2번째 포도주는 모두 마신 상태여야 한다. 따라서 dp[i] =dp[i-2] + drinks[i] 1-2. i-1번째 포도주를 마셨을 때 i번째 포도주와 i-1번째 포도주를 모두 마실 때는 ..

♣ 다각형의 넓이를 구하는 공식 CCW처럼 다각형의 넓이를 구하는 공식도 있다. CCW에서 본 신발끈 기법과 유사하다. 위와 같이 점들의 x, y 좌표가 주어지면 공식을 이용하여 면적을 구할 수 있다. 먼저 반시계 방향으로 꼭짓점 좌표들을 나열한다. 그리고 맨 처음 좌표를 맨 끝에 추가하여 나열한다. 신발끈 공식처럼 앞 꼭짓점의 x좌표와 뒷꼭짓점의 y좌표를 곱한 값들을 모두 더한다. 이번에는 반대로 앞 꼭짓점의 y좌표와 뒷꼭짓점의 x좌표를 곱한 값을 모두 더한다. 이제 첫 번째 결과에서 두 번째 결과를 뺀다 => 82-(-38) = 120 이 결과값을 2로 나누면 다각형의 넓이를 구할 수 있다. 단, 꼭짓점을 반시계 방향 대신 시계 방향으로 나열하여 계산하면 결과값이 음수가 된다. 그래서 음수가 나온 경..

♣ CCW 세 점 A, B, C가 존재할 때, 특정 선분에 대하여 특정 점이 왼쪽에 있는지(시계 방향) 오른쪽에 있는지(반시계 방향)를 판별할 수 있는 알고리즘이다. 아래 그림을 예로 들어보자. C -> B -> A로 진행하는데, 첫 번째 그림은 시계방향, 두 번째 그림은 직선, 세 번째 그림은 반시계 방향을 나타낸다. 즉 선분 CB에 대한 점 A의 위치라고 생각하면 점 A는 선분 CB에 대해 각 그림에 따라 시계방향, 직선, 반시계 방향에 위치하는 것이다. CCW(Counter Clock Wise)는 이렇게 세 점을 이었을 때의 방향을 판단하는 데 유용하게 쓸 수 있는 알고리즘이다. 점 A, B, C를 보면 선분 CB에 대한 점 A의 위치(방향)을 구하는 것이므로 점 C를 (x1, y1), 점 B를 (..

♣ 순열(permutation) 순열은 서로 다른 n개의 대상에서 r개를 뽑아 일렬로 배열한 것을 말한다. 이때 나올 수 있는 경우의 수를 수학식으로 아래와 같이 표현한다. 이때 배열의 순서를 고려해야 한다. 순서가 다르면 서로 다른 순열이다. 만약 [1, 2, 3, 4] 중 3개를 뽑아 배열하는 경우의 수를 구한다면 아래와 같다. 이와 같이 여러 수의 순서를 고려하여 배열하는 '순열'을 파이썬 코드로 만들 수 있다. ♣ 백준 알고리즘 문제 이해 1부터 N까지의 수로 이루어진 순열이 있고, 입력에서 주어진 특정한 수열의 바로 전 순열을 출력한다. 예를 들어 1부터 5까지의 수가 있고, 특정한 순열 5 4 3 2 1 의 바로 앞에 있는 순열은 5 4 3 1 2 이다. ♣ 문제풀이 방법1(순열 정의하기) 첫..

♣ Queue 개념 큐는 데이터를 보관하는 컨테이너이다. 먼저 입력된 데이터가 먼저 제거되므로 '선입선출'이라고 한다. 대기열은 앞과 뒤에 두 개의 끝이 있으며 항목은 후면에서 입력되고 전면에서 제거된다. Rear는 대기열 내부에 항목이 삽입되는 지점을 나타내고, Front는 대기열에서 항목이 제거되는 지점을 나타낸다. 큐에서 항목은 순서대로 제거되고 사이의 항목을 제거할 수는 없다. 파이썬에는 두 가지 형태의 큐가 존재한다. 1. 선입선출 큐 먼저 들어가는 요소가 가장 먼저 나온다. 이를 사용하려면 큐 모듈에서 Queue 클래스를 호출해야 한다. 2. 후입선출 큐 마지막으로 입력된 요소가 가장 먼저 나온다. 이를 사용하려면 대기열 모듈에서 LifoQueue 클래스를 호출해야 한다. ♣ Queue와 Li..