This is Mi

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 피보나치 수는 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번: 부녀회장이 될테야 첫 번째 줄에 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..

교재에 서술된 정답 코드가 아닌, 제가 직접 작성한 코드입니다. 최소 이동 칸을 구하기 위한 것이므로 오른쪽 이동과 아래쪽 이동만 고려하면 된다. 만약 어떤 칸의 오른쪽과 왼쪽에 모두 괴물이 있다면 해당 칸으론 더 이상 이동할 수 없으므로, count에서 -1 해야 한다. 다만 마지막 칸의 경우에는 j + 1 < m과 i + 1 < n 때문에 flag가 True라서 count - 1 되므로, return 시 count에 1을 더해주어야 한다. from collections import deque def solution(x, y): graph[x][y] = 0 queue = deque([(x, y)]) count = 0 while queue: i, j = queue.popleft() count += 1 f..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 접근 방식 주차장에 빈 공간이 있으면, 가장 번호가 공간에 주차시킨다. 즉, 현재 주차 공간의 현황을 알려주는 리스트가 필요하다고 판단하였다. 비어 있으면 0, 주차되어 있다면 0이 아닌 다른 값이 저장된 리스트. 리스트의 index(x) 메서드는 리스트 내에 x 값을 원소가 여러 개라도 첫 번째로 발견된 x의 인덱스를 반환하기 때문에 가장 작은 번호 공간에 주차시키는 건 어렵지 않게 처리할 수 있다. 주차 공간이 없다면 대기한다. 이를 위한 waiting 리스트가 필요하다. FIFO 방식이므로, 빈 공간이 발생하면 pop(0)을 하여 가장 첫 번째 원소를 ..