This is Mi

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번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 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)을 하여 가장 첫 번째 원소를 ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 접근 방식 겹치는 카드가 존재하는지 확인하기 위해 집합을 사용하자. 카드에 대한 정보 s를 문자열로 받고나면, 이것을 3개씩 끊어 [ 'S01', 'D02' ... ]처럼 리스트로 담을 것이다. 그리고 이것을 집합으로 만들어 리스트와 집합의 길이가 서로 다르면, 리스트 내에 중복 요소가 존재한다는 것이므로 ERROR를 출력한다. 무늬별 카드 개수는 딕셔너리를 사용하자. 기본적으로 모든 카드가 필요하다는 전제로 초기 딕셔너리의 모든 value는 13으로 설정한다. 이후 s를 3개씩 끊은 리스트를 순회하면서 각 무늬의 value 값을 -1한다. 단, 출력 순서는..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 수정 전과 후 버전이 있습니다. 아래쪽이 수정 후 버전으로, 최종 정답 코드입니다! 1. 수정 전 접근 방식 1,000,000이라는 큰 수 n이 소수인지 판별하는 가장 간단한 함수(아래 is_prime 메서드)로는 절대 문제를 해결하지 못한다. 따라서 더욱 효율적인 소수 판정법을 고민해야 했다. 에레토스테네스의 체 내가 기존에 알고 있는 소수 판정법은 2부터 루트 n까지의 소수로 나누어 보는 것이었다. 그러나 이 문제는 n이 1부터 100만까지이기 때문에 ① 2부터 루트 n까지의 '소수'들을 구하고 ② 그 소수들로 n을 나누는 과정에서 시간 초과가 날 것이 뻔했다..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 접근 방식 D가 11보다 클 때는 바로 d - 11, h - 11, m - 11을 하면 된다. 그러나 태혁이가 바람 맞은 날이 11일이라면, 바람 맞은 게 11시 전인지, 11시 이후인지를 따져야 한다. 만약 11일 11시에 바람 맞았다면, 정확히 몇 분에 바람 맞았는지 확인해야 한다. 2. 정답 코드 T = int(input()) for test_case in range(1, T + 1): d, h, m = map(int, input().split()) result = 0 if d > 11: dd = d - 11 dh = h - 11 dm = m - 11 ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 접근 방식 딕셔너리를 사용: key는 숫자 체계, value는 입력 데이터에서 key의 개수 count( ) 메서드를 통해 각 숫자의 개수를 세어 딕셔너리에 저장한다. 이후 출력은 숫자 * 딕셔너리[숫자](=개수)로 간단하게 처리한다. 2. 정답 코드 T = int(input()) for test_case in range(1, T + 1): t, length = input().split() data = input().split() numbers = [ "ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT..