Always Be Wise

그리디 알고리즘(Greedy Algorithm)이란 문제를 해결하는 과정에서 순간 순간마다 최선이라고 생각하는 것을 선택하여 최종 해답에 도달하는 알고리즘을 의미한다. 계산 과정이 굉장히 빠른 알고리즘이지만, 순간 순간 마다의 최선의 선택이 언제나 전체 결과의 최선의 해결책을 보장하지는 않는다는 단점이 있다. 그리디 알고리즘을 사용하기 위해서는 다음의 두 가지 조건을 만족해야 한다. 1. 최적 부분 구조(Optimal Substructure) : 부분 문제의 최적 결과를 전체에 그대로 적용할 수 있다. 2. 탐욕적 선택 속성(Greedy Choice Property) : 이전의 선택이 이후 선택에 영향을 주지 않는다.

동적 프로그래밍(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 해결하는 방법을 의미한다. 여러 개의 문제로 나누어 해결한다는 점에서 분할 정복(Divide and Conquer)과 유사해 보이지만, 동적 프로그래밍의 경우, 간단한 문제들이 반복적으로 일어난다는 점에서 차이가 있다. 즉, 동적 프로그래밍은 간단한 문제들을 한 번만 해결하고 그보다 복잡한 문제를 풀어나갈 때 똑같은 간단한 문제가 다시 나타나면 그 결과 값을 이용해해결하는 방법이다. 이때, 간단한 문제의 결과 값을 기억하여 반복 수행을 제거하는 과정을 메모이제이션(Memoization)이라고 한다. 동적 프로그래밍을 사용하려면 아래 두 가지 조건을 만족해야 한다. 1. 부분 문제 반복(Overlapp..

플로이드 워셜 알고리즘(Floyed-Warshall Algorithm)은 모든 정점에서 모든 정점 사이의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘이 하나의 정점에서 모든 정점 사이의 최단 경로를 찾는 것과는 차이가 있다. 또한 가중치를 음수와 양수 모두 가질 수 있다는 점도 다르다. 플로이드 워셜 알고리즘의 기본 동작 원리는 다음과 같다. 1. 최단 거리 테이블을 만든다. 이때, 초기 주어진 조건으로 하나의 정점에서 다른 정점으로 바로 갈 수 있는 경우 그 값으로, 갈 수 없는 경우 무한대로 테이블을 초기화한다. 2. 모든 정점에 대하여 해당 정점을 지나 다른 정점으로 이동할 때의 거리를 구하고, 기존의 거리와 비교하여 그 거리가 더 짧다면 테이블의 값을 갱신한다. 점화식으로 표현하자면 다음과..

위상 정렬은 사이클이 없는 방향 그래프의 정점들을 방향성을 거스르지 않고 순서대로 나열하는 것을 의미한다. 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 위 그림과 같이 수강해야 할 과목이 세 가지 있다고 가정하자. 세 과목을 정상적으로 수강하기 위해서는 화살표의 방향대로 [자료구조 - 알고리즘 - 고급 알고리즘] 순으로 들어야 한다. 만약 [자료구조 - 고급 알고리즘 - 알고리즘] 순으로 듣고자 한다면, 해당 순서는 화살표의 방향을 거스르기 때문에 올바른 수강 순서가 아니다. 위상 정렬 알고리즘을 이해하기 위해서는 진입차수와 진출차수에 대한 개념을 알아야 한다. 진입차수(Indegree)는 특정한 정점으로 들어오는 간선의 개수를 의미..

이분 그래프는 아래 그림 처럼 그래프의 정점들이 두개의 그룹(빨간색 정점으로 이루어진 그룹, 파란색 정점으로 이루어진 그룹)으로 나뉘고, 같은 그룹의 정점들끼리는 서로 간선으로 이어지지 않는 경우를 의미한다. 간선이 없고 정점만 있는 경우도 이분 그래프이다.

다익스트라 알고리즘(Dijkstra Algorithm)은 그래프 내 하나의 정점에서 다른 모든 정점까지의 최단 거리/경로를 구하는 알고리즘이다. BFS와 다른 점은 가중치 그래프에서도 사용 가능하다는 것이다. 다만, 그래프 내 엣지들은 모두 양수여야 한다. 다익스트라 알고리즘의 기본 동작 원리는 다음과 같다. 1. 출발 정점을 설정한다. 2. 최단 거리 테이블을 초기화한다. 이때, 초기 값은 출발 정점을 제외하고 모두 무한대 값을 가진다. 3. 출발 정점과 연결된 정점 가운데 방문하지 않는 정점들을 찾는다. 4. 그중 최단 거리가 가장 짧은 정점을선택한다. 이때, 최단 거리란 갱신하기 전 최단 거리를 의미하며 2번에서 초기화한 테이블의 값과는 다르다. 5. 해당 정점을 거쳐 다른 정점으로 가는 거리를 ..

크루스칼 알고리즘(Kruskal Algorithm)이란 무방향의 가중치 그래프의 모든 정점을 최소 가중치로 연결하는 방법을 의미한다. 최소 스패닝 트리를 찾을 때 대표적으로 사용하는 알고리즘이다. 크루스칼 알고리즘은 무언가를 결정해야 할 때마다 그 순간에 가장 좋다고 생각하는 것을 선택하는 탐욕적인(Greedy) 방법을 따른다. 구체적인 동작 과정은 아래와 같다. 1) 모든 엣지들을 끊어 놓는다. 2) 엣지들을 가중치 순으로 오름차순 정렬한다. 3) 정렬된 엣지들을 순서대로 선택한다(가장 낮은 가중치를 먼저 선택). 4) 선택한 엣지가 사이클을 형성하지 않는지 확인한다. 5) 사이클을 형성하지 않는다면, 해당 엣지를 최소 스패닝 트리에 포함시킨다. 엣지들을 가중치 순으로 오름차순 정렬한다. B-C D-E..

