이번이 드디어 알고리즘 마지막 시간이다. 마지막 답게 아직 풀리지 않고 있는 알고리즘에 대해 소개하는 시간을 갖겠다. 근사 알고리즘이라는 말에서도 알 수 있듯이 해당 알고리즘들은 아직 풀리지 않고 있기에 정확한 해를 구하지 못해 최대한 근사한 해를 구하는 방법을 알아내는 것이다. 수학 혹은 컴퓨터공학에서 가장 유명한 밀레니엄 문제 중 하나 인 P-NP 문제에 대해 소개하고 대표적인 NP 문제에 대한 코딩을 해보며 마지막 알고리즘 포스팅을 마쳐볼까 한다. 필자가 어릴적에 했던 재밌는 게임 중에서 '한붓그리기' 게임이 있었다. 그 게임은 간선과 정점으로 이루어진 그래프가 주어졌을 때, 각각의 간선을 딱 한번씩만 방문해서 모든 정점을 방문 할 수 있는 경로를 찾는 게임이었다. 이를 이산수학에서 오일러 회로 (..
어릴적 셜록 홈즈 소설을 읽었는데 '춤추는 인형'을 참 재밌게 읽은 기억이 난다. 이 춤추는 인형도 일종의 암호화 였다. 우리가 사용하는 자연어를 컴파일 가능한 기계어로 바꾸듯이, 셜록홈즈의 춤추는 인형에서는 자연어를 춤추는 인형으로 암호화 하여 범죄에 이용했다. 이 때 셜록홈즈가 이 문제를 아주 재미있게 푼다. 춤추는 인형이 마치 글자 처럼 연속성을 가지고 있다는 점을 홈즈가 알게되고 그는 인형 중 가장 많이 나온 것을 알파벳 'E'라고 눈치챈다. 그 이유는 영어에서 가장 출현 빈도가 높은 글자가 바로 'E'이다. 홈즈는 한 인형이 E라는 가정을 알게 되자 그 이후에 여러가지 가정을 통해 쉽게 암호를 풀게 되었다. 이처럼 우리가 사용하는 글자에는 분명 많이 사용하는 빈도가 있을 것이다. 영어 뿐만 아니..
트리 구조의 탐색 앞서 이분 매칭에서 배운 대로 매우 유리하다. 반면에 순회 방법은 조금 복잡하다. 일정 조건에 의해 설계된 트리 구조는 자식 노드에 대한 조건이 명확하다면 내가 원하는 값을 쉽게 찾아낼 수 있다. 하지만, 트리구조 전체를 탐색하게 된다면 얘기가 조금 달라진다. 모든 노드를 방문하기 위해서는 트리 구조를 탐색하는 일정 조건이 필요하다. 트리 구조를 유지보수하는데 있어 순회 방법에 대한 정의는 필수적으로 필요하다. 이번 시간에는 트리 구조의 순회 방법에 대해 한번 알아보도록하자. 순회 방법을 쉽게 알 수 있게 이진 트리라는 조건으로 알아보지만, 다른 트리 구조에서도 충분히 적용할 수 있다. 1. 전위 순회 (Pre-order Traversal) 전위 순회의 시작 점은 루트 노드이다. 루트 ..
얼마전 회사 업무를 진행하던 도중에 프로그램 하나에 문제가 생겨서 살펴보게 되었는데, 해당 프로그램의 Select 구문에 Binary Search가 적용되어서 문제가 생긴 적이 있었다. 우리가 알고리즘을 배우면서 효율적으로 문제를 푸는 방법에 대해 많이 살펴보게 되는데, 항상 효율성이 정답은 아니다. 이번에 배울 Binary Search Tree 역시 그렇다. 이를 적용하게 되면 일반적인 Search 보다 훨씬 효율적으로 문제를 풀 수 있지만 항상 이를 적용 한다고 옳은 것은 아니다. 1. Binary Search 란? 이진 탐색 트리(Binary Search Tree)를 알기 위해서는 우선 Binary Search에 대해알아야 한다. Binary Search는 알고리즘 보다는 자료를 저장하는 구조의 일..
카페에 와서 샌드위치 하나와 커피 하나를 마신다고 가정해보자. 이 카페에서 선택할 수 있는 커피는 총 5가지가 있고, 샌드위치도 총 5가지가 있다. 이 경우, 내가 구매할 수 있는 커피와 샌드위치 구매 쌍은 총 25개가 된다는 점은 쉽게 직관적으로 알 수 있다. 이 때, 몇가지 조건을 추가해보기로 하자. 만약 커피1과 샌드위치 1,2를 먹으면 할인이 가능하고, 커피 2는 샌드위치 1,3을 먹으면 가능하다. 이와 같이 5종류의 커피 모두 특정 샌드위치와 먹게되면 할인이 가능한 이벤트를 진행중이다. 당신은 이벤트가 가능한 세트 하나를 선택하려고 한다. 그렇다면 당신이 선택할 수 있는 세트의 개수는 총 몇개인가? 1. 최대 이분 매칭이란? 이처럼 2개의 집합으로 니누어저 있는 정점을 연결 할 수 있는 최대 개..
BFS와 더불어 탐색 알고리즘 중에서 많이 사용되는 것이 바로 '깊이 우선 탐색' 알고리즘이다. 너비 우선탐색이 Queue를 이용해 알고리즘을 구현했다면, DFS는 Stack을 이용해 구현하게 된다. 자신과 인접한 노드 하나를 선택하고, 해당 노드에 또 인접한 정점 하나를 계속 탐색하는 방식으로 탐색하게 된다. 쉽게 설명해 연결된 노드 끝까지 탐색하는 방식이다. 1. DFS Algorithm 방문 순서 DFS 알고리즘에서는 시작 노드와 인접한 모든 노드를 Stack에 쌓게 된다. 위와 같은 그래프 구조에서 한번 탐색하는 순서를 살펴보자. 시작 노드 1번에서 출발한다고 가정해보면 1번 노드와 인접한 2,3,4번 노드 중 가장 빠른 2번으로 이동하게 되고 Stack에 1번 노드와 인접한 노드인 2, 3, 4..
이번 시간에는 탐색 중에서 대표적 알고리즘인 BFS(Breadth First Search)에 대해 알아보도록하자. DFS와 더불어서 프로그래밍 문제를 푸는데 정말 많이 쓰이게 되는 알고리즘이다. 트리구조로 구성된 노드를 탐색할 때 자신을 기분으로 주변에 있는 노드를 모드 검색하는 방법이다. 따라서 너비 우선 탐색이라고 하고, 반대되는 개념인 깊이 우선 탐색은 연결된 끝까지 탐색을 하는 방식이다. 1. BFS Algorithm 방문순서 너비 우선 탐색은 시작 노드로 부터 연결된 모든 노드를 Queue에 넣고 다음 노트를 선택하는 방식이다. 이 과정을 반복하면서 계속 다음 노드를 선택한다. 아래 예시를 보면서 설명하도록 하자. 시작 노드를 1번이라고 하면 Queue에 2, 3, 4번 정점을 넣게 된다. 그 ..
Iterative Improvement은 최적의 해답을 찾는 알고리즘 중 하나이다. 기본적인 문제 풀이의 원칙은 '현재 가능한 솔루션에서 좀 더 나은 솔루션으로 개선해 나가는 것'이다. 점진적인 개선 활동을 통해 최적의 해를 찾아내는 것이 Iterative Improvement의 핵심이다. Iterative Improvement의 대표적인 방법은 선형 계획법(LP, Linear Programming)이다. 선형 계획법에 대해 자세히 알아보자. 1. 선형계획법 (Linear Programming) 대학교 전공떄 계량분석론을 한번이라도 들어본 경험이 있다면 매우 쉽게 그 개념을 이해할 수 있을 것이다. 혹은 중학교때 배운 연립방정식을 배운 적이 있을 것이다. 이 두가지 문제가 일종의 선형계획법이다. 아래의 ..
이번 시간에는 두번째 그리디 알고리즘에 대해 배워보도록 하겠습니다. 지난 시간에 배웠던 알고리즘과 매커니즘 자체가 크게 차이가 나지 않으므로 각 알고리즘의 차이점에 대해 분석하면서 공부하는 것이 중요할 것입니다. 각각의 알고리즘의 풀이 순서와 결과 값이 매우 유사하므로(특히 그래프의 크기가 작다면) 차이점에 대해 더욱 주의깊게 살펴보아야 합니다. 1. 솔린 알고리즘 (Solin’s Algorithm) 솔린 알고리즘은 한번의 단계에서 여러개의 간선을 선택하여 최소 신장 트리를 만들게 됩니다. 간선을 선택하는 기준은 다음과 같습니다. 1번 정점부터 다른 정점으로 연결되는 간선들 중 최소 간선을 선택한다.중복된 선택은 제외한다.모든 정점들이 연결된 하나의 트리로 완성되거나, 더이상 선택할 간선이 없을때까지 반..
Greedy 알고리즘으로 많이 불리는 탐욕 알고리즘 역시 매우 자주 사용되는 알고리즘 중 하나입니다. Greedy알고리즘은 주로 최적화 문제에서 사용되고, 최적화 문제의 대표적 알고리즘 입니다. 이름에서도 알 수 있듯이 미래를 예측하지 않고, 순간마다 최선의 선택을 하는 방법입니다. 동적 프로그래밍의 경우가 데이터를 저장하고 문제를 풀어나가며 지속적으로 데이터를 참조합니다. 따라서, 매우 많은 동작이 발생합니다. 그렇기 때문에, 미래를 굳이 확인하지 않아도 직관적으로나, 논리적으로 현재의 선택이 최적화가 된다고 생각 될 때, 사용되는 알고리즘 입니다. Greedy알고리즘의 최대 장점은 무엇보다도 빠르다는 것이며, 단점은 항상 최적화 되지 않는 다는 점입니다. 매번 최선의 선택을 해나가기에 문제를 푸는데 ..