문제 링크 https://www.acmicpc.net/problem/16720 가장 왼쪽 위에서 출발해 오른쪽 밑으로 도착해야한다. 맨 윗줄과 아랫줄 사이에는 벽들이 있는데, 한 줄당 세 칸의 벽과 한 칸의 통로가 있으며, 한 줄을 통째로 밀어 통로의 위치를 이동시킬 수 있다. 간단하게 풀 수 있다. 우선 현재 위치에서 왼쪽 혹은 위로 가는 경로는 당연히 제외한다. 저 두 상황을 제외한다면 단순히 인접한 길로 이동하는 총 시간은 어떻게 가도 같게된다. 다음으로 어떤 벽을 어떻게 회전시킬지를 결정해야 한다. 통로의 위치를 한 열로 몰아준다.생각하기 싫어서 1, 2, 3, 4번 열 모두 한 번씩 해본 뒤 가장 작은 값을 구했다. 답을 { 3 (오른쪽으로 이동) + (n - 1) (아래로 이동) + $\sum..
문제링크https://www.acmicpc.net/problem/16719 문자열을 하나씩 추가해나갈 때, 그 문자열들이 사전 순으로 출력되게끔 해야 한다. 어떤 구간에서 가장 작은 문자를 찾아 체크하고, 전체 문자열에서 체크된 문자들만 출력한다. 그다음 그 문자를 기준으로 오른쪽 구간, 왼쪽 구간의 순서로 처리한다. 예제의 STARTLINK로 예를 들자. 1) 우선 전체 구간 중 가장 작은 문자는 A이다. A에 체크 후 출력한다. 문자 S T A R T L I N K 인덱스 0 1 2 3 4 5 6 7 8 출력 O 2) A를 기준으로 오른쪽구간 [3, 8]에서 같은 과정을 거친다.가장 작은 문자 I에 체크 후 체킹된 문자들을 출력한다. 문자STARTLINK인덱스012345678출력 O O 3) I 기준..
[알고리즘] CCW로 세 점의 방향성 판별하기
0. 들어가기 전에 첫 알고리즘 포스트입니다. 이번에 쓸 내용은 CCW입니다. 원래는 기하 알고리즘들을 전반적으로 다루려고 했는데 생각보다 글이 길어져서 CCW만 쓰게 되었습니다. 본 글의 내용은 고등학교 과정(2007 개정 교육과정 기준)인 '기하와 벡터' 수준의 지식만 있으면 얼추 알아들을 수 있지만, 혹시 그렇지 않다면 설명을 봐도 이해가 안가실 수 있습니다. 급하게 CCW를 사용해야 한다면 바로 아래의 한 줄 요약과 본문 하단의 코드(여기)만 보고 쓰시면 됩니다. 1. CCW 기하 알고리즘을 공부하기 전에 필수로 알아야 할 것이 있는데, 그게 바로 CCW입니다. 거의 사칙연산처럼 쓰게 될 거에요. CCW는 Counter Clockwise의 약자로써, 평면 위에 놓여진 세 점의 방향관계를 구할 수 ..
문제 링크 15922 아우으 우아으이야!! 문제와 같은 문제입니다. 예전에 썼던 풀이 그대로 퍼올게여. 문제를 풀기 위해 수직선들을 좌표가 낮은 순으로 정렬하자. 그리고 앞의 수직선부터 탐색한다. 인접한 두 수직선의 관계는 다음과 같다. 빨간 선의 양 끝점을 $s, e$라 하고, 파란 선의 양 끝점을 $ns, ne$라 하자. ①은 $s \leq ns$ & $ne \leq e$인 경우이고, 더 작은 선분을 무시하는걸로 해결할 수 있다. ②는 $ns < e$인 경우이고, 중복해서 더해지는 $e - ns$값을 빼주면 된다. ③의 경우엔 그냥 둘 다 더하면 된다. 파란 선은 현재 내가 보고있는 선분, 빨간 선이 파란 선분의 바로 직전 선분이다. 정답 코드
문제 링크 기억하는 알파벳이 판별할 문자열에 순서대로 들어있는지 확인하면 된다. 비슷한 문제로 15904 UCPC는 무엇의 약자일까? 가 있다. 기억하는 알파벳의 문자열을 $s$라 하고 판별해야 하는 문자열을 $x$라 하자.$s$는 별개의 인덱스 $idx$를 가지고, $x$를 순서대로 탐색하면서 $s[idx] = x[i]$이면 $idx$를 증가시킨다.$idx$가 $s$의 끝까지 간다면 모두 나온 것이니 "true"를 출력하고, 그렇지 않으면 "false"를 출력한다. 정답 코드 질문 및 피드백 환영합니다.
문제 링크 14268 내리갈굼 문제와 15782 Calculate! 2 문제와 같은 유형이다.자세한 풀이는 링크를 들어가면 있다. 두개 다 보면 이해 간다. 세그먼트 트리를 이용하긴 하지만 쿼리는 구간이 아닌 한 정점에서만 물어보므로 lazy propagation을 단순히 O(lgN)의 시간복잡도로 해결하기 위해 사용한다.따라서 세그먼트 트리에서 리프노드 이외의 노드의 값은 뭐가 들어있던 상관이 없기 때문에 코드의 29, 41번째 줄에서 v를 한 번만 더해줬다(리프노드에선 원래 한 번만 더해진다). 크게 상관있는 부분은 아니다. 정답 코드 질문 및 피드백 환영합니다.
문제 링크 트리의 한 노드가 갈굼당하면 그 자식들이 모두 갈굼당해야한다. 구간이 보인다. 트리를 평평하게 펴서 세그먼트 트리로 만들고, lazy propagation을 적용하자.비슷한 문제로 15782 Calculate! 2 가 있다. 트리를 펴는 자세한 설명은 해당 링크를 보자. 위 링크와 차이점은 이번에는 pre-order로 순회했다는 것이다. 두 배열 $l$과 $r$, 주어진 트리의 어떤 정점 x에 대해 $l[x]$는 세그먼트 트리에서 x의 시작 구간이고 $r[x]$는 끝 구간이다. 이를 dfs로 쉽게 구할 수 있다.$l[x]$는 순회하는 순서로 값을 채워넣으면 된다.$r[x]$는 모든 자식들을 순회한 뒤 $l[x]$에서 자식 수만큼 증가시켜 넣어준다. (이는 세그먼트 트리에서 x의 마지막 자식의 ..
문제 링크 https://www.acmicpc.net/problem/15923 문제가 너무 쉬워서 설명할 게 없다. 방금 받은 좌표를 nx, ny라 하고 직전에 받은 좌표를 x, y라 하면 ans += abs(x+y-nx-ny) 이다. 내용이 너무 없으니 입출력 조건이라도 쓰자. 입력첫째 줄에 꼭지점의 개수 N이 주어진다. (4 ≤ N ≤ 20) 이후 둘째 줄 부터 N개의 줄에 걸쳐 꼭지점의 좌표 (x, y)가 주어진다. 좌표는 40 이하의 음이 아닌 정수이며, 중복되는 좌표는 주어지지 않는다.출력욱제가 설계한 건물의 둘레의 길이를 출력한다. 정답 코드