https://www.acmicpc.net/problem/14868 풀이 과정시드마이어의 문명과 비슷한 게임을 구현하는 시뮬레이션 문제문명이 건설되었을 때, 시간이 지남에 따라 점점 퍼지다가 두 문명이 인접하면 하나의 문명으로 합쳐진다.이때 모든 문명이 하나로 합쳐지기까지 걸리는 시간을 구하는 문제이다. 문명이 건설되었을 때 퍼지는 것은 BFS로 구현할 수 있고, 문명을 하나의 그룹으로 합치는 것은 분리집합으로 구현할 수 있다.(분리집합을 사용하지 않고도 풀 수 있다는데, 그렇게는 안 풀어봤다.) from collections import dequeimport sysinput = sys.stdin.readlinedef find(x): if parent[x] == x: return x ..

문제 설명https://www.acmicpc.net/problem/1876 지름이 20cm 인 볼링공을 너비 105cm 인 레인 위에서 굴린다.볼링공이 구르기 시작한 첫 위치는 레인의 정 가운데 위치이고, 해당 위치에서 x도 각도로 굴린다.굴러간 공은 레인 벽과 부딪히면 입사각과 동일한 각도로 반사되어 튕긴다.볼링공이 구르기 시작한 첫 위치로부터 T 미터 떨어진 곳에 지름 12cm 인 볼링 핀이 있다. 처음 굴리기 시작한 각도 x 와 볼링공과 볼링핀 사이 거리 T 가 주어질 때, 이 볼링공이 볼링핀을 맞히는지 여부를 출력하라.  접근 방법우선 각도에 따라서 공이 여러번 튕길 수 있고, 매번 튕기는 것을 다 시뮬레이션으로 구현하는 것은 너무 복잡해보였다.그래서 수학적으로 문제를 풀 수 있을 것 같아서 태블..

https://www.acmicpc.net/problem/1248어떤 수열의 연속하는 모든 부분수열 ai ~ aj 에 대한 합의 부호값 (+, 0, -) 를 알고 있을 때, -10 ~ 10 사이의 숫자를 사용하여 만들 수 있는 수열을 찾는 문제 처음에는 어떻게 해야할 지 감이 안왔는데, 보통 이렇게 알고리즘이 감이 안오는 문제는 입력 크기를 줄이고 완전탐색으로 풀도록 유도하는 경우가 많다. 이 문제도 수열의 길이가 최대 10으로 -10 ~ 10 까지 숫자 10개를 모두 시도해보면서 풀 수 있다.그렇다고 정말 나이브하게 완탐으로가면 21^10 이라는 경우의 수를 체크해야 한다.하지만 모든 부분수열의 ai ~ aj 부호값을 모두 만족해야 하는점에서 경우의 수를 치다보면 체크할 경우의 수가 확 줄어든다는 것을..

https://www.acmicpc.net/problem/1166 이분탐색 심화 개념을 사용해야 하는 문제.. (나도 알고 싶지 않았다)문제 자체는 간단하다.어떤 정육면체 N개를 W*H*L 직육면체 안에 넣고자 할 때, 이 정육면체의 한변의 길이를 최대한 늘리는 것이 문제 풀이이다.단순히 직육면체와 같은 부피를 갖는 N개 정육면체에 대한 한변 길이 구하기로는 풀 수 없다. 극단적으로 얇은데 큰 직육면체를 생각하면 된다. (1 x 10억 x 10억) 내가 맨 처음 생각한 풀이는 (알고보니 정해였지만) 이분탐색이다.주어진 직육면체의 세 변 중 가장 짧은 변의 길이를 반씩 나누면서 그 변의 길이를 정육면체의 변의 길이로 할 때 N개 이상의 상자를 담을 수 있는지 계산하는 것이다. s = 0, e = min(W..

https://www.acmicpc.net/problem/4315 재미있는 트리 연습 문제아이디어 + 구현 모두 깐깐한 문제였다.각 노드가 갖고 있는 구슬 개수가 모두 1개가 되도록 할 때 구슬을 옮기는 최소 횟수를 구하는 문제이다. 내가 생각한 풀이 흐름은 다음과 같다. 1. 전체 트리를 DFS 돌면서 현재 자신을 root 로 하는 서브트리에 대해 이 서브 트리가 가지고 있는 모든 구슬의 개수, 필요한 구슬의 개수를 구한다. 만약 가지고 있는 구슬이 필요한 구슬보다 많다면, 그 차이를 return 하여 부모 노드로 여분 구슬을 넘긴다. DFS 실행이 끝나면 모든 노드는 자신을 루트로 하는 서브트리 모두를 채울 수 있도록 딱 맞게 구슬을 갖고 있거나, 모자라거나 둘 중 하나의 상태가 된다. 2. 두번째로..

