** 알고리즘 공부 방법/순서에 대한 글을 쓰고자 합니다. 내용은 차차 추가해 나갈 예정입니다. - 이 글은 하이퍼링크 형태로 작성 되었습니다. - 이 글은 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 책을 상당 부분 참고하여 작성하였습니다. - 이 글은 학부 과정에서 배우는 C언어와 기초적인 자료구조(큐, 스택, 그래프, 트리, 힙, 이진검색트리, 딕셔너리)의 이론적인 이해가 있음을 가정하고 작성하였습니다. ** 17.10.9) 웹상에 좋은 자료들이 많으니 대부분의 내용을 링크로 대체하겠습니다. ** 18.10.3) 링크 추가 및 업데이트 ** 18.10.17) 방법에 대한 글은 여기에 포스팅하였습니다. 이 글은 순서(커리큘럼) 에 관한 글입니다. ** 언어의 선택 알고리즘 문제를 해결하는데 있어서..
A. Anastasia and pebbles 문제 Anastasia 에게 2개의 주머니가 있고 각 주머니에 최대 k개의 조약돌을 넣을 수 있다. 또한 한 주머니에는 한 종류의 조약돌만 넣을 수 있을 때 모든 조약돌을 줍는데 걸리는 최소 일자를 구하는 문제이다. 문제 풀이 매일 각 주머니에 최대한 넣는걸 반복하면 된다. 소스 코드 B. Masha and geometric depression 문제 b, q, l, m 이 주어졌을 때 보드에 적게되는 수열의 수를 구하는 문제이다. 문제 풀이 b가 0인 경우와 q가 -1, 0, 1 인 경우들을 잘 분리해서 구현하면 된다.좀 더 생각해보면 q가 -1인 경우만 제외해서 구현하면 쉽게 구현할 수 있다.싸이클을 체크하는 use set와 bad integer를 저장하는 ..
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]+..
네트워크 플로우 포드풀커슨 \(min(O(Ef),O(VE^2))\)네트워크 플로우 디닉 \(O(V^2E)\) 1. 잔여용량이 존재하는 간선을 따라 BFS하면서 정점들의 level을 매겨준다. s가 level 0- t의 level이 정해지지 않는다면 더 이상 증가경로는 없음. (현재 유량이 최대 유량) 2. s부터 DFS하면서 t에 도달할 때 까지 항상 level[u]+1==level[v] 를 만족하는 edge만 따라서 이동한다.- DFS 종료 하면서 유량 갱신해주고 더 이상 증가경로가 없을 때 까지 반복한다.- DFS 시 추가적으로 현재 몇 번 간선까지 사용하였는지 저장하는 배열을 이용해서 불필요한 탐색을 줄인다. 3. 더 이상 증가 경로가 없다면 1.로 돌아간다.
A. Bear and Big Brother 문제 Limak 와 Bob의 몸무게가 주어진다. Limak는 매년 3배씩 커지고 Bob은 2배씩 커진다. Limak가 Bob보다 커지기 위해서는 최소 몇 년이 지나야 하는지 구하는 문제이다. 문제 풀이 단순하게 1년 씩 늘리면서 2와 3을 각각 곱하고, Limak가 커질 때 출력하면 된다. 소스 코드 B. Bear and Friendship Condition 문제 친구 관계가 그래프로 주어진다. 한 컴포넌트내의 모든 정점이 서로 연결되어 있는지(완전 그래프)인지 판별하는 문제이다. 문제 풀이 각 정점마다 연결된 간선이 해당 정점이 포함된 컴포넌트 크기 - 1 인지 확인한다. 소스 코드 C. Bear and Different Names 문제 N명의 군인이 있고, ..
째로탈출 2 문제 N*M 보드에 파란 구슬 빨간 구슬 구멍이 한 개씩 있고, 상하좌우 4방향으로 기울일 수 있을 때, 최소 몇 번 만에 빨간 구슬이 구멍에 나올 수 있는지 출력하는 문제이다. 단, 파란 구슬이 구멍으로 같이 나오면 실패이다. 문제 풀이 최대 10번 까지 보드를 조작할 수 있으므로, BFS 탐색을 이용하면 각 상태 공간에서 상하좌우 4방향으로 전이 가능 하고, 한 상태 공간에서 해당 방향으로 최대 \(max(N,M)\) 만큼 이동할 수 있으므로 \(O(4^{10} max(N,M))\) 임을 알 수 있다. 따라서 각 상태 공간 내에서 한 방향으로 이동 할 때1. 빨간 구슬과 파란 구슬이 일직선 상에 없음1.1) 빨간 구슬이 가는 길에 구멍이 있는 경우 --> 탈출 성공1.2) 파란 구슬이 가..
영화 수집 문제 쿼리마다 i 번째 영화 위에 쌓여있는 다른 영화의 수를 출력하는 문제이다. 문제 풀이 naive하게 쿼리마다 현재 영화보다 위에 있는 영화를 카운트하는 방식으로는 \(O(NM)\) 이라 불가능하고, 힌트로는 영화를 꺼냈을 때 그 부분이 밀쳐지지 않고 비워진다는 방식으로 이해한다는 것이다. 그리고 영화를 꺼내면 맨 위에 차곡차곡 쌓는다. 그래서 현재 i층에 영화가 존재하는지, 안 하는지를 저장하는 \(check[i]\)을 생각해 보자. index value 0 0 1 0 2 0 .... .. m 1 m+1 1 m+2 1 ... ... m+n-1 1 초기의 \(check[i]\)값은 위와 같다. 여기에 현재 i번째 영화가 어디 있는지에 대한 \(idx[i]\) 배열을 만들어 준다. 초기에는 ..