본문 바로가기

Algorithm

 (3)
[Algorithm] 너비 우선 탐색(BFS, Breadth-First Search) 그래프 탐색이란, 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 단 한번씩 방문하는 것을 의미한다. 그래프 탐색에는 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 두 가지의 방법이 있는 데, 그 중에서 너비 우선 탐색에 대해 알아보고자 한다. 너비 우선 탐색(BFS, Breadth-First Search) 너비 우선 탐색이란, 인접한 노드들을 차례대로 방문하는 그래프 탐색 방법이다. 위 그림은 너비 우선 탐색과 깊이 우선 탐색에 대한 그림이다. 그림과 같이 너비 우선 탐색 트리는 높이가 작은 노드부터 차례대로 탐색하고 더 높은 높이를 탐색한다면, 깊이 우선 탐색은 자신보다 높은 높이의 노드를 탐색한다. 너비 우선 탐색은 큐(Queue) 자료구조를 사용한다. 큐를 이용하여 너비 우선 탐색을 구현..
[백준] 1781 컵라면 1781 컵라면 : https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다. 문제 번호 1 2 3 4 5 6 7 데드라인 1 1 3 3 2 2 6 컵라면 수 6 7 2 1 4 5 1 위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 www.acmicpc.net 문제 당 마감시간과 보상이 주어지고, 이때 보상이 최대 수를 구하는 문제 접근 주어진 마감 시간 내에 최대 보상을 얻어..
[Algorithm] 탐욕 알고리즘(Greedy Alogrithm) 탐욕 알고리즘이란? 최적해 문제에서 사용되는 알고리즘으로, 매순간 가장 최적으로 여겨지는 선택을 해나가며 최종적으로 최적의 해를 구하는 알고리즘이다. 동적 프로그래밍의 수행 시간문제를 보완하기 위해 고안된 알고리즘이다. 현재 동적 프로그래밍과 서로 보완해나가며 같이 사용되고 있다. 매 순간 최적을 고른다고 해서 이 것이 항상 최적인 해를 얻는다는 보장이 없으므로, 최적인 해답을 얻는지 확인하는 절차가 반드시 필요하다. 또한 모든 문제에서 탐욕 알고리즘이 적용가능한 것은 아니다. 허프만 코드(Huffman Code) 탐욕 알고리즘의 대표적인 예로는 허프만 코드가 있다. 허프만 코드는 데이터 압축 방법으로, 문자의 출현 빈도수에 따라 서로 다른 길이의 코드를 부여한다. 일반적으로 빈도수가 높은 문자가 짧은 ..

티스토리툴바