[이코테] 문제1 - 음료수 얼려 먹기 풀이 시간: 30분 이내 1) 문제 해결 아이디어 이 문제는 DFS 혹은 BFS로 해결 가능하다. 특정 지점에서 DFS/BFS를 수행하여 이동 가능한 모든 지점에 대해 방문 처리를 한다. dfs 문제는 재귀 함수를 이용하여 해결한다. 재귀 함수의 종료 조건은 해당 좌표가 범위를 벗어났을 경우다. 현재 좌표를 아직 방문하지 않았다면 방문 처리를 하고 상하좌우에 해당하는 좌표를 매개변수로 하여 dfs를 호출한다. 1. 해당 지점이 아직 방문하지 않은 곳이라면 방문 처리 2. 상하좌우 지점 재귀 호출로 탐색 2) 소스코드 n, m = map(int, input().split()) # 세로, 가로 graph = [list(map(int, input())) for _ in ..
[이코테] BFS 예제 풀이 시간: 10분 이내 1) 문제 해결 아이디어 BFS 예제 문제로 책 147p 참고 BFS 구현을 위해 큐(deque 라이브러리) 이용 2) 소스코드 from collections import deque # BFS 메서드 def bfs(graph, start, visited): # 큐 구현을 위한 deque 라이브러리 사용 queue = deque([start]) # 현재 노드 방문 처리 visited[start] = True # 큐가 빌 때가지 반복 while queue: # 큐에서 하나의 원소를 뽑아 출력 v = queue.popleft() print(v, end=' ') # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입 for i in graph[v]: if..
[이코테] DFS 예제 풀이 시간: 5~7분 이내 1) 문제 해결 아이디어 DFS 예제 문제로 책 142p 참고 DFS 구현을 위해 재귀함수 이용 2) 소스코드 # DFS 메서드 def dfs(graph, v, visited): # 현재 노드 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드 재귀 호출 for i in graph[v]: # 인접 노드가 방문되지 않았다면 if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보(2차원 리스트) graph = [ [], # 노드 번호가 1번부터 시작하므로 비워두는게 좋음 [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7..
[백준] 2873번 - 롤러코스터 풀이 시간: 6~7 시간 1) 문제 해결 아이디어 아이디어를 떠올리는데 어려움을 겪은 문제다. 케이스를 분류하고 일반화하기가 까다로운 문제로 지금까지 풀었던 그리디 문제 중에는 제일 어려운 문제인 것 같다. 특히나 r, c가 모두 짝수인 경우가 구현하기 가장 까다롭기 때문에 푸는데 실패를 계속 겪고 정답이 되기까지 시간이 오래걸렸다. 각 칸은 한 번만 방문할 수 있고 지나간 칸의 합이 가장 최대가 되는경로를 출력하는 문제다. 지나간 칸의 합이 가장 최대가 되기 위해서는 최대한 많은 칸을 지나가야한다. 이 문제는 r, c가 짝수인지 홀수인지에 따라서 케이스를 분리하는 것이 중요 포인트다. 3번째 케이스같은 경우는 제외할 1칸을 어떻게 설정할지를 떠올리는 것이 중요하다. 그..
[백준] 12845번 - 모두의 마블 풀이 시간: 30~35분 이내 (풀이1) 문제 그대로 구현한 방법 1) 문제 해결 아이디어 아이디어를 떠올리는 것은 어렵지 않았으나 계속 런타임 에러(TypeError)가 났다. 주어진 테스트 케이스에서는 값이 잘 나왔으나 다른 테스트 케이스의 경우 제대로 된 값이 오류가 발생했다. 1. 두 카드는 인접한 카드 2. 합성한 카드 A의 레벨은 변하지 않음 카드를 합성할 때마다 카드A, B 레벨의 합만큼 골드를 받음 1. 레벨의 최댓값(max)를 기준으로 계속 오른쪽으로 합성하기(최댓값의 인덱스가 맨 마지막이 될 때까지) 2. 최댓값(max)기준으로 계속 왼쪽으로 합성하기(남은 카드가 1개가 될 때까지) 첫번째 오류. 리스트 값 삭제 후 리스트 길이에 대한 처리 리스트 ..
[백준] 11256번 - 사탕 풀이 시간: 10~15분 이내 1) 문제 해결 아이디어 문제 설명대로 코드를 구현하기만 하면 풀 수 있는 쉬운 문제였다. 박스 크기(r, c)에 담을 수 있는 최대 사탕 개수는 (r * c)이다. 최소한의 상자 개수는 박스 부피(volume)가 큰 상자부터 사탕을 담는 것이다. 그래서 입력받은 상자(box)들을 부피 기준으로 내림차순 정렬해주었다. 2) 소스코드 t = int(input()) # 테스트 케이스 수 for i in range(t): j, n = map(int,input().split()) # 사탕 개수, 상자 개수 box = [] # n개의 박스 크기 res = 0 # 박스 개수 for _ in range(n): box.append(list(map(int, i..
[백준] 16435번 - 스네이크버드 풀이 시간: 10분 이내 1) 문제 해결 아이디어 문제에 나온대로 구현만 하면 되는 쉽게 풀 수 있는 문제다. 높이가 작은 것부터 검사해야 많은 과일을 먹어 길이가 최대가 될 수 있으므로 과일 높이(h)를 오름차순 정렬한다. for문에서 과일 높이가 스네이크 버드 길이보다 커지면 더이상 과일을 먹을 수 없기 때문에 break로 탈출한다. 이미 앞에서 오름차순 정렬이 된 상태이기 때문에 뒤에 값은 더 검사해볼 필요도 없다. 2) 소스코드 n, l = map(int, input().split()) # 과일 개수, 초기 길이 h = list(map(int, input().split())) # 과일 높이(n개) h.sort() # 과일높이 오름차순 정렬 length = l ..
[백준] 1744번 - 수 묶기 (풀이1) 양수, 음수 리스트로 입력받아 계산하기 1) 문제 해결 아이디어 여기서는 처음부터 양수, 음수 2개의 리스트로 나누어 입력을 받고 이후에 계산을 하는 방식이다. 아이디어는 쉽게 떠올렸으나 주어진 테스트 케이스에서는 결과값이 제대로 나왔으나 나머지 테스트 케이스에 대해 오답이 나와 설계 오류를 찾는데 시간이 조금 걸렸다. 여기서 묶는 다는 것은 두 값을 곱한다는 뜻이고 묶지 않는다는 것은 두 값을 더한다는 뜻이다. 1. 양수끼리 묶기(양수는 내림차순 정렬하여 순서대로 양수끼리 곱셈) 2. 음수끼리 묶기(음수는 오름차순 정렬하여 순서대로 음수끼리 곱셈) 3. 0은 음수와 묶기(0은 음수와 곱셈) 4. 양수, 음수 묶지 않기(양수와 음수는 덧셈) 첫번째 오류. 1에 ..
