[백준] 1260번 DFS와 BFS 파이썬 정답 코드
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. 문제 내용 2. 접근 방식 문제 이름에서 사용해야 할 알고리즘을 알려주고 있기 때문에 별다른 접근 방식은 없다. 3. 정답 코드 from collections import deque def dfs(n): print(n, end=' ') visited[n] = True for i in graph[n]: if not visited[i]: dfs(i) def bfs(n): visited[n] = True queue = deq..
[백준] 2606번 바이러스 파이썬 정답 코드
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1. 문제 내용 2. 접근 방식 1번 컴퓨터와 연결된 노드들을 탐색한다. 깊이 우선 탐색과 너비 우선 탐색 모두 사용할 수 있다. 그러나 너비 우선 탐색 코드가 가장 먼저 떠올라서 너비 우선 탐색으로 코드를 작성하였다. 3. 정답 코드 from collections import deque def bfs(v): visited[v] = True queue = deque([v]) while queue: n = queue.popleft() for i in data[n]: i..
[백준] 2748번 피보나치 수 2 파이썬 정답 코드
2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 1. 문제 내용 2. 접근 방식 다이나믹 프로그래밍(DP) 피보나치를 구하는 가장 일반적인 재귀 함수 방식은 시간 복잡도가 O(2^n)이다. 이 문제에서 n은 90보다 작거나 같은 자연수이므로, 재귀 함수 방식으론 절대 풀 수가 없다. 따라서 작은 문제에서 큰 문제로 차근차근 답을 도출하는 다이나믹 프로그래밍의 상향식 방식을 따라 dp 테이블을 사용하여 피보나치 수를 구한다. 3. 정답 코드 n = int(input()) dp..
[백준] 2775번 부녀회장이 될테야 파이썬 정답 코드
2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 1. 문제 내용 2. 접근 방식 다이나믹 프로그래밍(DP) a층의 b호에 살려면 a-1층의 1호부터 b호까지의 사람 수 합만큼 데려야 살아야 한다. 예를 들면, 2층 3호에 사는 사람 수는 1층 1호 + 1층 2호 + 1층 3호 = 0층 1호 + ( 0층 1호 + 0층 2호) + ( 0층 1호 + 0층 2호 + 0층 3호)이다. 즉, ① 2층 3호라는 큰 문제를 작은 문제로 나눌 수 있으며 ② 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하다. (이것이 취업을 위한 코딩 테스트이다, p..