알고리즘 일지

문제 링크 Problem - D - Codeforces  문제 풀이 마지막 포스팅 이후, 2개월 만에 문제풀이를 쓰는 것 같다. 오랜만에 코드포스도 쳤겠다... 요즘 저조한 퍼포먼스로 초심을 되찾고자 업솔빙 포스팅을 자세하게 적어보고자 한다. 대회 중부터 쭉 붙잡다가 2 시간 걸려서 푼 문제다. 이 글에 적은 풀이보다 더 쉬운 방법은, 조건에 맞지 않는 부분배열 B를 찾는 것이다. 하지만, 대회 때는 조건에 맞는 부분배열 B를 모두 찾는 것에 혈안이 되어, 이 부분을 놓치게 되었다. 문제. 배열 $A = [a_1, a_2, \cdots , a_N]$ 이 주어질 때, 배열 A의 부분배열 B가 다음을 만족할 때, 부분 배열 B의 개수를 찾아라. 부분배열의 크기를 $m$이라고 하자. A의 정렬 된 부분배열 B..

더 좋은 퀄리티를 위해 글의 내용이 바뀔 수 있습니다. 며칠 동안, 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..

오늘도 어김없이 버츄얼을 한판 돌렸다. 바쁘거나 그러지 않으면, 밤 10시쯤에는 버츄얼을 무조건 돌리고 있다.오늘은 성적이 역대급이지만, 버츄얼이라 그런지.. 오히려 좀 슬프다..  A. Verify Password 이 문제는 보자마자 좀 짜증이 났다... 저걸 언제 다 구현하지...그래서, 문제에서 요구하는 데로 Comparator를 하나 만들고, 정렬시킨 다음 똑같은지 비교했다.  B. Increase/Decrease/Copy$A$ 배열의 원소를 1, -1씩 연산해서 $B$배열을 만드는 최소 연산 횟수를 묻고 있다.근데 $B[N]$도 주어져서 $A$배열의 원소를 하나를 복사해 와야 한다. 최대한 가까울 때 복사해서 만들면 된다.. 간단한 구현이다.. A문제보단 쉬웠다. 구현만 하면 됐다.근데 한번 틀..