그리디 알고리즘이란?그리디 알고리즘은 매 순간 최선으로 보이는 선택을 하고, 그 선택을 번복하지 않는다 는 전략이다. 그리디는 한번 결정하면 되돌아가지 않는다는 백트래킹이 없는 방식이다. 항상 지금 최선 == 전체 최선 이 아니다. 그리디 알고리즘을 적용하려면탐욕적 선택 속성 각 단계에서 국소 최적 선택을 해도, 그게 전체 최적해로 이어진다.최적 부분 구조전체 문제의 최적해가 부분 문제의 최적해로 구성된다. ex) 분수 배낭 문제에서, 배낭 용량은 50kg. 물건은 쪼갤 수 있다.물건 A: 무게 10kg, 가치 60 → kg당 가치 6물건 B: 무게 20kg, 가치 100 → kg당 가치 5물건 C: 무게 30kg, 가치 120 → kg당 가치 4 1. 탐욕적 선택 속성 확인 : kg 당 가치 기준으..
문제- 메모이제이션(Memoization)을 사용한 하향식 DP로 피보나치 수를 계산합니다.- 이미 계산한 값을 저장하여 중복 계산을 방지합니다. 문제풀이def fibonacci_memo(n, memo=None): """ 메모이제이션을 사용한 피보나치 (하향식 DP) Args: n: 피보나치 인덱스 memo: 계산 결과를 저장할 딕셔너리 Returns: n번째 피보나치 수 """ if memo is None: memo = {} if n 동적 프로그래밍에 대한 개념은 여기에 정리하였다. 다이나믹 프로그래밍 (DP) 정리다이나믹 프로그래밍이란?복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알..
문제- DFS로 그래프를 탐색합니다.- 깊이 방향으로 끝까지 탐색합니다.- 재귀 또는 스택을 사용합니다. 문제풀이def dfs(graph, start, visited=None): """ 깊이 우선 탐색 (재귀) Args: graph: 그래프 딕셔너리 start: 현재 정점 visited: 방문 리스트 Returns: 방문 순서 리스트 """ # 재귀 호출에서 비어있을 때 최초로 초기화 필 if visited is None: visited = [] visited.append(start) # [시작정점의 연결점 확인] for i in graph[start]: ..
문제- BFS로 그래프를 탐색합니다.- 가까운 정점부터 방문합니다.- 큐(Queue)를 사용합니다. 문제풀이from collections import deque# 시작점과 동일한 레벨인지는 어떻게 판단하지? def bfs(graph, start): """ 너비 우선 탐색 Args: graph: 그래프 딕셔너리 start: 시작 정점 Returns: 방문 순서 리스트 """ visited = [] # TODO: 큐 생성 및 시작 정점 추가 ## 방문한 정점 집합 queue = list() # 시작 정점 추가 queue.append(start) arr = [] #..
Ch 1.1 ~ 1.4 는 여기에서 확인할 수 있습니다. 컴퓨터 시스템 Ch 11.1 정보는 비트와 컨텍스트로 이루어진다.개발자가 작성한 소스 프로그램은 텍스트 파일의 아스키 문자로 변환되고, 아스키 문자는 비트값이므로 비트로 저장이 된다. 같은 비트열도 컨텍스트skylarcoding.tistory.com 1.5 캐시가 중요하다시스템은 정보를 한 곳에서 다른 곳으로 이동시키는 일에 많은 시간을 쓴다. 이러한 여러 복사과정들이 프로그램의 실제 작업을 느리게 하는 오버헤드다. 시스템 설계자들의 주요 목적은 이러한 복사과정들을 가능한 빠르게 동작하도록 하는 것이다. 캐시 메모리라는 작고 빠른 저장장치를 고안하여 프로세서가 단기간에 필요로 할 가능성이 높은 정보를 임시로 저장할 목적으로 사용한다. 프로그..
