Adrian's Web Page

이번에는 조금 더 어려운 이야기를 해보자. 이번 시간에는 그래프에 대한 지식이 살짝 필요하니 모르시는 분들은 미리 사전 학습을 해보시는 걸 추천합니다.(그래프 위키 백과 : https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84) 임의의 그래프에서 최단거리를 구하는 방법을 알아 보자. 최단거리 문제를 푸는 대표적인 2가지 방법은 다익스트라 알고리즘과, 워셜-플로이드 알고리즘이 존재한다. 1. 다익스트라 알고리즘 (Dijkstra algorithm) 다익스트라 알고리즘을 적용하기 위해선 아래의 조건을 만족하는 그래프여야한다.음의 가중치를 가지는 edge가 있어서는 안된다. 다익스트라 문제를 풀기 위해 아래와 같은 그래프를 예시로 들어 문제를 해결하자. 위 그..

해당 책을 읽은지는 꽤 되었지만, 책을 읽으면 독후감을 반드시 쓴다는 나 자신과의 약속을 했기 때문에 늦게나마라도 독후감을 쓴다. 이 책은 매우 정치적 성향을 크게 띄고 있는 책으로 생각되기 쉽지만, 막상 읽어보면 그렇지 않다. 두 사람은 정치성을 배제하고 이야기를 하려고 노력한다. 사건에 대한 가치 판단은 독자에게 맡기고, 함세웅 신부님은 자신이 겪었던 일들에 대해서 말하고 주진우 기자는 자신이 아는 사실에 대해서 소개한다. 물론, 자신들이 판단하는 사건에 대한 평가도 일부 드러내기도 한다. 하지만, 누구든지 하나의 현상을 소개하면서 자신의 생각을 드러내지 않고 말하는 일은 정말 쉽지 않다. 학창시절 역사시간으로 돌아가보더라고 그렇다. 역사선생님의 목적은 교과서에 나온 역사적 사건들에 대해 설명하는게 ..

프로그래밍 문제해결에서 가장 많이 쓰이는 코딩 스킬 중 하나인 "동적 계획법(Dynamic Programming)"에 대해 알아볼 시간이다. 이름에서 알 수 있듯이 알고리즘이 아는 프로그래밍 방법이라고 생각하면 좋다. 하지만, 알고리즘 시간에 소개하는 이유는 워낙 많이 쓰이기도 하고, 앞서 배웠던 Conquer 알고리즘의 응용 버전이기 때문이기도 해서 이번 시간에 소개를 할 생각이다. 우리 모두 피보나치 수열이 무엇인지는 알고 있을 것이다. 피보나치 문제를 푸는 가장 좋은 방법은 반복해서 풀어낸다. 코드로 작성하기도 매우 쉽고 직관적으로도 이해가 잘 된다. 피보나치 수열을 recursive 하게 풀어낸다면 아래와 같은 코드를 작성하게 될 것이다. 12345678910111213141516171819202..

내가 옳다고 생각하는 일을 소신껏 밀고 나가는게 참 힘들다는 걸 요즘 많이 느낀다. 서로 충돌하는 이해 관계 속에서 누가 맞고 틀린지 참 알수없다. 정의란 무엇인가라는 책에서는 상황에 대한 여러 가정을 두고 어느 쪽이 옳은 방향인가 제시를 한다. 그런데 세상은 훨씬 더 복잡하다. 책 속에서의 가정은 이미 존재하지 않고 누가 옳은 길인지 더욱 모르겠다. 심지어 때론 나의 주관마저 흔들린다. 지난 2년 사이 나는 너무나도 많은 사람을 만났다. 내가 지낸 학교라는 우물 안은 정말 좁았다. 학교 그것도 같은 전공 내에 있는 사람끼리는 비슷한 가치관이 형성되어 있었고 그 속에서 다름을 찾기 어려웠다. 하지만 내가 2년 사이 만난 사람들은 각자의 개성이 뚜렸했고, 가치관도 제각각 이었다. 적당히 학교에서 프로젝트하..

1947년 제주도에서 삼일절 행사가 한창 진행되고 있었다. 이날 행사에는 제주도 민들이 가두 시위를 하고 있었기 때문에, 경찰 병력도 꽤나 존재했다. 미군정 산하의 대한민국이었기에 소수의 미군도 존재했다. 이러던 와중 사건 하나가 발생했다. 한 기마 경찰이 지나가고 있었는데 아이를 밟고 지나쳤다. 하지만 해당 경찰은 이를 눈치채지 못하고 그대로 지나가게 되았다. 그러자 이 광경을 지켜보던 몇몇 시민이 분노를 했고, 해당 경찰을 깜짝 놀라 도망가게 되었다. 시민들 역시 해당 경찰을 돌을 던져가며 쫒아가게 된다. 그러자 경찰서에 있던 경찰관들이 해당 경찰을 위협한다고 판단했고, 시민들에게 총을 쏘기 시작했다. 그 결과 시민 6명이 사망했고, 6명이 중상을 입게 되었다. 양 쪽의 오해로 인해 발생된 이 작은 ..

