0. 그래프그래프는 아이템과 이들 사이의 연결 관계를 표현하는 자료구조이다.그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조이다.정점(Vertex): 그래프의 구성요소로 하나의 연결점간선(Edge): 두 정점을 연결하는 선차수(Degree): 정점에 연결된 간선의 수인접(Adjacency): 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.경로(Path): 어떤 정점에서 시작하여 다른 정점으로 끝나는 순회로 두 정점 사이를 잇는 간선들을 나열한 것싸이클(Cycle): 경로의 시작 정점과 끝 정점이 같음(시작한 정점에서 끝나는 경로)V개의 정점을 가지는 무향 그래프는 최대 V * (V-1) / 2개의 간선이 가능하다.선형 자료구조나 트리..

0. 백트래킹Go as deep as possible, backtrack if impossible 모든 조합을 시도해서 문제의 해를 찾는 알고리즘이다.모든 가능성을 하나의 트리(상태 공간 트리)처럼 구성할 수 있으며, 가지 중에 정답이 있다.하지만 모든 경로를 찾는 것은 비효율적이기 때문에, 해답이 될 가능성이 있는 선택지만 타고 들어간다.즉, 완전 탐색(순열, 조합, 부분집합, BFS, DFS 등) + 가지 치기라고 생각하면 편하다.상태 공간 트리(State-Space Tree)문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리ex) 미로를 해결할 때 갈림길에 놓인 지점가지치기(pruning)가능성이 없는 노드가 포함되는 경로는 더 이상 고려하지 않는다.1. 적용 예시n-queenn*n 체스 보..

0. 이진 탐색(Binary Search)이진 탐색은 타겟(원하는 값)을 찾을 때까지 이진 탐색을 반복 수행하며 검색 범위를 반으로 줄여가면서 순차 탐색보다 빠르게 검색을 수행하는 알고리즘이다.단, 이진 탐색을 하기 위해서는 자료가 정렬된 상태여야 하는 제약이 존재한다. 분할 정복을 기반으로 하는 방식으로, 분할 정복을 알고 있다면 더욱 이해하기 쉽다.1. 이진 탐색의 로직자료의 중앙에 있는 원소를 고른다.중앙값(중앙 원소의 값)과 타겟을 비교한다.중앙값과 타겟이 일치하면 탐색을 끝낸다.타겟이 중앙값보다 작으면 자료의 왼쪽 반에 대해 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해 새로 검색을 수행한다.찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다아래 그림은 6을 찾는 이진 탐색의 그림이다...

0. 탐욕 알고리즘이란?탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다.일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.각 선택 시점에서 이루어지는 결정은 그 순간에는 최적이지만, 그 선택이 모인 최종적인 해답이 최적이라는 보장은 없다.1. 배낭 짐싸기(Knapsack)배낭에 담을 수 있는 물건의 총 무게(W)가 정해져 있다.이 때, 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값이 최대가 되는 물건을 담는 경우, 그리디 알고리즘을  생각해볼 수 있다.1-1. 0-1 Knapsak배낭에 물건을 통째로 담아야 하는 문제 ➡ 물건을 쪼갤 수 없는 경우이 방식은 그리디 알고리즘을 적용하기 어렵다. 아래에는 총무게가 30kg인 배낭에 0-1Knaps..