Simple Explain

#1167번 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름을 구하는 문제이다. 대충 거리의 총합정도는 구하겠는데 어떻게 최대거리를 갖는 노드를 찾는지 도저히 이해가 되지 않았다. 다음 블로그를 참고했다. https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름..

#13549 숨바꼭질3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 신기한 문제였다. BFS를 공부하다가 만난 문제이지만 사실 BFS를 통한 풀이가 온전한 풀이가 아니라는것. 문제는 점프라는 행위에 있다. 다른 행위와는 달리 점프에 소요되는 비용은 0이다. 그래프 내에서 가중치가 0이라는 말이다. 모든 엣지의 가중치가 동일할 때 정확한 수행능력을 보여주는게 BFS알고리즘이다. 그렇기 때문에 가중치가 다른 위..

#16947번 서울 지하철 2호선 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 테스트케이스 통과까지는 성공했지만 시간초과가 났다. import sys sys.setrecursionlimit(10**9) N = int(input()) matrix = [[] for _ in range(N+1)] for i in range(N): prev, to = map(int, input().split()) matrix[prev]...

#2667번 단지 번호 붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net N = int(input()) mat = [[int(x) for x in input()] for _ in range(N)] visited = [[False for _ in range(N)] for __ in range(N)] answer = [] tmp = 0 def search(r, c): global tmp visited[r][c] = True state = mat..

그래프 문제를 푸는 날이었다. 먼저 풀었던 아이는 #1260번 DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 무난하게 해결! 개념을 확립하는데 큰 도움이 됐다! DFS는 재귀, BFS는 Queue를 통해 해결하는게 가장 좋은 것 같아. 간혹 BFS로 해결하는게 유리한 문제에서 DFS를 사용하면 recursionError이 발생하는데, 파이썬에서 설정한 재귀의 한계깊이에 도달하면 발생하는 문..

#1248번 맞춰봐 https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 www.acmicpc.net 이름부터가 재수없었던 문제이다. 내가 멍청해서인지 문제 이해부터 잘 되지 않았다. 위의 스토리는 그냥 시간끌기 및 혼동용이고 밑에 문단만 읽으면 된다. 4 -+0++++--+ 다음과 같은 값이 들어올 경우 위 값을 matrix로 변환할 수 있다 이 2차원 리스트의 의미는 다음과 같다. 첫 입력으로 받은 숫자만큼의 길이를 가진 수열을 구하는게 정답인데 (위의 경우는 4, _ _..

#2133번 타일채우기 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 이번의 타일은 3줄짜리다!.. 여러 점화식을 고민해봤지만 결론은 다음과 같다. n==2일 때는 3가지 경우가 가능하다. 대충 이런 느낌으로 세 개. 문제는 그 다음부터인데 일단 홀수 줄의 타일의 경우에는 불가능하다 -> 0 짝수 일 때만 가능하기 때문에 다음 케이스는 dp[4]가 되는데 이 때는 dp[2]에서 구해놓은 3가지 케이스 중 두개를 중복을 허용해서 골라주면 된다. -> 3*3 = 9 단, 4줄의 타일일 경우에는 새로운 모양이 생겨나는데 바로 이런 형태이다. 총 2가지 경우가..

#9465번 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 기존의 DP문제와는 약간 다른 모습을 보여서 신기했다. 기존의 DP는 특정 조건에 맞춰서 값을 새로 추가해나가는 형태였는데 이 문제는 주어진 값들 (리스트)을 갱신해 나가는 형태로 진행하는게 효율적이었다. 풀이 1) 스티커를 떼면 상하좌우 스티커를 사용할 수 없다. 2) 그런 상황에서의 스티커 점수의 최댓값 상하좌우에 위치한 값을 선택할 수가 없다 -> 대각선 상에 ..

#2089번 https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net -2 진수로 변환하는 문제이다. 기본적인 2진법은 자리수 마다 2의 제곱수를 해주는데 -2진법은 -2의 제곱수를 자리해주는 방식이다. 때문에 1,3,5,7 번째 자리 즉 홀수번 째 자리에서는 양수가 나오고, 짝수번 째 자리에서는 음수가 나온다. 이를 잘 조합해서 변환해주면 된다. 처음엔 ..

#6588 골드바흐의 추측 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 정말 피곤한 문제였다. 소수는 에라토스테네스의 체를 이용해서 구해야한다. 이건 매번 이해만 하고 외워지지가 않는다. 멍청한걸까? bool_prime = [False, False] + [True]*(1000000-1) prime = [] for i in range(2, 1000000 + 1): if bool_prime[i]: prime.append(..