■ Dynamic Programming(동적 계획법)큰 문제를 작은 문제로 나누고, 그 작은 문제의 결과를 저장하여 같은 계산을 반복하지 않도록 하는 알고리즘 기법이다.중복 부분 문제 (Overlapping Subproblems)동일한 부분 문제를 여러 번 계산하게 되는 구조.최적 부분 구조(Optimal Substructure)문제의 최적해가 부분 문제의 최적해로 구성될 수 있다.기법특징 재귀 모든 경우를 완전 탐색. 그라디 항상 가장 좋아 보이는 선택을 한다. 최적해를 보장하지 않을 수 있다. DP 중복 계산을 피하며 모든 경우를 고려. 항상 최적해를 구한다.  DP에는 크게 2가지 구현 방식이 있다. 이 구현 방식을 피보나치 수열을 구하는 문제를 통해 알아보자. 1. Top-Down 방식p..

■ 그라디(Greedy) 알고리즘그라디(탐욕, 욕심쟁이) 알고리즘은 매 단계에서 “가장 좋아 보이는 선택”을 하는 알고리즘이다. 이 선택이 전체적으로도 최적일 거라는 가정 하에 작동한다.항상 최적의 값을 계산하는것을 보장하진 않는다. 다만 최적에 “근사한 값”을 목표로 한다.예시로 위 상황에서 항상 최적의 값(가장 짧은 KM)을 구하면 서울(40)→이천(80)→대구(30)의 순으로 총 150KM가 나온다. 하지만 서울→이천→대전→부산으로 가는 경로는 총 145KM이기 때문에 최적에 근사한 값을 내는 것을 확인할 수 있다. 예시) “손님에게 거스름돈을 줄 때 가장 적은 개수의 동전으로 거스름돈을 주려고 한다.”사용 가능한 동전의 종류는 [500원,100원,50원,10원]일 때, 거슬러 줘야 할 동전의 최소..

■ 개요Queue와 같이 FIFO(먼저 들어온 요소가 먼저 나감)처럼 삽입은 순서대로 하지만, 꺼낼 때는 우선순위가 높은(낮은) 순서로 꺼내지게 된다.중복을 허용하며, 우선순위가 같다면 일반적으로 삽입 순서에 따라 처리되거나, 다른 기준으로 정렬될 수 있다.  ■ Heap 우선순위 큐는 힙(Heap)을 사용해 구현하는데, 여기서 말하는 힙은 메모리 구조에서 말하는 힙이 아닌, “자료구조에서의 힙”을 의미한다. Heap 자료구조는 “완전 이진트리”로 구성된다.모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나(작거나) 같아야 한다.마지막 레벨은 왼쪽부터 값이 채워진다.위에서부터 내려갈수록 값이 커지면 Min-Heap, 값이 작아지면 Max-Heap이다.Min-Heap이던, Max-Heap이던 Roo..

■ 개요우리가 흔히 알고 있는 그래프 탐색 알고리즘에는 깊이우선탐색(DFS), 너비우선탐색(BFS), 다익스트라(Dijkstra) 알고리즘 등이 있다. 그렇다면 이런 그래프 탐색 알고리즘이 "2차원 배열의 타일맵(TileMap)"에서 어떻게 최단 경로를 찾는 데 사용될 수 있을까?  결론부터 말하자면, TileMap도 그래프이다. 예를 들어, 타일을 상하좌우 4방향으로만 이동할 수 있고, 흰색 타일을 길, 검은 타일을 장애물이라 하자. 이 경우, A타일은 인접한 B,C,D타일로 이동할 수 있다. 이런 타일을 그래프의 노드로 표현하면, A노드는 B,C,D를 자식 노드로 가지고 있는 것과 동일한 구조로 볼 수 있다.즉, 각 타일은 그래프의 정점, 이동 가능한 인접한 타일은 간선으로 연결되어 있는 그래프이다...