앜스토리 | 호기심 많은 개발자의 보물창고

재귀라는게 말로는 쉬운데 깊이 이해하기가 참 어려운 것 같다. 그래서 포스팅좀 해볼라고... 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을... 재귀함수(再歸函數)는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 재귀는 큰 문제의 풀이법을 작은 문제의 같은 풀이법으로 구성할 수 있을 때 사용되는 문제 해결 기법이다. 재귀를 사..

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 0을 출력하고, 0을 리턴한다. fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다. 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다. fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다. 1은 2번 출력되고, 0은 1..

알고리즘 문제 푸는데 위치관계에 대한 이해가 필요한 것 같아 포스팅한다. 공부하는 겸... 아 정말이지 세상 쉬운거 하나 없다 이럴 때 후회되는 건 어릴 때 수학공부나 열심히 해둘 걸... 하지만 지금 후회해봤자 무슨 소용인가 지금 열심히 할 수 밖에 없는 듯... 두 원의 위치관계 원과 원의 사이의 거리는 두 원의 중심사이의 거리(중심거리)를 이용하고, 두 원의 반지름은 모두 이용한다. 정확히 말하면 반지름의 합과 차를 이용한다는 것이다. 두 원을 각각 O, O'이라고 해보자. 그리고 원 O의 반지름을 r, 원 O'의 반지름을 r', 두 원의 중심사이의 거리를 d라고 해보자. 두 원의 위치관계 - 두 점에서 만나는 경우 첫 번째로 두 원이 두 점에서 만나는 경우가 있다. 원이 두 점에서 만난다는 얘기는..

벨만-포드 알고리즘은 Richard E. Bellman(리처드 E 벨먼)과 Lestor Ford Junior(래스터 포드 주니어)의 이름에서 따온 알고리즘이다. 벨먼은 알고리즘의 중요 분야인 동적 계획법을 고안한 사람이기도 하다. 이 알고리즘은 그래프의 최단 경로 문제를 해결하기 위한 알고리즘이다. 모든 간선에 대해 가중치를 계산, 갱신해가며 가중치가 변경되지 않을 때까지 처리를 반복한다. 이 알고리즘을 해석해보자. 위 그래프는 똑같이 벨만 포드 알고리즘의 모습이다. 이 것을 파헤쳐보고자 한다. 먼저 초기 비용 값이 각 포인트에 할당된다. 모서리 중 하나가 선택된다. 편의를 위해 A-B 모서리를 선택했다. 끝점에서 끝점까지의 각 순회 비용이 발생하고, 선택한 모서리에서 계산된다. 계산은 초기 포인트의 비..

대부분의 프로그래밍 언어에서 인덱슨느 보통 1이 아닌 0에서 시작하는 경우가 많다. 그 이유는 무엇일까? 네덜란드의 유명한 컴퓨터 과학자인 다익스트라(Dijkstra, 1930-2002)는 이에 대한 제안서를 작성했다. 이 내용을 요약하면 다음과 같다. 먼저 수학에서 수의 구간을 표현하는 방식에는 다음과 같은 4가지 방법이 있다. - 열린 구간 - 닫힌 구간 - 반열린 구간 - 반닫힌 구간 예를 들어 2에서 12까지의 정수를 표현하는 방식은 다음과 같다. ① 1 < n < 13 ② 2 ≤ n ≤ 12 ③ 1 < n ≤ 12 ④ 2 ≤ n ≤13 다익스트라는 이 4가지 방법중 시작은 닫힌 구간, 끝은 열린 구간으로 표현하는 것이 좋다고 얘기했다. 즉 ④번 방식을 말하고 있다. 그 이유는 첫째, 각 구간의 ..

알고리즘의 성능은 시간 복잡도(Time complexity)와 공간 복잡도 (space complexity)로 표현한다. 시간 복잡도는 입력 값의 개수와 처리 시간과의 관계를 표현하고, 공간 복잡도는 입력 값의 개수와 메모리 증가량과의 관계를 표현한다. 시간 복잡도는 입력 값의 개수와 알고리즘의 처리 시간과의 상관관계를 표현한 말로 입력 데이터의 양이 많아짐에 따라 처리 속도가 어떻게 변화하는지를 수학의 기호를 빌려 표현하는 방식이다. 쉽게 생각해서 수학의 방정식을 떠올리면 된다. x축을 입력 값의 개수로 놓고 y축을 처리 시간으로 봤을 때, x가 증가함에 따라 y가 어떻게 변화하는지를 표현하는 것이다. x와 y가 일정한 비율로 증감한다면 선형(linear) 시간 복잡도를 가진다고 표현하며, 지수나 로그..

혼자서 공부를 하다가 알고리즘의 학습법에 대해 고민을 해보았다. 너무 어려워도 어려운 것이다. 제일 단순하고 쉬운 알고리즘이 입력된 문자열을 모두 나열한 다음 거기서 해당 문자열을 골라내라는 것이다. 그런데 처음 접하는 사람들이 이것을 어떻게 풀 수 있을까? 결론만 말하면 무한 연습 뿐이다 진짜 공부하는거 옛말이 별 거 없다. 그냥 오로지 이론 학습하고 연습하고 실전을 통해서 몸에 익히는 수밖에 없다. 아니 이럴거면 왜 글 썼냐고? 나에게 상기시키기 위해서... 당일엔 언제나 의기와 화이팅이 넘치나 하루가 지나고 이틀이 지나면 망각 해버리는 게... 매일 같이 글을 쓰면 좀 나아지려나 싶어서 작성해본다 허허... 모든 문제에는 사실 해결하는 방법이 있다. 예를 들면 수도권 지하철에서 영등포에서 출발해서 ..