Algorithm/Baekjoon

🗂️ 문제링크: https://www.acmicpc.net/problem/18352 💡 접근법인접 리스트를 통해 그래프를 구현하고, BFS를 사용하여 각각의 도시까지의 최단 거리를 distance 리스트에 저장한다. 현재 노드의 거리 값은 이전 노드의 거리 값 + 1이다.이후 K와 거리가 같은 도시를 출력하면 된다. 😎 내 코드import sysfrom collections import dequedef BFS(v): queue = deque() queue.append(v) visited[v] = True while queue: now_node = queue.popleft() for i in graph[now_node]: if not ..

🗂️ 문제링크: https://www.acmicpc.net/problem/10815 💡 접근법이분탐색 시 탐색 범위를 설정해야 한다. 해당 문제에서는 카드 리스트를 정렬하고, 카드 리스트 인덱스의 최솟값(0)과 최댓값(len(card_list)-1)을 low와 high로 각각 지정한다. mid의 값을 변경하며 탐색한다. 이때 카드 리스트에서 mid 인덱스에 해당하는 값보다 상근이가 가지고 있는 숫자가 작으면 mid 값을 줄여야하므로 high = mid - 1로 설정한다. 반대의 경우엔 mid 값을 키워야하므로 low = mid + 1로 설정한다. 만약 카드 리스트에서 mid 인덱스에 해당하는 값이 상근이가 가지고 있는 숫자와 같다면 1을 저장한다. 😎 내 코드import sysN = int(sys...

🗂️ 문제링크: https://www.acmicpc.net/problem/11726 💡 접근법n=1일 때 직사각형을 채우는 방법은 1가지다.n=2일 때 직사각형을 채우는 방법은 2가지다.n=3일 때 직사각형을 채우는 방법은 3가지다.n=4일 때 직사각형을 채우는 방법은 5가지다.n=5일 때 직사각형을 채우는 방법은 8가지다. 이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-2] (N>2)이다. 😎 내 코드import sysn = int(sys.stdin.readline())dp = [0] * 1001dp[1] = 1dp[2] = 2for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2]print(dp[n]%10007) ✅ 정답 확인

🗂️ 문제링크: https://www.acmicpc.net/problem/1654 💡 접근법“N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.”라는 문제 조건에 따라 이분탐색의 기준을 필요한 랜선 개수 이상인지 이하인지 따라 범위를 좁혀나간다. 따라서 만들 수 있는 랜선의 수가 N개일 때 종료조건을 걸지 않고 계속해서 범위를 좁혀나가면서 최대의 랜선 길이를 구한다. 더이상 탐색 범위가 좁혀지지 않을때 high 값이 가장 긴 랜선의 길이가 되어 출력된다. 😎 내 코드import sysK, N = map(int, sys.stdin.readline().split())line = [int(sys.stdin.readline()) for _ in range(K)]def cal_line_num(heigh..

🗂️ 문제링크: https://www.acmicpc.net/problem/2805 💡 접근법N과 M의 범위가 크기 때문에 모든 경우의 수를 계산할 경우 시간초과가 발생한다. 절단 높이를 작게하면 가져가는 나무의 길이가 크고, 절단 높이를 크게하면 가져가는 나무 길이기 작다.이를 이용하여 절단 높이를 기준으로 이분 탐색을 수행한다. 또한 절단 높이를 최대로 하여 필요한 만큼의 나무를 가져가므로, 나무의 길이가 딱 떨어지지 않는 경우를 생각해야 한다. 이 경우엔 high(mid-1) 값을 출력하면 필요한 만큼 나무를 가져가면서 최대로 하는 절단 높이를 구할 수있다. 😎 내 코드import sysN, M = map(int, sys.stdin.readline().split())tree = list(map(..

🗂️ 문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 💡 접근법 1을 만드는 방법은 1가지이고, 2를 만드는 방법은 (1+1), (2)로 2가지이고, 3을 만드는 방법은 (1+1+1), (2+1)*2, (3)으로 4가지이고, 4를 만드는 방법은 (1+1+1+1), (1+1+2)*3, (1+3)*2, (2+2)로 7가지이고, 5를 만드는 방법은 (1+1+1+1+1), (1+1+1+2)*4, (1+2+2)*3, (3+1+1)*3, (3+2)*2로 13가지이다. 이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-2] +..

🗂️ 문제 링크: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 💡 접근법 계단을 어떻게 올라갈까?가 아니라 계단을 어떻게 올라왔을까? 라는 관점에서 접근해야 한다. n번째 계단에 올라오기 위해서는 두 가지 경우가 있다. n-1번째 계단으로 오는 경우와 n-2번째 계단으로 오는 경우이다. n-1번째 계단으로 오는 경우에는 dp[n] = dp[n-3] + stairs[n-1] + stairs[n] 이다. n-2번째 계단으로 오는 경우에는 dp[n] = dp..

🗂️ 문제 링크: https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 💡 접근법 DP로 풀 수 있는지 먼저 확인한다. 부분 문제가 반복적으로 나타나야 한다. 부분 문제의 최적 결과를 사용하여 전체 문제의 최적 결과를 낼 수 있다. DP 테이블을 초기화한다. 조건에 맞는 점화식을 구한다. 😎 내 코드 import sys def fib_recur(n): global recur_cnt if n == 1 or n == 2: recur_cnt..