Data Structure & Algorithm/Algorithm

[Algorithm] Breadth-First Search(BFS)

오늘의 알고리즘 Topic은 Breadth-first search(너비우선탐색)입니다.사실 BFS라고 더 많이 불리고 있습니다. BFS하면 짝꿍 DFS도 빠질 수 없습니다.DFS는 이후 게시글에서 알아보도록하고 오늘은 BFS를 먼저 살펴보겠습니다.특징BFS의 기본 개념은 Tree 구조에서 파생되었고, Tree의 노드를 순회하는 방식 중에 하나입니다.어떠한 자료구조를 순회할 때는 항상 기준이 중요합니다. BFS의 기준은 바로 현재 노드의 Depth입니다. Tree는 기본적으로 Depth라는 개념이 있습니다.Root 노드로부터 몇번째 자식노드냐에 따라 Depth가 정해집니다.위 사진에서 최상단의 붉은 원이 Root노드이며, 11 노드는 Root 노드로부터 3번째 노드이므로 Depth가 3입니다.Tree 노드..

[Algorithm] Greedy(탐욕 알고리즘, 탐욕법)

오늘은 Greedy 알고리즘에 대해 알아보겠습니다.Greedy의 기본적인 개념은 전체를 고려하지 않고, 현재 상태에서 할 수 있는 최선의 선택을 하는 알고리즘 입니다.사실 전 처음에 개념의 뜻을 이해하지 못했는데요. 혹시라도 바로 이해가 되지 않더라도 천천히 이해해봅시다.접근법Greedy를 통해 문제에 접근하는 방식은 다음과 같습니다.1. 정렬 또는 기준 정의: 해결하려는 문제에 따라 최선에 대한 기준(최대, 최소 등)을 정합니다.2. 현재 상태에서의 최선을 선택: 각 단계에서 마다 기준에 따른 최선의 선택을 합니다.핵심따라서 Greedy를 이용해서 푸는 문제는 대부분 다음과 같은 특징을 갖는 것이 핵심입니다.- Greedy choice property(탐욕적 선택): 각 단계에서의 항상 탐욕적 선택만 ..

[Algorithm] Dynamic Programming(DP; 동적계획법)

오늘은 알고리즘 기법 중 Dynamic Programming에 대해 알아보도록 하겠습니다. 동적 프로그래밍, 다이나믹 프로그래밍, DP, 동적 계획법 등 다양한 이름으로 불립니다.알고리즘의 핵심은 문제를 작은 하위 문제들로 나누고 하위 문제들의 값을 캐싱하고 활용하여 큰 문제를 해결한다는 점입니다. 접근법DP는 두 가지 접근법이 존재합니다.1. 탑다운(Top-Down) 방식: 재귀와 캐싱2. 바텀업(Bottom-Up) 방식: 반복문을 통한 DP DP의 활용 예제로는 피보나치(Fibonacci) 함수 구현이 있습니다.탑다운(Top-Down) 방식var cache = [Int: Int]()func fibonacci(_ n: Int) -> Int { if let result = cache[n] { ret..