그리디 알고리즘이란? 그리디 알고리즘은 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다. 그리디 알고리즘(Greedy Algorithm)란 바로 눈 앞의 이익만을 쫓는 알고리즘이다. 대부분의 경우에는 뛰어난 결과를 도출하지 못하지만, 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다. 이러한 특성때문에 '욕심쟁이 알고리즘'이라는 별명이 붙은 알고리즘이기도 하다. 아래 이미지를 보면 큰 값을 찾기 위한 '그리디 알고리즘의 동작방식과 실제 큰 값은 다르다.'는 것을 알 수 있다. (진짜 욕심쟁이네....

다이나믹 프로그래밍(dynamic programming, DP)이란? 다이나믹 프로그래밍은(DP) 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 구하는 알고리즘 설계 기법이다. 앞에서 구했던 답을 뒤에서도 이용하고, 또 그 뒤에서도 이용할 수 있다. 쉽게 말해서는 답을 재활용하는 것이고, 같은 말로 프로그래밍 영역에서는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. DP는 구체적인 알고리즘이라기 보다는 문제해결 패러다임에 가깝다. DP는 아래와 같은 특징이 있다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 DP의 구현은 일반적으로 두 가지(탑다운 - 하향식, 바텀업 - 상향식) 방식으로 구현함 ..

그래프 순회(Graph Traversal) 그래프 순회란 그래프 탐색(Search)이라고도 불리우며, 그래프의 각 정점을 방문하는 과정을 말한다. 그래프의 각 정점을 방문하는 그래프 순회(Graph Traversls)에는 크게 깊이 우선 탐색 DFS(Depth-First Search, DFS)과 너비 우선 탐색 BFS(Breadth-First Search, BFS) 2가지 알고리즘이 있다. 두 가지 모두 탐색 알고리즘에 해당한다. DFS는 주로 스택 또는 재귀로 구현한다. BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다. 깊이 우선 탐색 - DFS(Depth-First Search, DFS) 깊이 우선 탐색은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고..

그래프(Graph) 비선형 자료구조인 그래프 또는 트리에서 자료를(원소) 보관하는 것을 정점(Vertex) 혹은 노드(Node)라고 부르며, 정점에서 다른 정점으로 가는 경로를 간선(Edge) 혹은 링크(Link, 다른 노드의 위치 정보)라고 부른다. 이를 통해 연결된 노드 간의 관계를 표현할 수 있다. 즉, 연결 관계를 표현하는 자료구조라고 할 수 있다. 아래의 이미지처럼 그래프는 트리보다 더 넓은 범위라고 할 수 있다. 그래프의 종류 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph) 무방향 그래프는 간선을 통해 양방향으로 갈 수 있다. 방향 그래프는 간선의 방향이 존재하는 그래프로 한 방향으로만 갈 수 있다. 노드 사이에 양방향으로 표시된 간선은 양방향으로 통행..

분할 정복(Divide and Conquer) 분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다. 분할 정복(Divide and conquer)은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다. 대표적인 분할 정복 알고리즘으로는 병합 정렬이 있다. 위의 이미지에 보이듯이 병합 정렬은 상단에서 '분할' 하고, 중앙에서 '정복' 하고, 하단에서 '조합' 한다. 이를 좀 더 구체적으로 살펴보면 아래의 이미지와 같다. 중요 개념 정리 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. 조합: 하위 문제에 대한 결과를 ..

이분 탐색(binary search)란? 이분탐색(binary search)은 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법이다. 이분탐색을 사용하는 이유와 시간 복잡도 내가 원하는 값을 빠르게 찾을 수 있기때문에! 정렬된 데이터에서만 사용 가능한 제약사항이 존재하지만 선형 검색과는 달리, 이진 검색에서는 주목할 원소를 다음에 검색할 범위의 중간 지점으로 단숨에 이동하게 된다. 일반적으로 n개의 원소가 오름차순으로 정렬된 배열에서 이진 검색에서 한 단계씩 진행할 때마다 검색 범위는 거의 반으로 좁혀진다. 따라서 시간 복잡도는 O(logN) 으로 굉장히 빠르다. 아래 그림에서 차이를 확인해보자. 선형탐색 vs 이분탐색 ..