알고리즘 일지

더 좋은 퀄리티를 위해 글의 내용이 바뀔 수 있습니다. 며칠 동안, Fortune's Algorithm에 관한 글들을 찾아 읽으며, 원리와 그 작동방식.. 그리고 심각한 부동소수점의 오차 때문에 엄청 고생했다... 제일 답답했던 점은, 내 검색 엔진이 이상한 건지는 모르겠지만 이상하게만치, Fortune's Algorithm에 구현에 관한 자세한 설명이 있는 곳이 별로 없다는 것이었다. 물론 Fortune's Algorithm이 구현부가 굉장히 난해하고, 하나하나 짚고 넘어가면, 엄청나게 설명해야 할 것이 많기 때문에 웬만한 연산에 대해, 설명을 생략하는 글들이 대부분이었다... 무튼, 그래서... Fortune's Algorithm이 뭐냐...? 보로노이 다이어그램 (들로네 삼각분할)을 O(NlogN)..

문제 링크30788번: Sakura Reflection  문제 풀이 기하학 + DP 섞인 문제들을 풀다가... 만난.. 정말 어렵고.. dp에 관해 깨달음을 얻게 해 준 문제다.일단, Sakura Reflection 표지로 생각하면 너무 어려우니까, 간단하게, 원에 화살표가 그려진 사진으로 생각해 보자. 0$^\circ$ 에서 179$^\circ $ 틀어진 축을 기준으로 대칭을 시키면, 그 사진은 회전과 동시에, 좌우 반전이 된다. 좌우 반전이 되지 않은 상태일 때, 회전된 각도는 0$ ^\circ$에서, 359$ ^\circ$ 만큼 되어 있을 수 있다. 자 그럼, 사진의 기울어진 정도에 따라 상태를 0에서 359라고 인덱싱 해보겠다. 그 기준은, 화살표가 보고 있는 방향이라고 생각하고 정의하면 편하다...

문제 링크27577번: Everything Is A Nail 문제 풀이 오랜만에 BOJ를 탐닉하다... 사람들이 풀고 있길래... 찍먹을 해보게 되었습니다..간단하게 설명하면, 처리해야 하는 작업의 종류가 0, 1, 2 세 가지가 있고, 각 작업이 순서대로 주어집니다.이때, 작업을 처리해야 하는 도구가 존재하고, 첫 번째 도구는 마음대로... 그리고 다른 도구들로 한 번씩 변경 가능합니다. 즉, 배열안을 세 파티션으로 나눈 다음, 각각의 지정된 원소가 몇 개 있는지 총합한 값을 최대로 만드는 문제로 바라볼 수 있겠습니다. 근데 도구 선택이 자유로우므로, 도구를 드는 순서 3! 번 다 정하고 해보면 되겠습니다. 다르게 풀수도 있지만, 상위문제에서는 이런 유형의 문제가 많이 존재하는데요. 거의 작업종류가 엄..

안녕하세요. 참가자 여러분들! 이번에도 운영진으로 참가한 황현석이라고 합니다. 반가워요! 이번에도 역시 출제자, 검수자 여러분들 수고 많았습니다! 제일 바쁘셨을 시온형도 고생많으셨습니다. 대다수의 문제 출제에 기여한 준원님도 고생 많으셨고요 ㅎㅎ 대회 끝나고, 집에와보니, 데이터가 약했다는 소식을 듣고, 씻지도 않고... 책상에 앉아 코드 좀 막고, 보강 좀 하느라, 녹초가 되었던 것 같습니다. 몸도 힘들고, 마음까지 뒹숭생숭하니까 정신이 없던 하루가 된 것 같아요. 거두절미하고 늦은 밤이라 풀이만 짧게 써보려고 합니다!A. 햄버거문자열 하나를 원하는 위치에 옮겨서, 햄버거 모양을 만드는데 필요한 최소한의 연산 횟수를 묻고 있습니다.간단하게 구현하거나 특징을 찾아서 풀려는 시도가 있었는데, 저는 제일 깔..

