Adrian's Web Page

이번이 드디어 알고리즘 마지막 시간이다. 마지막 답게 아직 풀리지 않고 있는 알고리즘에 대해 소개하는 시간을 갖겠다. 근사 알고리즘이라는 말에서도 알 수 있듯이 해당 알고리즘들은 아직 풀리지 않고 있기에 정확한 해를 구하지 못해 최대한 근사한 해를 구하는 방법을 알아내는 것이다. 수학 혹은 컴퓨터공학에서 가장 유명한 밀레니엄 문제 중 하나 인 P-NP 문제에 대해 소개하고 대표적인 NP 문제에 대한 코딩을 해보며 마지막 알고리즘 포스팅을 마쳐볼까 한다. 필자가 어릴적에 했던 재밌는 게임 중에서 '한붓그리기' 게임이 있었다. 그 게임은 간선과 정점으로 이루어진 그래프가 주어졌을 때, 각각의 간선을 딱 한번씩만 방문해서 모든 정점을 방문 할 수 있는 경로를 찾는 게임이었다. 이를 이산수학에서 오일러 회로 (..

베네수엘라에 전운이 감돌고 있다. 요즘 워낙 별의별 국내 문제가 많이 터지고 있어 많은 사람들이 해외 이슈에는 신경쓰지 못하고 있는 것이 사실이다. 그래도 지금 관심있게 지켜볼 필요가 있는 나라가 있는데 바로 베네수엘라이다. 지난 1월 11일 베네수엘라의 대통령이었던 니콜라스 마두로의 두번째 임기가 시작되었는데, 이와 동시에 베네수엘라가 두 쪽으로 갈라지게 되었다. 믿기 어렵겠지만 지금 베네수엘라는 대통령이 두명이다. 대부분의 남미 지역들이 그렇듯이 베네수엘라 역시 반미감정이 심한 나라 중 하나다. 베네수엘라의 전임 대통령이자 독재자였던 우고 차베스는 베네수엘라 국내에 깊이 존재했던 반미감정을 이용해 오랜 기간 대통령을 역임했다. 전형적 포퓰리스트였던 차베스는 민심 자극에는 소질이 있었으나, 정치능력은 ..

어릴적 셜록 홈즈 소설을 읽었는데 '춤추는 인형'을 참 재밌게 읽은 기억이 난다. 이 춤추는 인형도 일종의 암호화 였다. 우리가 사용하는 자연어를 컴파일 가능한 기계어로 바꾸듯이, 셜록홈즈의 춤추는 인형에서는 자연어를 춤추는 인형으로 암호화 하여 범죄에 이용했다. 이 때 셜록홈즈가 이 문제를 아주 재미있게 푼다. 춤추는 인형이 마치 글자 처럼 연속성을 가지고 있다는 점을 홈즈가 알게되고 그는 인형 중 가장 많이 나온 것을 알파벳 'E'라고 눈치챈다. 그 이유는 영어에서 가장 출현 빈도가 높은 글자가 바로 'E'이다. 홈즈는 한 인형이 E라는 가정을 알게 되자 그 이후에 여러가지 가정을 통해 쉽게 암호를 풀게 되었다. 이처럼 우리가 사용하는 글자에는 분명 많이 사용하는 빈도가 있을 것이다. 영어 뿐만 아니..

트리 구조의 탐색 앞서 이분 매칭에서 배운 대로 매우 유리하다. 반면에 순회 방법은 조금 복잡하다. 일정 조건에 의해 설계된 트리 구조는 자식 노드에 대한 조건이 명확하다면 내가 원하는 값을 쉽게 찾아낼 수 있다. 하지만, 트리구조 전체를 탐색하게 된다면 얘기가 조금 달라진다. 모든 노드를 방문하기 위해서는 트리 구조를 탐색하는 일정 조건이 필요하다. 트리 구조를 유지보수하는데 있어 순회 방법에 대한 정의는 필수적으로 필요하다. 이번 시간에는 트리 구조의 순회 방법에 대해 한번 알아보도록하자. 순회 방법을 쉽게 알 수 있게 이진 트리라는 조건으로 알아보지만, 다른 트리 구조에서도 충분히 적용할 수 있다. 1. 전위 순회 (Pre-order Traversal) 전위 순회의 시작 점은 루트 노드이다. 루트 ..

무능한 지휘관은 유능한 적보다 더 무섭다. 수많은 전쟁 역사를 살펴보면 무능한 지휘관이 아군을 패전의 수렁 속으로 집어 넣은 경우가 참 많다. 지휘관의 멍청함 속에 많은 수많은 장병들이 죽거나 다치게 된 경우다. 군대 비속어 중 하나인 주적은 간부다라는 말이 괜히 나온게 아니다. 이 무능한 지휘관들이 국가와 군대에 얼마나 많은 피해를 주었는지 알게되면 정말 피가 거꾸로 솟게 된다. 그들을 믿고 따랐던 젊은 병사들과 그들의 가족들을 생각하면 너무 가슴아픈 일이다. 그래서 오늘은 한중일을 대표하는 가장 무능했던 지휘관 3명을 소개해볼까 한다. 한명씩 그 면면을 자세히 살펴보도록 하자. 무타구치 렌야 - 임팔 작전 세계 2차대전에서 무능한 지휘관은 참 많았지만 그 중에 최고봉은 단연 이분이 아닐까 한다. 바로..

얼마전 회사 업무를 진행하던 도중에 프로그램 하나에 문제가 생겨서 살펴보게 되었는데, 해당 프로그램의 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개의 집합으로 니누어저 있는 정점을 연결 할 수 있는 최대 개..

1990년 3당합당은 대한민국 정치사에 큰 영향을 줬다. 전국 정치 구도는 호남과 비호남으로 나뉘게 되어 호남 진영은 지지세가 크게 약화 되었다. 여당인 민주자유당은 다음 대선도 손쉽게 승리할 것이라고 예상되었다. 하지만, 대선 직전에 치러진 14대 국회의원 총선거에서 민자당은 예상치 못한 일격을 당하게 된다. 당시 정주영 회장이 대통령 출마를 선언하고 통일국민당을 창당했는데, 제3정당인 이 당이 무려 득표율 17.4%로 약진했고, 민자당은 한자리가 부족하여 과반 의석에 실패하게 되었다. 만에 하나 통일국민당과 민주당이 단일화 하게 된다면 민자당 세력에 대등하다는 것이 수치 상으로 증명이 된것이다. 민자당은 다행스럽게도 TK지역에서 탈당한 일부 무소속 위원들이 복당을 하며 과반의석 유지는 가능해졌지만, ..

가끔 생각해보면 대부분의 보통 남자들은 참 간사한 것 같기도 하다. 좋아하는 여자에게 고백할 때 남자들은 세상 모든것을 사랑하는 여자에게 준다고 약속을 한다. 간신히 여자의 마음을 붙잡지만, 시간이 지날수록 남자들은 바쁜 일상 속에서 애인에게 점점 소홀하게 된다. 연락 빈도가 줄어들고 여자친구가 아닌 타인과 보내는 시간의 비율을 늘리게 된다. 다른 여자와 자신의 여자친구를 비교하기도 하고 내 상황에서 더 좋은 사람을 만나지 않을 거라는 기대를 한다. 처음 고백하는 순간 말한 다짐은 온데간데 없이 사라진다. 이렇게 연인들은 이별을 겪게 된다. 처음 사랑을 고백했을 때의 다짐은 사라진 채 둘은 각자의 길로 떠나게 된다. 2. 삼국지의 조조가 유비에게 주인공을 빼앗긴 이유 중 하나는 그의 태도 변화에 있을지도..

BFS와 더불어 탐색 알고리즘 중에서 많이 사용되는 것이 바로 '깊이 우선 탐색' 알고리즘이다. 너비 우선탐색이 Queue를 이용해 알고리즘을 구현했다면, DFS는 Stack을 이용해 구현하게 된다. 자신과 인접한 노드 하나를 선택하고, 해당 노드에 또 인접한 정점 하나를 계속 탐색하는 방식으로 탐색하게 된다. 쉽게 설명해 연결된 노드 끝까지 탐색하는 방식이다. 1. DFS Algorithm 방문 순서 DFS 알고리즘에서는 시작 노드와 인접한 모든 노드를 Stack에 쌓게 된다. 위와 같은 그래프 구조에서 한번 탐색하는 순서를 살펴보자. 시작 노드 1번에서 출발한다고 가정해보면 1번 노드와 인접한 2,3,4번 노드 중 가장 빠른 2번으로 이동하게 되고 Stack에 1번 노드와 인접한 노드인 2, 3, 4..