앞서 배운 Space-time trade off 알고리즘의 응용해여 장문에서 특정 문자열을 찾는 프로그램을 구현해보자. 보기가 되는 텍스트를 보고 내가 찾고자 하는 단어가 몇번째에 행에 나오는지 찾는 과정이다. An automaton is a self-operating machine or a machine or control mechanism designed to automatically follow a predetermined sequence of operations, or respond to predetermined instructions. 위 문장은 영문 위키백과에 나온 오토마타(자동기계)에 관한 정의이다. 위 텍스트에서 우리가 찾고자 하는 단어는 sequence이다. 이 단어를 아래 알고리즘들이 ..

앞선 시간에 리스트 안에 있는 데이터의 개수를 구하는 방법에 대한 알고리즘을 배워보았다. Brute Force 방식을 이용해 O(n^2) 시간 복잡도를 가지는 알고리즘을 배웠고, Transform & Conquer를 이용하여 미리 정렬을 수행한 다음 차례대로 그 숫자를 읽는 방법에 대해 배웠다. 두가지 방법보다 더욱 쉽게 데이터 안에 있는 숫자들의 개수를 구하는 방법이 있다. A = {5, 2, 7, 5, 4, 1, 2, 3} 다음과 같이 총 8개의 자료가 존재한다고 하고 리스트 안에 있는 최소값과 최대값이 1과 7이라는 사실을 알고 있다고 가정하자. 그렇다면 공간 7개를 가지는 별도의 리스트를 만든다. (Ex. B[7]의 리스트 생성) 그리고 인덱스 0부터 7까지 있는 해당 배열에 A를 탐색하며 해당 ..

1부터 100까지의 숫자 중 특정한 숫자 하나를 찾는 방법은 무엇이 있을까? 가장 간단하고 정확한 방법은 찾으려는 1부터 100까지 숫자를 각각 비교해나가는 방법이다. 조금 무식하고 오래 걸리는 방법이긴 하지만 더 정확한 방법은 없다. 특히 숫자가 배열 구조로 저장되어 있다면 이런 방법을 사용할 수 밖에 없다. 이 구조를 이진 트리 구조로 바꿔보자. 최상위 노드에 중앙 값인 50을 넣고 그 아래는 각 서브트리에 해당하는 중앙 값은 25와 75를 차례대로 기록한다. 이런 방식으로 1부터 100에 대한 숫자를 이진 트리로 바꿔 저장되어 있다고 생각해보자. 찾으려는 숫자를 50과 비교하여 크다면 75서브트리로, 50보다 작다면 25서브트리로 내려간다. 이런 방식으로 숫자를 찾게 된다면 단 7번의 비교로도 원하..

독일의 천재 수학자 가우스는 초등학교 시간에 1부터 100까지의 숫자를 모두 더하라는 선생님의 질문에 계산을 순식간에 끝냈다고 한다. 1부터 100의 숫자는 등차수열로 연속된다. 따라서 1과 100, 2와 99, 3과 98이 서로 짝지어져 있고, 이 계산이 총 50번 반복되는 구조를 갖는다. 따라서 101 * 50이라는 단 한번의 연산으로 1부터 100까지의 모든 합계를 구해냈다. 이 공식은 나중에 등차수열의 합계를 구하는 기본 공식이된다. 이 처럼 1부터 100까지 더하는 문제를 두개씩 짝지어 풀어야 되는 부분은 50개로 나눈다면 쉽게 풀어낼 수 있다. 이처럼 일정한 문제를 동일한 크기의 n개로 나누어 푸는 방식을 분할 정복 알고리즘 (Divide and Conquer)라고 한다. 분할 정복 알고리즘은..

in dubio pro reo 형사피고인은 유죄의 판결이 확정될 때까지는 무죄로 추정된다. 대한민국 헌법 제 27조 4항 내가 이 문구를 참 좋아하게 된 계기는 어릴 적 경험에서 비롯되었다. 초등학교 6학년이었던 나는 당시 매우 조용한 성격이었다. 그에 반해 당시 담임 선생님은 초등학교 교사 답지 않게 매우 무섭고 괄괄한 성격이셨다. 내가 초등학교를 다니던 시절에는 항상 학생들에게 어린이 신문을 한 부씩 나눠 주었다. 수업을 듣고 있던 중 선생님께서 사물함 위에 버려져 있는 신문을 발견하셨다. 화가 난 담임 선생님은 이 신문을 버린 학생이 누군지 찾기 시작했다. 담임 선생님은 신문을 모두 꺼내 보라고 하셨는데 미리 신문을 쓰레기통에 버린 나는 신문을 가지고 있지 않았다. 나와 딴 한 친구만 신문이 하필 ..