다이나믹 프로그래밍 (동적 계획법) 최적해를 구하기 위해 매우 많은 시공간이 필요한 경우 연산 결과를 저장하여 중복 연산을 방지함으로써 시공간 효율성을 높임 간단히 말하자면 한 문제를 무조건 한 번만 풀도록 결과를 저장해 사용한다는 것 언제 사용하는가 큰 문제를 작은 문제(큰 문제의 분할)로 나눌 수 있는 경우 작은 문제와 큰 문제의 해결 로직이 같아야 함 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일 해결 로직이 순수함수(동일 입력에 반드시 동일 출력이 보장)에 해당해야 함 어떻게 저장하는가 위 조건을 만족하는 문제들의 연산 결과들은 수열에 해당한다고 볼 수 있다. 수열은 규칙적으로 배열된 숫자들의 모임이기 때문에 배열(리스트)에 저장한다. 분할 정복 알고리즘과의 차이 분할 정복 알고리..
사전 지식 탐색 많은 양의 데이터 중 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고, 관리하고, 처리하기 위한 구조 스택과 큐에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - 파이썬에서의 스택(Stack)과 큐(Queue) 재귀함수 자기 자신을 호출하는 함수. 수학의 점화식을 코드화한 것 점화식: 특정 함수를 자기보다 더 작은 변수와 함수의 관계로 표현한 것 재귀 함수는 점점 작아지는 자기 자신 + 종료 조건을 통해 동작한다. 그래프 그래프에 대해 잘 모른다면 아래 글을 참고할 것 2021/02/01 - [개발 일지/Algorithm] - [Data Structure] 그래프(Graph) DFS (깊이 우선 탐색, Depth-First Searc..
스택(Stack) 후입선출(LIFO) 구조라고도 한다. 나중에 들어온 게 먼저 나간다. 파이썬에서는 다음과 같이 리스트 자료형을 통해 구현할 수 있다. stack = [] stack.append(0) # [0] stack.append(1) # [0, 1] stack.pop() # [0], return 1 큐 (Queue) 선입선출(FIFO) 구조라고도 한다. 먼저 들어온 게 먼저 나간다. 파이썬에서는 큐를 구현하기 위해 collections 모듈의 deque(덱)을 이용한다. 덱(deque)이란 스택과 큐를 합친 자료구조로, 양 방향에서 삽입/삭제가 가능하다. from collections import deque queue = deque() queue.append(0) # [0] queue.append(..
구현 알고리즘 실생활의 문제를 코드로 나타내 해결하는 방식 완전 탐색과 시뮬레이션 유형으로 나뉜다. 완전 탐색 (Brute-force search) 모든 경우의 수를 다 계산하는 방식 즉 로직을 간단하게 하기 위해 시간, 공간 복잡도를 늘리는 방식이다. 따라서 주어진 입력의 범위가 적을 때만 사용해야 한다. 시뮬레이션 (Simulation) 문제에서 제시한 알고리즘을 한 단계씩 차례대로 수행하는 방식 자주 등장하는 유형 실생활의 문제를 코드로 나타내기 위해서는 수식화 단계를 거쳐야 한다. 좌표로 나타내기 이동 가능한 경로를 계산하는 등의 방식에서 사용된다. # 상하좌우 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] literal = ['Up', 'Down', 'Left', 'Righ..
그리디(탐욕) 알고리즘 가장 좋은 것만 취한다는 의미에서의 그리디이다. 이전 결과를 신경쓰지 않고, 현재 상황에서 자신이 가진 최적 값과 입력된 값을 비교해 최적인 값을 취한다. 언제 사용하는가? 최적의 해(최대, 최소 등)를 구해야 하는 경우 주의할 점 항상 최적해를 도출하는가에 대한 주의를 해야 한다. 자주 등장하는 유형 순회하며 최적해 고르기 처음부터 끝까지 쭉 훑으며 비교해 최적해를 계속 갱신하는 방식 배열에서 최대/최소값 찾기가 이에 해당한다. 최적해를 도출할 공식을 정한 뒤 예외를 쳐 냄 항상 최적인 공식이 정해져 있고, 이를 최대한 많이 적용하는 방식 웬만한 난이도에서면 최적인 공식만을 적용할 수 없도록 예외가 존재한다. 이를 빠짐없이 찾아내는 것이 어려워 은근 정답률이 낮은 유형 최대/최소..
