목록Algorithm (121)
블로그 옮겼습니다
(해싱에 대한 개념은 제 개인적인 생각이 많이 섞여있어서 틀린 내용이 있을 수도 있다는 것을 미리 밝힙니다.) 해싱은 어떤 큰 데이터(스트링, 트리 등)가 있을 때 이 것을 하나의 수로 나타내어 비교를 하기 쉽도록(그리고 빠르도록)할 때 유용하다. 기본적으로 컴퓨터에서 저장할 수 있는 수의 크기의 한계가 존재하기 때문에보통 해시값은 아무리 커도 long long 범위 내에 들어 와야 한다. 그래서 modular 연산을 사용하게 되는데그러면 문제가 생길 수 있는게 서로 다른 데이터 인데 해시값이 같은 경우가 생길 수가 있는 것이다. 그래서 원래의 해쉬테이블은해시값이 단순히 해쉬테이블의 인덱스를 나타내고 그 인덱스에 실제 데이터가 링크드 리스트와 같은 형태로 연결되어서결국 실제 데이터를 찾는 과정이 필요하기..
이 문제는 흔히 가로외 세로의 길이가 같은 격자판에서 각 칸이 검은색 또는 흰색으로 이루어져 있을때 자식이 4개이거나 0개인 트리로 격자를 표현하는 '쿼드 트리' 라는 개념의 변형 문제이다. 격자가 주어졌을때 이 격자를 가장작은 정사각형모양으로 키우고 새로생긴 격자를 흰색으로 채운 뒤 쿼드트리의 노드의 개수를 구하는 것이 첫번째 요구되어지는 것이고 그다음엔 압축된 쿼드트리의 노드 수를 구해야 하는데 압축을 하는 방법은 공통된 서브 트리들을 딱 하나만남겨서 공유하는 것이다. 이렇게 할때 최소한의 노드 수를 사용하도록 압축했을 때의 노드의 수를 구하는 것이 두번째 요구되어지는 답이다. 우선 복잡도 계산을 위해 총 노드 수의 상한을 계산해보자. 격자의 가로 세로 길이는 128이 최대이기 때문에 쿼드트리의 높이..
http://codeforces.com/contest/681/problem/E 바퀴벌레의 좌표와 속도, 시간이 주어지고 N개의 접시에 대한 정보(좌표와 반지름)가 주어질 때 바퀴벌레가 접시 안에 들어가면 살 수 있는데 처음에 정한 방향으로만 갈 수가 있을 때, 바퀴벌레가 살 수 있는 확률을 구하는 문제 우선 바퀴벌레의 속도와 시간을 곱하면 바퀴벌레가 갈 수 있는 최대 거리가 되며, 바퀴벌레의 위치를 중심으로하고 반지름이 최대 거리인 원을 그렸을 때 접시들과 겹치는 방향들의 seq 들의 합집합의 각도들의 합에 대해 2π 로 나눠 주면 답이 된다. 일단 하나의 접시에 대해서만 생각해 보자. 우선 바퀴벌레의 이동가능 범위 원과 접시가 겹치지 않는다면 이 접시는 살 수 있는 확률을 전혀 증가시켜 주지 않는다. ..
https://community.topcoder.com/stat?c=problem_statement&pm=11476 N
https://community.topcoder.com/stat?c=problem_statement&pm=11500 우선 문제는 흔히 알고있는 '사천성' 이라는 게임을 최소한의 턴 수로 클리어 하기 위해 필요한 턴 수의 기대값이다.그냥 그때 그때 최적의 선택을 할 때 클리어 하는 데 필요한 턴 수의 기대값이라고 생각하면 될 것 같다. 처음에 실수할 수 있는 것이 뭐냐면.. 실제로 게임을 할 때 뒤집혀 있는 두개의 칸을 선택하면 이 두개가 동시에 뒤집히는것이 아니라 하나씩 선택을 하는데, 하나를 선택하면 이것이 뒤집하고 이 정보를 바탕으로 더 최적의 선택을 할 수가 있기 때문에 답이 다르게 나온다는 사실이다. 문제에서 플레이어는 한번 뒤집었던 칸의 모양은 평생 기억한다고 되어있기 때문에 클리어 까지 필요한..
이 문제는 M개의 트리가 주어지고 각각의 트리에 대해 하나의 엣지를 선택하여 오른쪽 트리에게 주었을때(마지막 트리는 맨 처음 트리에게 준다.) 각 M개의 트리가 여전히 모두 트리가 되도록 간선을 선택하는 모든 경우의 수를 계산하는 문제이다. 우선 이 문제는 dp 로 풀 수가있다. 그래서 내가 처음 생각해낸 풀이는 dp[i][u][v] : i-1번째 트리에서 엣지 u-v 를 선택했고 i번째 트리부터 엣지들을 잘 선택했을때 M개의 트리가 여전히 트리인 경우의수 이렇게 하면 각각의 트리의 모든 엣지에 대해 없애보고 이전 트리에서 넘겨준 u-v 를 추가했을 때 여전히 트리가 된다면 선택하고 다음트리로 넘어가는 식으로 구현하면 되고 기저 케이스는 M번째 까지 왔을 때 0번째 트리에서 삭제한 엣지를 저장해 두었다가..
http://codeforces.com/contest/787/problem/C 이 문제는 게임 dp 문제인데 Nim 게임과 같은 게임 dp 문제와 다른점이 하나 있다. Nim 게임에서는 보통 두 플레이어가 매 턴 마다 돌을 한개 이상씩 가져가기 때문에 돌이 점점 줄어들고, 그렇기 때문에 돌의 개수와 현재 차례인 플레이어, 이 두가지로 하나의 상태를 정의할 때 그래프로 표현해 보면 노드 A에서 노드 B로 가는 경로가 여러개가 있을 수는 있지만 한번 방문한 노드는 다시 방문되어지지 않는다 (즉, 사이클이 없다) 하지만 이 게임에서는 monster 가 움직일 칸 수를 번갈아서 결정하다 보면 게임 판이 원의 형태로 되어있기 때문에 현재 차례인 플레이어와 현재 monster의 위치가 다시 같은 상태가 돌아올 수도..
http://codeforces.com/contest/681/problem/D 간단하게 문제를 설명하자면, N개의 사람이있고 M개의 연결관계가 주어진다그리고 하나의 컴포넌트는 트리구조를 이룬다. (여러개의 컴포넌트로 이루어질 수도 있음)N명의 사람들 각각은 선물을 주고 싶은 사람이 한사람 씩 있는데 이 한 사람은 무조건 자기 자신이거나 자신의 조상이어야 한다. 또, 우리는 어떤 list를 작성해야하는데각 N명의 사람들은 list의 맨왼쪽에 있는 명단부터 차례대로 봐가면서 무조건 가장 처음으로 등장하는 조상에게 선물을 줘야한다. 그리고 만약 list를 끝까지 다 봤는데도 자신의 조상이 나오지 않는다면 아무에게도 선물을 주지 못하고 집에간다. 문제는 N명의 사람모두가 자기가 선물을 주고 싶은 사람에게 선물을..
그래프 + dp 이다. N
사실 원래의 풀이와 아주 큰 차이는 없다. 두번의 dfs를 돌리는 것까지는 똑같지만 변수가 하나 줄었고, 점화식이 좀 더 단순해 졌다. 우선 size(i) 는 i를 루트로 갖는 서브트리의 총 노드수라고 보면노드 i 부터 자손들까지의 거리의 총합 S(i)는,노드 i의 자식이 c1, c2, c3..... cn 이고, ck 와 연결된 간선의 가중치는 wk 일때size(c1)*w1 + size(c2)*w2 +....+size(cn)*wn +S(c1) + S(c2) + S(c3) +.....+S(cn) 이다.즉 각각의 간선에 대해 몇번 지남당하는지를 계산한다고 보면된다. 이렇게 각각의 간선에 대해 몇 개의 경로에 대해 지남 당하느냐로거리 의 총합을 구하는 경우가 많은 것같다. 트리상에 존재하는 모든 정점쌍간의 거..