주어진 삼각형 그림을 보면, 작은 삼각형의 합으로 다음 삼각형이 채워진다.-> DP 주어진 그림을 그려보며 생각해보면, 점화식을 어렵지 않게 찾을 수 있다.N12345678P(N)11122345P(8) = P(7) + P(3)P(7) = P(6) + P(2)P(6) = P(5) + P(1-> P(N) = P(N-1) + P(N-5)이다. 풀이dp = [0] * 101dp[1] = dp[2] = dp[3] = 1dp[4] = dp[5] = 2for i in range(6, 101): dp[i] = dp[i-1] + dp[i-5]t = int(input()) # 테스트 케이스 개수for _ in range(t): n = int(input()) print(dp[n])
⚙️ Problem Solving
방향 없는 그래프 주어짐 -> 연결 요소(connected component) 개수 구하는 프로그램 아이디어그래프 탐색 (DFS/BFS)방문 못한 노드 하나라도 있다면 카운트 증가하고그 방문 못한 노드 (false 노드)에서 시작해서 다시 그래프 탐색false 노드 없을 때까지 그래프 탐색 반복 풀이 - DFS 사용import sysinput = sys.stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]for _ in range(M): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u)visited = [False] * (N+..
문제 요약수빈 현재 위치 N, 동생 현재 위치 K, 0부터 100,000 까지의 정수수빈이가 동생을 찾을 수 있는 가장 빠른 시간 구하기.수빈이가 이동할 수 있는 건 3가지 : X-1, X+1, 2*X 풀이시작 노드에 연결된 노드는 3개, 각 노드에서 1초가 지날 때마다 하나씩 이동하다가,목표 노드에 도착하면 걸린 시간 리턴-> BFS로 풀이할 수 있다 def bfs(n, k): if n == k: # 같다면 걸린 시간 0 return 0 visited = [False] * 100001 # 입력 값 범위보다 크게 queue = deque([(n, 0)]) # n에는 현재 노드 위치, 0에는 걸린 시간 저장 while queue: cur, time = queu..
문제 요약n * m 사이즈 토마토 보관 상자익은 토마토 인접한 곳에 있는 건 영향 받아 익게 됨.창고에 보관한 토마토들이 최소 며칠 지나면 다 익게 되는지!단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다. M,N은 2부터 10001은 익은 토마토, 0은 안 익은 토마토, -1은 토마토 없음토마토는 최소 하나 있다고 한다. 모두 익을 때까지의 최소 날짜를 출력하되,모든 토마토가 익어있다면 0 출력, 모두 익지 못하는 상황이라면 -1을 출력한다. 풀이이 문제는 BFS로 풀어야 하는 문제다. 하루가 지날 때마다 영향을 받아 익게 되기 때문. from collections import dequem, n = map(int, input().split()) # 가로, 세로graph = []for i in..
문제 요약각 계단에는 일정한 점수가 쓰여 있음 - 그 점수 얻음1. 한 계단 / 두 계단씩 오를 수 있다2. 연속된 세 개의 계단은 모두 밟아서는 안 된다3. 마지막 도착 계단은 반드시 밟아야 한다각 계단에 쓰여 있는 점수가 주어질 때 총 점수의 최댓값 풀이DP로 풀 수 있다. '마지막 도착 계단은 반드시 밟아야 한다' 라는 조건 -> 도착지부터 생각하는 접근이 더 쉽다. n번째 계단에 올라오기 위해서는 두 가지 경우가 있다.1. n-1번째 계단에서 오는 경우dp[n] = dp[n-3] + stairs[n-1] + stairs[n]2. n-2번째 계단에서 오는 경우dp[n] = dp[n-2] + stairs[n]-> 이 중에서 더 큰 수가 dp[n]이 된다. dp[n-3]이 있기 때문에 1, 2, 3번..
Python에서 리스트를 정렬하는 데 사용되는 두 가지 주요 방법은 sort() 메서드와 sorted() 함수이다. 1. sort() 메서드sort()는 리스트 자체를 정렬한다. 즉, 호출된 리스트를 직접 수정하고 아무것도 반환하지 않는다. (반환 값 None)이 메서드는 리스트에만 적용되며, 다른 반복 가능한(iterable) 데이터 유형에는 사용할 수 없다. 2. sorted() 함수sorted()는 어떤 반복 가능한 객체도 입력으로 받아 정렬된 새 리스트를 반환한다. 이는 리스트뿐만 아니라 문자열, 튜플, 딕셔너리의 키 등 다양한 데이터 유형에 사용될 수 있다.원래 데이터는 수정되지 않고, 정렬된 새로운 리스트가 결과로 반환된다. 성능 차이속도 측면: sort()와 sorted()는 내부적으로 동..
문제 요약한 개의 회의실 - 이를 사용하고자 하는 N개의 회의각 회의의 시작 시간, 끝나는 시간 주어질 때겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 구하기-> 그리디의 대표적인 예인 Activity selection 문제이다.-> 빨리 끝나는 시간 순으로 정렬하여 그리디로 풀 수 있다! 참고https://en.wikipedia.org/wiki/Activity_selection_problem#:~:text=The%20activity%20selection%20problem%20is,finish%20time%20(fi). Activity selection problem - WikipediaFrom Wikipedia, the free encyclopedia Combinatorial optim..
2×n 크기의 직사각형을 채우는 방법의 수 n이 1일 때는 1, n이 2일 때는 가로 두개, 세로 두개로 2가지 ( =, || )n이 3일 때는 n이 2일 때 + n이 1일 때n이 4일 때는 n이 3일 때 + n이 2일 때-> 점화식 : 직사각형 가로의 길이가 N인 경우는 n-1 경우의 수 + n-2 경우의 수를 더한 값 n = int(input())def tiling(n): if n == 1: return 1 if n == 2: return 2 dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2]) % 10007 ..
풀이 1: DFS, 재귀이용 - RecursionErrordef dfs(x, y): visited[x][y] = True for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: nx, ny = x + dx, y + dy if 0 첫번째 풀이이다. DFS와 재귀를 사용하여 풀었더니 Recursion Error가 났다.Recursion Error: 재귀와 관련된 에러. 주로 Python이 정한 최대 재귀 깊이보다 더 깊어질 때.이 경우, 재귀를 사용하지 않도록 바꾸어야 한다.BFS를 사용해서 풀거나, 재귀 없이 DFS를 구현해야 한다. 참고 링크 : https://yesolz.tistory.com/entry/Python-%EB%B0%B1%EC%A..
그래프 탐색 문제로 DFS, BFS 둘다 사용하여 풀이가 가능하다.아래는 DFS를 활용한 풀이이다. DFSn = int(input()) # 정사각형 모양의 지도의 크기 입력# 지도 입력 받기map_data = [list(map(int, input())) for _ in range(n)]visited = [[False] * n for _ in range(n)] # 방문 여부를 저장하는 배열 초기화def dfs(x, y): visited[x][y] = True # 현재 위치를 방문했음을 표시 count = 1 # 단지의 크기를 세기 위한 변수 초기화 for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: # 현재 위치에서 이동할 수 있는 방향에 대해 반복..