https://www.acmicpc.net/problem/4436 가볍게 브론즈 문제를 하나 풀어봤다. (솔브드 마라톤 시스템 추천 문제)모든 k 값을 1부터 다 시도해보면서 브루트포스로 구현하면 되는 문제다. 근데 푸는데 생각보다 시간이 오래 걸렸다.. 그 이유는 set 연산자를 착각해서 그렇다.나는 s.union() 메서드가 기존 집합에 자동적으로 더해주는 줄 알았는데, 기존 집합이 변하지 않고, 새로운 합집합을 반환한다는 점을 프린트로 찍으면서 디버깅하느라 10분정도 걸려서 푼 것 같다.. 이 문제 덕분에 파이썬 집합 연산은 새로운 집합을 반환하므로 기존 집합을 덮어써야 한다는 것을 깨달을 수 있었다. import sysinput = sys.stdin.readlinewhile True: try..

https://www.acmicpc.net/problem/11437 워냑 유명한 유형이다보니 (나도 풀어보지는 않았지만 이 유형에 대해서 들어봤었다.) 정형화된 알고리즘이 있을 것 같은데, 우선 스스로의 고민으로 먼저 풀어보기로 했다. 어떤 트리가 주어질 때, 임의의 두 노드에 대해 그 두 노드의 최소 공통 조상 노드를 찾는 것이 문제의 요구사항이다.이때 트리의 루트는 1번 노드이다.(나는 이 조건을 못 보고 어떤 루트로 잡든 성립하는 문제인가보다~ 하고 1번 노드를 루트로 잡고 풀었는데, 생각해보면 두 노드 중에 한 노드를 매번 루트로 잡으면 그 노드가 최소 공통 조상이 되어버리니 루트는 정해져있어야 의미있는 문제였다.) 처음에는 특정 노드에서부터 루트를 향해 올라가면서 공통 조상 노드를 찾는 방법을 ..

https://www.acmicpc.net/problem/14442 자바로 한번 구현해봤더니 파이썬의 편리함을 다시 한번 깨닫게 해준 문제... 문제 풀이는 간단하다.(i, j) 위치에 k번의 벽 부수기 횟수가 남은 상태로 도착했을 때, 그때의 최단 이동 경로를 다 저장하면된다.최악의 경우 1000*1000*10 = 1000만 칸의 배열을 채워야 하는데, 2초 시간 제한과 512MB 의 메모리 제한이라면 충분히 채울 수 있다. 만약 이동하려는 칸이 벽이라면 현재 칸에서 남은 벽 부수기 횟수를 1 감소시켜서 이동시키고, 이동하려는 칸이 벽이 아니라면 남은 횟수를 그대로 가져가면서 이동하면 된다. import java.io.BufferedReader;import java.io.IOException;impor..

https://www.acmicpc.net/problem/1949 지금까지 푼 트리 DP 문제와 같은 방법으로 풀면 된다.다만 3번 조건이 애매하게 마음 속에 걸렸다.뭔가 직감적으로는 내 풀이가 3번 조건을 자연스럽게 만족하는 정답을 도출할 것 같은데 확실하진 않은 느낌.. 우선 풀이는 다음과 같다.현재 노드를 루트로 하는 서브트리에 대해 현재 노드가 우수마을인 경우, 최적해와 우수마을이 아닌 경우 최적해를 저장하는 DP 테이블을 짜고 다음과 같이 점화식을 세운다. dp[node][우수마을o] = sum( dp[child][우수마을x], ... )dp[node][우수마을x] = sum( max(dp[child][우수마을o], dp[child][우수마을x]), ... ) 부모 노드가 우수마을이 아닌 경우,..

https://www.acmicpc.net/problem/2533 트리 DP 문제DP 테이블을 다음과 같이 정의한다. dp[i][j] = i 번째 노드가 루트인 트리에 대해 이 노드가 얼리어답터 인지 (j = 0) 아닌지 (j = 1) 에 따른 그 트리에서의 얼리어답터 최소 수 점화식은 다음과 같이 쓸 수 있다. dp[i][0] = i 번째 노드가 루트인 트리에 대해 이 노드가 얼리어답터인 경우, 모든 자식노드는 얼리어답터여도 되고, 아니어도 된다. 두 경우를 모두 구해서 최소 값을 취한다. 따라서 sum( min( dp[k][0], dp[k][1] ) ) + 1, ( k 는 직접 연결된 자식 노드들의 번호 ) dp[i][1] = i 번째 노드가 루트인 트리에 대해, 이 노드가 얼리어답터가 아닌 경우, ..