분류 전체보기 (133) 썸네일형 리스트형 백준 10870 "피보나치 수 5" Python n = int(input()) if n == 0 : print(0) exit() if n == 1 : print(1) exit() dp = [0]*(n+1) dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-1] +dp[i-2] print(dp[n]) 백준 10872번 def recursive(n): if n == 1: return 1 return n*recursive(n-1) n = int(input()) if n == 0 : print(1) exit() print(recursive(n)) [다시 풀어볼것] 백준 6603 def recursive(depth, idx) : #탈출 조건 if depth == 6: print(*answer) return #dfs 로직 for i in range(idx, k): answer.append(s[i]) recursive(depth+1, i+1) answer.pop() while True: inputs = list(map(int, input().split())) answer = [] k = inputs[0] s = inputs[1:] if k == 0 : exit() recursive(0, 0) print() # 1 2 3 4 5 6 7 8 9 10 11 12 13 참고 : https://ji-gwang.tistory.com/267 다이나믹 프로그래밍 (DP) - 동적 계획법 다이나믹 프로그래밍(DP) 메모리(배열, 자료구조를 만들어서 사용)를 적극 활용해 수행 속도를 비약적으로 줄이는 기법 메모리제이션(Memorization) 계산한 결과를 메모리 공간에 기억 같은 문제를 다시 호출 ⏩ 결과를 그대로 가져옴 값을 기록 == 캐싱 DP 조건 예시) 피보나치 수열 (점화식을 이용한 수열) 1. 최적 부분 구조 - 큰 문제 ▶ 작은 문제 ⏩ 작은 문제들을 모아서 큰 문제 해결 2. 중복되는 부분 문제 - 작은 문제들이 반복되어야 한다. 탑 다운(하향식) 재귀를 이용 바텀 업(상향식) 반복문을 이용 분할 정복과의 차이점 = 부분 문제의 중복 여부 DP와 분할 정복은 모두 최적 부분 구조를 가질 때 사용! ( 큰 문제 ⏩ 작은 문제 ) DP는 각 부분 문제들이 서로 영향을 미치며 부.. [정렬] 프로그래머스 - H-index python def solution(citations): answer = 0 citations.sort() cnt = 0 length = len(citations) for a in citations: if a length -cnt: if answer < length -cnt: answer = length -cnt cnt += 1 return answer [완전탐색] 프로그래머스 - 카펫 python from math import ceil, floor, sqrt def solution(brown, yellow): answer = [] height = 0 width = 0 area = brown + yellow sqrt_area = (ceil(sqrt(area))) for i in range(3, sqrt_area+1): if area % i == 0: if (area/i - 2)*(i-2) == yellow: height = i width = area/i answer.append(int(max(height, width))) answer.append(int(min(height, width))) return answer [DPS] 프로그래머스 - 단어 변환 DFS def solution(begin, target, words): if target not in words : return 0 visited = [] answer = 0 dfs_flag = True #답을 찾으면 False, 모든 DFS 종료 def dfs(begin, point): visited.append(begin) point += 1 #탈출 조건 cnt = 0 for i in range(len(begin)): if begin[i] != target[i]: cnt+=1 if cnt == 1: nonlocal answer answer = point nonlocal dfs_flag dfs_flag = False return #실행문 for word in words: flag = 0 if word .. [DFS] 프로그래머스 - 네트워크 DFS def solution(n, computers): answer = 0 visited = [False] * n def dfs (graph, start, visited): visited[start] = True for node in range(len(graph[start])): if visited[node] == False and node != start and graph[start][node] == 1: dfs(computers, node, visited) for i in range(n): if visited[i] == False : dfs(computers, i, visited) answer+=1 return answer 이전 1 ··· 13 14 15 16 17 다음