Algorithm/Algorithm Categories
-
이분탐색 (Binary Search)Algorithm/Algorithm Categories 2022. 3. 27. 18:06
기본 개념 배열 내의 특정 값을 찾는 기초적인 알고리즘이다. 특정 값을 찾기 위해 모든 데이터를 순차 탐색을 하는 것이 아니라 탐색 범위를 반씩 줄여나가며 탐색을 진행한다는 특징을 가지고 있다. 여기서 중요한 점은 배열이 정렬되어 있어야 한다는 점이다. 특정 조건을 토대로 범위를 절반씩 줄여나가기 때문에 정렬되지 않은 배열에서 이분 탐색은 사용할 수 없다. 이분 탐색을 구현할 때 변수를 보통 세 가지를 사용한다. start, mid, end 세 가지 변수를 통해 현재 탐색 범위의 시작은 start, 탐색 범위의 끝은 end, 그 중간 값은 mid로 사용한다.(물론 변수 명은 개인에 따라 바뀔 수 있다). 이 세 변수를 통해 찾으려는 데이터와 중간 값 위체에 있는 데이터를 반복적으로 비교해서 특정 값을 찾..
-
다이나믹 프로그래밍 (Dynamic Programming, DP)Algorithm/Algorithm Categories 2022. 3. 13. 01:50
기본 개념 다이나믹 프로그래밍(동적 계획법)은 큰 문제를 여러 작은 문제들의 해결을 통해 풀어가는 알고리즘을 뜻한다. 쉽게 말해 하나의 큰 문제를 쪼개 작은 여러 개의 문제로 만들고, 이 작은 문제들을 해결하다 보면 큰 문제를 해결할 수 있게 된다는 개념이다. (작은 문제들은 큰 문제의 조각들이니까) 언뜻 보면 분할 정복(Divide and Conquer)과 비슷하게 생각할 수 있지만 다이나믹 프로그래밍이 가진 다음 두 가지 조건으로 분할 정복과 구별된다. 최적 부분 구조(optimal substructure) 중복된 하위 구조(overlapping subproblems) 최적 부분 구조는 현재 최적 선택이 전체 최적 선택이 되어야 한다는 조건이다. 큰 문제를 여러 작은 문제들로 나눠놨으니 이는 당연한 ..
-
깊이 우선 탐색 (Depth-First Search, DFS)Algorithm/Algorithm Categories 2022. 1. 30. 16:34
기본 개념 '깊이 우선 탐색'은 '너비 우선 탐색'과 마찬가지로 그래프(혹은 트리와 같은 자료구조)를 탐색하는 방법 중 하나다. 루트 노드에서부터 접근할 수 있는 최대한 깊은 노드까지 탐색을 한 뒤, 전으로 돌아와 다른 노드의 끝까지 다시 탐색하는 방식을 반복해 탐색을 수행하는 알고리즘이다. 갈 수 있는 최대 깊이까지 탐색을 수행한 뒤, 다음 탐색으로 넘어간다는 알고리즘 수행 방식으로 인해 너비 우선 탐색에 보다 탐색 속도가 느리다. 하지만 특정 목표 노드가 있을 경우 해당 노드까지의 경로 혹은 도달 가능 여부를 빠르게 파악할 수 있다는 장점이 존재한다. 예시 위와 같은 총 7개의 노드를 가진 그래프를 예시로 생각해보자. 루트 노드는 A로 설정해보자. 이제 좌에서 우 순서로 깊이 우선 탐색을 진행하겠다...
-
너비 우선 탐색 (Breadth-First Search, BFS)Algorithm/Algorithm Categories 2022. 1. 18. 08:34
기본 개념 '너비 우선 탐색'이란 그래프(혹은 트리와 같은 자료구조)를 탐색하는 방법 중 하나로, 자신이 탐색할 수 있는 가장 가까운 곳을 우선적으로 탐색하는 알고리즘이다. 다시 말해, 루트 노드에서부터 시작해 인접한 자식 노드들을 한 번씩 탐색하고 이를 반복해 탐색을 수행하는 알고리즘이다. 자신과 가까운 모든 경로를 탐색하고 그다음 거리의 경로를 탐색한다. 때문에 모든 경로를 탐색해야 하는 경우 '깊이 우선 탐색'보다 빠르게 수행할 수 있다는 장점이 있다. 예시 3*3, 총 9칸의 보드가 있고 이 보드를 탐색한다고 해보자. (움직일 수 있는 방향은 상하좌우 네 방향뿐이며 현재 내 위치는 A이다.) 너비 우선 탐색에서는 Queue를 이용해 탐색하는 방식을 주로 사용한다. Queue를 만들어주고 내 위치를..
-
그리디 알고리즘(Greedy Algorithm)Algorithm/Algorithm Categories 2022. 1. 1. 19:35
기본 개념 그리디 알고리즘(greedy algorigthm, 탐욕 알고리즘)이란 선택의 상황에서 현재 가장 최선이라고 생각되는 것을 선택해 나가 결과를 도출하는 알고리즘이다. 현재 최적인 값만 탐색하면 되기 때문에 계산 속도가 빨라 실용적이라는 장점이 있으나, 최종 값이 최적 값이라는 보장이 없다는 단점이 존재한다. 그리디 알고리즘을 사용할 때에는 두 가지 조건이 만족되어야 한다. 탐욕 선택 속성(greedy choice property) 최적 부분 구조(optimal substructure) '탐욕 선택 속성'은 현재 선택이 다음 선택과 무관해야 한다는 조건이고, '최적 부분 구조'는 현재 최적 선택이 전체 최적 선택이 되어야 한다는 조건이다. 두 조건을 만족하지 않다면 그리디 알고리즘을 사용했을 때 ..