그래프(Grpah)란 연결 관계를 저장할 수 있는 자료 구조를 의미한다. 그래프에서 하나의 데이터 단위를 나타내는 객체를 노드라고 한다. 위 그림에서 하나의 유저가 하나의 노드다. 두 노드의 직접적인 연결 관계를 엣지라고 한다. 위 그림에서 흰 선들이 그래프의 엣지에 해당한다. 두 노드 사이에 엣지가 있을 때 두 노드는 인접해 있다고 표현한다. 엣지가 갖는 특성에 따라 그래프의 종류를 세부적으로 구분할 수 있다. 우선, 엣지들이 방향을 가지고 있을 경우 방향 그래프라고 한다. 방향 그래프를 통해 인스타그램의 팔로우 관계처럼 한 유저가 다른 유저를 팔로우하는 일방적인 관계를 나타낼 수 있다. 엣지들의 연결 관계뿐만 아니라 어떤 정보를 나타내는 수치를 갖는 그래프를 가중치 그래프라고 한다. 예를 들어, 인천..

트리(Tree)는 데이터 사이의 계층 관계를 표현하는 비선형 자료구조를 의미한다. 트리는 노드(Node)와 가지(Edge)로 구성된다. 아래 그림에서 A, B, C 등이 노드에 해당하며 해당 노드들을 연결하는 선들이 가지다. 트리의 가장 위쪽에 있는 노드를 루트(Root), 가장 아래쪽에 있는 노드를 리프(Leaf)라고 한다. 리프는 단말 노드(Terminal Node), 외부 노드(External Node)라고도 하며, 물리적으로 가장 아래쪽에 위치한다는 의미가 아니라 해당 노드 아래로 가지가 더 이상 뻗어나갈 수 없다는 의미이다. 리프를 제외한 노드(루프 포함)를 비 단말 노드(Non-Terminal Node), 내부 노드(Internal Node)라고도 한다. 어떤 노드와 노드가 가지로 연결되어 있..

DFS(Depth First Search)는 깊이 우선 탐색, 세로 검색, 수직 검색이라고도 한다. DFS는 트리의 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선하는 알고리즘을 의미한다. 리프에 도달해서 더 이상 검색할 곳이 없으면 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다. 그런데 DFS는 노드를 방문 하는 순서에 따라 3가지 순회 방식을 갖는다. Preorder(전위 순회) [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회 순회 순서 : A -> B ->D -> E -> G -> H ->C -> F -> I Inorder(중위 순회) [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회 순회 순서 : D -> B -> G -> E -> H -> A -> C -> I -> ..