King of the Jungle Lion

문제링크:11280번: 2-SAT - 3 (acmicpc.net), 11281번: 2-SAT - 4 (acmicpc.net) 11281번: 2-SAT - 4 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 이 문제는 2-CNF식을 True로 만들기 위한 xi값들이 가능 한지, 그리고 가능 하다면 xi값들을 정하는 문제이다. 2-CNF식이란 &를 and, |를 or이라고 했을 때 식의 구조가 (x1|x2)&(x4|x3)&(xi|xj) 이렇게 임의의 xi들이 괄호 안에서는 or, 괄..

문제링크: 2150번: Strongly Connected Component (acmicpc.net) 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 이 문제는 그래프가 주었을 때 그래프 내의 강한 연결 요소, SCC (Strongly Connected Component)를 구하는 문제이다. 여기서 SCC란 두 정점 u, v가 있을 때 서로 간에 방문 할 수 있는 경로가 있을 때, 그리고 그러한 정점들의 최대 부분집합을 뜻한다. u->v ..

문제링크:16287번: Parcel (acmicpc.net) 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 이 문제는 5000개의 중복되지 않는 무게를 가진 원소를 4개 골라서 총 합이 w무게로 맞출 수 있는 지 없는지를 구하는 문제이다. 만약 그냥 계산한다면 시간복잡도가 5000C4로 약 O(N^4) = 5000^4로 매우 커질 것이다. 이 문제는 반드시 꼭 4개를 고르는 것에 초점을 두어 2개, 2개로 나누어 두는 경우를 생각하여 중간에서 만나기 알고리즘과 ..

문제링크: 1708번: 볼록 껍질 (acmicpc.net) 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 이 문제는 N개의 점이 주어졌을 때 N개의 점을 모두 포함할 수 있는 볼록 껍질 (convex hull) 의 각 꼭지점들을 구하는 문제이다. 볼록 껍질이란 이 문제에서 설명하는 그대로 점들 중 일부 점들을 이용하여 볼록 다각형을 만드는데, 그 볼록 다각형이 모든 점을 포함할 수 있으면 볼록 껍질이 된다. 이 문제를 처음 봤을때 선분 교차 판정 때 이용한 벡터의 외적을 각 선분마다 사용..

문제링크:14942번: 개미 (acmicpc.net) 14942번: 개미 자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너 www.acmicpc.net 이 문제는 루트가 1인 n개의 노드를 가진 트리가 있을 때, 각 노드에서 무조건 루트 방향(조상노드방향) 으로 이동한다고 했을 때, 그리고 갈 수 있는 거리가 한정되어 있을 때 출발 해서 도달할 수 있는 최대 조상 노드를 구하는 문제이다. 이 문제는 얼마 전에 푼 LCA문제에서 이진 탐색을 이용한 희소 배열을 이용해서 조상 노드로 이동하는 원리를 사용했다. 먼저 dfs를 통해 루트(노드0)부터 탐색..

문제링크:5670번: 휴대폰 자판 (acmicpc.net) 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 이 문제는 휴대폰의 자동완성 기능에 대한 문제이다. 만약 전체 단어 사전에 hello, hell, heaven 이렇게 세 단어가 있다면 우리가 h를 입력했을때 세 단어 모두 다음에 e가 오므로 he 까지 자동 완성된다. 그리고 만약 다음에 a를 치면 hea로 시작하는 단어는 heaven이므로 heaven이 완성된다. 만약 l을쳐서 hel을 완성하면 hello와 hell이 겹치는 hell까지 완성된다. 만약 여..

문제링크:14725번: 개미굴 (acmicpc.net) 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 문제 원리는 간단하게 DFS를 이용하여 각 간선들이 입력되면 이를 바탕으로 그래프를 만들어 문제에 주어진 대로 출력하는 것이지만 각 노드들이 문자열로 이루어져 있고, 중복되는 노드들이 있어서 문자열에 익숙하지 않아 어려웠다. import sys N=int(sys.stdin.readline().rstrip()) tree=dict() for _ in range(N): inputs=list(sys.s..

문제링크:1761번: 정점들의 거리 (acmicpc.net) 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 이 문제는 정점 N개와 N개를 모두 이어줄 수 있는 가중치가 있는 N-1개의 간선들이 주어 질 때, 두 노드 사이의 거리를 얻는 문제이다. 문제는 정점의 개수인 N이 40,000개까지 주어질 수 있고, 거리를 얻어야 하는 두 노드 케이스가 10,000개까지 주어진다. 최소 공통 조상, LCA 알고리즘과 이분탐색을 연계하여 사용하면 두 노드 사이의 거리를 O(logN)의 시간 복잡도로 구할 수 ..

문제링크:1533번: 길의 개수 (acmicpc.net) 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 이 문제는 노드와 간선들이 인접행렬로 주어졌을 때, 시작노드로부터 도착 노드까지의 경로 중 시간이 T와 정확히 일치하는 경로들의 개수를 구하는 문제이다. 먼저 기존에 가중치가 없는 간선들이 인접행렬로 주어졌을 때에, 행렬의 곱을 이용해 경로의 개수를 구할 수 있었다. 만약 0,1,2의 노드와 가중치가 없는 간선들이 인접행렬로 다음과 같이 주어지면 각 matrix[i][j]는 i..

문제링크:2618번: 경찰차 (acmicpc.net) 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 이 문제의 조건은 먼저 경찰차가 두대 있는데 초기에 한대는 (1,1) 다른 한대는 (N,N) 좌표에 위치한다. 앞으로 W개의 사건들이 벌어지는데, 각 사건마다 사건의 좌표(X,Y) 가 주어진다. 경찰차 한대가 사건을 처리하러 가야 하고, 출동한 경찰차는 그 다음 사건까지 그 사건의 위치에서 대기한다. 여기서 경찰차가 움직인 거리는 만약 (1,1)의 경찰차가 간다면 |X-1|+|Y-1| ..