2048(Easy) 문제 게임의 규칙이 문제의 설명과 같을 때 최대 5번 움직여서 만들수 있는 최대 블록의 값을 구하는 문제이다. 문제 풀이 1. 깊이가 최대 5이고 하나의 상태공간에서 상하좌우 4개의 상태공간으로 전이 가능하다. 다음 상태공간을 만드는데 \(O(N^2)\)이 걸리므로, \(O(N^2 4^5)\) 로 해결 가능하다.2. 각 행(또는 열)에 대해 0이 아닌 블록들을 모은 후 2개씩 묶어서 합치는게 가능하면 합친다. 결과를 다시 해당 열에 복사한다.3. 구현 팁으로는 상, 하 // 좌, 우는 각각 순서만 반대로 넣으면 되고 세로와 가로는 행과 열만 바꾸어 넣으면 된다. ** 구현 실수하기 쉬운 예를 적어 보겠다.- 상, 하, 좌, 우를 따로 구현 하였는데 규칙이 다르게 구현 되어있음.- 2 ..
뱀 문제 (0, 0) 에서 뱀이 오른쪽 방향을 보고 출발한다. n개의 명령 (이전 명령으로 부터 t시간 뒤에, dir 방향으로 머리를 돌림)을 수행하면서 격자판 밖으로 나가거나 자신의 몸에 부딪히는 시간을 구하는 문제이다. 문제 풀이 뱀이 지나온 칸들을 선분으로 저장해서 관리하기로 한다. 1. 초기에 테두리 선분 4개를 추가해준다. 2. 추가적으로 모든 명령이 끝난후 에도 선분에 부딪히지 않을수 도 있으므로 (inf,R) 명령을 하나 넣어준다. 3. 현재 (x,y)에서 dir 방향으로 이동할 때 현재 까지 저장된 선분들과 비교하여 최대로 이동할 수 있는 시간을 구한다. 4. 이 시간이 t보다 같거나 작으면 t시간을 이동하기 전에 선분들 중 하나에 부딪히는 것이므로 답을 출력한다. 5. 아니라면 t시간 만..
이분매칭 포드 풀커슨 \(O(VE)\) 이분매칭 호프크로프트 카프 \(O(\sqrt{v}E)\) a->b 형태로 매칭 한다고 하였을 때. 1. 매칭되지 않은 a 정점을 level 0으로 하여 bfs 한다. 2. b정점이 매칭되어 있고 (matched_b[b]!=-1) 해당하는 a 정점의 level이 정해지지 않았다면 (level[matched_b[b]]==-1) 해당 정점의 level을 갱신한다. (level[matched_b[b]]=level[a]+1) 3. 매칭되지 않은 모든 정점에서 dfs 한다. b정점이 매칭되지 않았거나, 매칭된 a정점의 level이 현재 정점 level+1이라면 새로운 증가경로를 탐색한다. (matched_b[b]==-1||(level[matched_b[b]]=level[a]+..