문제 링크https://www.acmicpc.net/problem/1146 문제 풀이 일단 수는 1부터 $N$까지 하나씩만 사용하면 된다. 일단 수열을 만드는 조건을 조금 단순화 시켜서 시각화 해보면,3번째 수를 2번째 수보다 큰 수에서 골랐다면, 그 다음 4번째 수는 3번째 수보다 작은 수, 그 다음은 4번째 보다 큰 수 이런 식으로 지그 재그 모양으로 고르게 된다. 이런 식으로 지그재그 모양으로 고르게 된다. 여기서, 우린 dp로 경우의 수를 구해 줄 수 있다. $N$개의 수가 있을 때, 우린 최초의 수 $a$를 선택해보자. 그 다음 수 $b$를 선택하면, 우린 $a \rightarrow b$로의 수열을 일단 만들 었고, $b$에서 $a$로의 역방향 ($a$에서 $b$로의 증감 반대) 으로 시작하는 ..

문제 링크9616번: 홀수 정사각형 (acmicpc.net) 문제 풀이 자 문제에서는 $N, \; M$을 주지만, 일단 $N$과 $M$에 각각 1씩 더해서, $N \times M$ 격자점에서 사각형을 만드는 것으로 바꾸자. 일단 쉽게 한 변의 길이가 홀수인 정사각형을 평면에 맞게 평행하게 몇 개 만들 수 있는지부터 계산해 보자. 한 변의 길이가 $2i - 1$인 정사각형은, 격자점이 총 $(2i) \times (2i)$개가 필요하다.  그리고 수식으로 나타내면, 가로로는 $N - 2i$ 번, 세로로는 $M - 2i$번 움직 일 수 있다.그리고 한 변이 먹는 격자점은 $2i$개 이므로, 이것이 $N$ 이나 $M$을 초과 하면 안 된다.$$2i \leq \min(N, M)$$$$i \leq \bigg\lfl..

문제 링크Problem - D - Codeforces Problem - D - Codeforces codeforces.com  문제 풀이 평소에 그냥 딱 하고 풀리던 Dp문제들과 다르게 조금 오래걸려서 풀이를 쓰면서 익숙해지려고 한다. 왜 풀리는지 살짝 이해가 안 돼서 써보면서 나도 이해하려고 한다. 일단 Alice 는 케이크를 무조건 가중치가 적은 것부터 먹는 게 유효한 전략이다.따라서, 배열의 값들을 잘 압축하고, 갯수를 세서 재정렬한다. 즉, {4, 6, 1, 3} 이와 같이, 가중치가 낮은 순으로 정렬해서, 개수만 나는 담았다. 그럼 Bob이 Alice를 방해하는 전략이 중요하다. 근데, 전략이 유효한 전략이 없어서, 다이나믹 프로그래밍으로 모든 경우의 수를 적절하게 시행해야 한다. 이 시행방법을..

문제 링크https://www.acmicpc.net/problem/1514 문제 풀이 자물쇠를 돌려야 한다. 영향을 끼쳐서 나오는 경우의 수가 자물쇠의 3다이얼 밖에 안 되니 $10^3$ 정도이다.자물쇠를 돌리는데에 있어서, 어떠한 유효한 방법이나 선택적 전략이 없기 때문에, 다이나믹 프로그래밍을 하며 모든 경우의 수를 시험해봐야 한다. 다이나믹 프로그래밍에서 어려운 점은 이런 까다로운 많은 분기에서의 dp의 정의라고 할 수 있다.dp테이블을 잘 정의하는 것이 dp를 쉽게 푸는 길이라고 생각한다. 내가 정의한 dp는 다음과 같다. $dp[N][i][j][k] $ 은 $N$번째 다이얼까지 맞췄을 때, $N+1$번째 다이얼이 $i$번, $N + 2$번째 다이얼이 $j$번, $N+3$다이얼이 $k$ 번째를 향..