동적 프로그래밍(Dynamic Programming)을 사용하여 0과 1로 이루어진 특정 수열을 생성하고, 주어진 수열의 각 숫자들 중 0과 1의 개수를 구할 수 있다. 피보나치 n에서 0 호출횟수 = (피보나치 n-1에서 0 호출횟수) + (피보나치 n-2에서 0 호출 횟수)피보나치 n에서 1 호출횟수 = (피보나치 n-1에서 1 호출횟수) + (피보나치 n-2에서 1 호출 횟수)이므로 점화식count_zero[i] = count_zero[i-1] + count_zero[i-2]count_one[i] = count_one[i-1] + count_one[i-2]이런 점화식을 생각할 수 있다. t = int(input()) # 테스트 케이스의 수 입력def count_ways(n): count_z..
⚙️ Problem Solving
그래프 탐색 문제로dfs, bfs 둘다 사용이 가능하여 다양한 풀이가 가능한 문제다. DFS: dictionary(인접리스트), 재귀 사용n = int(input()) # 컴퓨터의 수 (1~100 정수)m = int(input()) # 직접 연결되어있는 컴퓨터 쌍의 수graph = {i: [] for i in range(1, n + 1)} # 각 컴퓨터와 이어진 컴퓨터들을 저장할 그래프 초기화for _ in range(m): a, b = map(int, input().split()) # 직접 연결된 컴퓨터 쌍을 입력받음 graph[a].append(b) # a와 b를 연결하여 그래프에 추가 graph[b].append(a) # b와 a를 연결하여 그래프에 추가visited = ..
풀이 1: DP이 문제를 위한 가장 효율적인 방법은 DP를 사용하는 것이다. 초기값초기값 dp[1] = 1, dp[2] = 2, dp[3] = 4(dp[2]는 1+1, 2로 2가지, p[3]은 1+1+1, 1+2, 2+1, 3으로 4가지) 점화식4일 때 dp[3]+1, dp[2]+2, dp[1]+3와 같이 구할 수 있다. --> n은 dp[n-1]+3, dp[n-2]+2, dp[n-3]+3--> 방법의 수 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 1, 2, 3의 합으로 나타내는 방법의 수에서 한 번 계산한 값을 재사용함으로써 중복 계산을 방지하고, 시간 복잡도를 줄일 수 있다.def count_ways(n): # n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 저장..
간단한 그리디 문제!입력 받는 것만 안 헷갈리면 될 것 같다. 11399번: ATMn = int(input())time = list(map(int, input().split()))time = sorted(time)lst = []cost = 0for i in range(len(time)): cost += time[i] lst.append(cost)print(sum(lst)) 11047번: 동전 0n, k = map(int, input().split())lst = [int(input()) for _ in range(n)]lst = sorted(lst, reverse=True)total = 0for i in range(n): if lst[i] lst[i] = 안 붙여서 처음에 틀렸다 ^^....
1. n, m, v 입력 받기 (띄어쓰기 입력)n, m, v = map(int, input().split())N(정점수), M(간선수), V(탐색 시작할 정점 번호) 2. 그래프 입력 받기 (노드 연결 정보) - 인접 행렬graph = [[0] * (n+1) for _ in range(n+1)]for i in range(m): a, b = map(int, input().split()) graph[a][b] = graph[b][a] = 1 정점 번호와 인덱스 일치시키기 위해 n+1로 초기화무방향 그래프이므로 graph[a][b] = graph[b][a] = 1 ** 그래프 출력하기def print_graph(graph): for row in graph[1:]: # 0번째 행과 열은 사용하..
subproblem 중복, 반복연산 많음 -> DP 풀이1 (Bottom-up)n = int(input())dp = [0] * (n+1)for i in range(2, n+1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i//3]+1, dp[i]) if i % 2 == 0: dp[i] = min(dp[i//2]+1, dp[i]) print(i, ": ", dp[i])if n 풀이2 (Top-Down) - Recursion Errordef min_operations(n, dp): if n 0: # 이미 계산된 값이 있다면 그 값을 반환 return dp[n] dp[n] = mi..
첫 번째 원소는 내림차순으로, 두 번째 원소는 오름차순으로, 세 번째 원소는 내림차순으로 정렬하는 예제 # 2차원 리스트 생성 two_dim_list = [ [3, 6, 9], [2, 5, 8], [3, 6, 7], [1, 4, 7], [2, 5, 10] ] # 우선순위에 따라 정렬하는 함수 정의 sorted_list = sorted(two_dim_list, key=lambda x: (-x[0], x[1], -x[2])) # 결과 출력 for item in sorted_list: print(item) 관련 문제 ) 백준 10825. 국영수 n = int(input()) students = [] for _ in range(n): name, kor, eng, math = input().split() stud..
퀴즈다음 코드들을 사용하는 상황을 구분해보자.a = [list(map(int, input())) for _ in range(n)]a = [list(map(int, input().split())) for _ in range(n)]std_list = [input().split() for _ in range(n)]for _ in range(n): name, kor, eng, math = input().split() students.append((name, int(kor), int(eng), int(math)))a, *b = map(int, input().split()) 정답a = [list(map(int, input())) for _ in range(n)]-> 정수로 변환해야되고, 입력 값 띄어..
table = copy ? table = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] copy = table 위 코드는 어떻게 동작하게 될까? `copy = table`라는 코드는 실제로 2차원 배열 `table`의 참조를 `copy`라는 변수에 할당하는 것이다. 새로운 2차원 배열을 생성하는 것이 아니라, `table`과 `copy`가 같은 메모리 주소를 참조하게 된다. 즉, 하나의 리스트를 두 개의 이름으로 가리키는 것이다. 이는 파이썬에서 객체의 참조를 다룰 때 일반적인 동작 방식이다. table = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] copy = table table[0][0] = 100 print(copy) # ..
문제 요약 고속도로를 이동하는 차량의 경로 routes 가 매개변수, 모든 차량이 한번은 단속용 카메라를 만나려면 최소 몇 대의 카메라 설치해야하는지 return 차량의 대수는 1대 이상 10,000대 이하 routes에는 차량의 이동 경로 포함, routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점 진입/진출 지점에서도 카메라를 만난 것 return routes return [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 return 5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다. 15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다. 나의 풀이 (..
