그리디 알고리즘
현재 상황에서 지금 당장 좋은 것만 고르는 방법. 현재 선택이 나중에 미칠 영향에 대해서 고려하지 않음.
거스름돈
가장 큰 화폐 단위부터 돈을 거슬러 주는 것. N원일 때 거슬러줘야 할 동전의 최소 개수를 구할 때, 가장 먼저 500원으로 거슬러 줄 수 있는 만큼 거슬러 준다. 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있음.
단, 800원을 거슬러 줘야 할 때, 화폐단위가 500, 400, 100인 경우처럼 동전의 단위가 서로 배수 형태가 아니라, 무작위로 주어진 경우에는 해결할 수 없음.
탐색 알고리즘
자료구조 기초
데이터를 표현하고 관리하고 처리하기 위한 구조. 스택, 큐, 배열, 트리, 그래프, Set 등이 있음.
- Stack - 선입후출, 후입선출 구조
- Queue - 선입선출 구조
재귀 함수
자기 자신을 다시 호출하는 함수. 종료 조건을 꼭 명시해야 함.
def factorial_recursive(n): if n <= 1: return 1 return n * factorial_recursive(n-1) # n! = n * (n-1)! print(recursive_function(5)) #120
그래프
- 인접 행렬 - 2차원 배열로 그래프의 연결 관계를 표현하는 방식.
- 인접 리스트 - 리스트로 그래프의 연결 관계를 표현하는 방식.
BFS, DFS
- BFS(Breadth First Search, 너비 우선 탐색) - 가까운 노트부터 탐색하는 알고리즘.
- DFS(Depth-First Search, 깊이 우선 탐색) - 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. ex) 재귀 함수
호출 스택 (Call stack)
- 호출 스택은 여러 함수들(functions)을 호출하는 스크립트에서 해당 위치를 추적하는 인터프리터 (웹 브라우저의 자바스크립트 인터프리터같은)를 위한 메커니즘.
- 현재 어떤 함수가 동작하고있는지, 그 함수 내에서 어떤 함수가 동작하는지, 다음에 어떤 함수가 호출되어야하는지 등을 제어함.