책 <누워서 읽는 알고리즘>

임백준

1. 기억하고 싶은 문장들

1장. 재즈

• 요즘 시대에 개발자에게 가장 중요한 능력은 특정 언어와 프레임워크로 개발하는 능력이 아니라 새로운 개념과 언어를 빠르게 배우는 능력이다. 그리고 이러한 능력의 기반이 되는 것은 바로 알고리즘이다.

• 눈이 빨간 승려 문제

  • N명의 승려가 있다면, N번째의 날에 모두 다같이 죽게 된다.

• 이진트리와 재귀함수

  • 빨간 승려 문제도 사실은 재귀함수로 풀 수 있는 문제가 된다.

• 모리츠 코르넬리스 애셔의 <그리는 손>

  • P를 출력하는 프로그램 P : 자기 자신의 소스코드를 출력하는 프로그램을 만들기

• 헝클어 놓은 실타래를 하나씩 푸는 문제

  • 예) 서로 다른 색, 나라, 음료, 담배, 애완동물을 가지고 있는 사람들을 유추해내는 문제

  • 제한 시간은 3분이나 나는 38분이나 걸렸다 ㅠㅠ

• 프로그래머가 작성해놓은 코드와 그 속에 담긴 알고리즘을 통해 그 프로그래머의 성향, 개성 및 실력을 유추할 수 있다.

• 주어진 문제에 대해서 적절한 알고리즘을 생각해내는 것은 하루아침에 되지 않는다. 평소에 꾸준한 훈련을 해야 가능한데, 이러한 훈련은 컴퓨터 앞에서 앉아있다고 되지 않는다. 영화도 보고, 전시회도 가고, 술도 마시고 연애도 하는 열정적인 사람이어야만 그것이 가능하다. 진정한 상상력은 삶의 속살을 이해할 때 비로소 풍부해지기 때문이다.

• 1부터 100까지의 수를 모두 더한 값 구하기 → 가우스

• <가우스> 99개의 값을 저장할 수 있는 배열에 1부터 100개의 수를 무작위로 넣는다. 배열에 저장되지 않은 한 가지의 수를 구하는 방법을 말하라

  • 1부터 100까지 모두 더하면 5050이므로 배열의 값을 모두 더한 다음 5050에서 빼면 배열에 들어가지 않은 하나의 숫자가 나오게 된다.

• <펠린드롬 알고리즘> 앞으로 읽으나 뒤로 읽으나 똑같은 단어를 회문 혹은 펠린드롬이라고 한다. 입력된 단어가 펠린드롬이면 true, 아니면 false 를 반환하는 프로그램을 작성하라

  • 단어의 길이를 체크한다.

  • 길이가 2보다 작으면 오류 메시지를 내보낸다.

  • 단어의 길이만큼 2로 나누어, 체크할 마지막 인덱스를 구한다.

  • 해당 인덱스만큼 반복하여 단어의 양 끝 인덱스의 문자를 비교한 뒤, 같으면 참, 다르면 거짓을 반환한다.

  • 이 알고리즘을 수행할 때 주목할 점은 for 문을 이용하여 양 끝의 문자를 비교할 때, length-1-index 와 같은 연산을 반목문 내에서 수행할 경우, 매 반복마다 불필요한 연산이 발생하므로, 해당 연산은 for 문 밖에서 처리하는 것이 성능 면에서 좋다는 것이다.

• 펠린드롬에 대한 흥미로운 수학적 관찰, 그루엔버거 알고리즘

  • 결국 모든 수는 펠린드롬으로 귀결된다.

  • 아무 숫자나 고른 뒤, 그 숫자를 뒤집고 두 수를 더한다. 그 수가 펠린드롬이 아니라면 다시 그 수를 뒤집고 더한다. 이 과정을 반복하면 반드시 펠린드롬이 발생하게 된다.

  • 하지만 숫자 196에 대해서는 아직까지 펠린드롬을 발견하지 못하였다. 무려 7천만개의 숫자까지 실험이 진행되었지만, 아직까지 펠린드롬을 발견하지 못했다.

• <콤웨이 둠스데이 알고리즘> 2199년 7월 2일은 무슨 요일인가

  • 둠스데이 교수는 프린스턴 수학과 교수임. “인생게임”의 창시자로 알려져 있음

  • 최초로 달력을 만들 때, 이집트 천문학자들은 1년을 365일로 하고, 4년마다 한번씩 하루를 더하는 알고리즘을 처음으로 만들었다.

  • 위의 알고리즘에도 버그가 존재하여 교황 그레고리 13세 때 새로운 세기가 시작될 때(100으로 나누어 떨어지는 해에) 400으로 나누어 떨어지지 않는 해는 윤년으로 치지 않기로 하는 알고리즘을 추가했다.

    • 예를 들면 아래와 같다.

      • 1900 : 4로 나누어 떨어지고, 400으로는 떨어지지 않으므로 그레고리 알고리즘에 따르면 윤년이 아니다.

      • 2000 : 4로도, 400으로도 나누어 떨어지므로 윤년이다.

      • 2100 : 4로는 나누어 떨어지지만, 400으로는 나누어 떨어지지 않으므로 윤년으로 치지 않는다.

  • 즉 윤년은 4로도 나누어 떨어지고, 그 세기의 시작이 400으로도 나누어 떨어지는 해일 것이다.

  • 둠스데이 알고리즘은 윤년을 기준으로 요일을 계산하는 알고리즘이다. 이때 둠스데이는 평년의 경우 2월 28일, 윤년의 경우는 2월 29일이 된다.

  • 요일은 7을 기준으로 순환한다. 따라서 둠스데이로부터 7일을 거슬러 올라간 날짜는 항상 둠스데이와 요일이 같게 된다. 이때, 둠스데이와 요일이 같을 수 밖에 없는 날짜를 미리 기억해두면 빠른 계산에 도움이 된다.

    • 04/04, 06/06, 08/08, 10/10, 12/12, 09/09, 05/09, 07/11, 11/07, 03/07

  • 100으로 나누었을 때, 윤년이 아닌 해를 미리 표시해둔다. 그에 따르면 2199년에는 목요일이 둠스데이이다. 위의 날짜 리스트에 따르면 2199년 7월 11일 역시 둠스데이와 같은 목요일이 되고, 그 전주인 2199년 7월 4일 역시 목요일이 된다. 따라서 2199년 7월 2일은 화요일이다.

2장. 록

• 정렬 알고리즘

  • 기본중의 기본이지만 가장 중요하다.

  • sorting 은 사실 ordering 에 더 가깝다.

• 퀵정렬

  • 토니 호어가 60년대에 발명한 매우 간단하고 아름다운 정렬 기법. 재귀를 토대로 만들어졌다.

  • 작업과정

    • 기준점 x를 하나 고른다.

    • 리스트1에서는 기준점보다 작은 것을 넣고, 리스트2에는 x를, 리스트3에는 x보다 큰 것을 넣는다.

    • 리스트 1과 리스트 3을 각각 다시 퀵소팅한다.

    • 그리고 리스트 1, 리스트2, 리스트3을 순서대로 합치면, 정렬 완료!

  • 가장 중요한 것은 기준점 x를 잘 고르는 것이다. x를 잘 고르려면 가운데 지점을 적절하게 골라야 하는데, x가 최저점이나 최고점일 경우, 나머지 리스트만 계속 재귀가 호출되므로 매우 비효율적이게 된다.

  • 적절한 x를 찾는 것이 가장 중요하기 때문에, 퀵정렬에 대한 변형 알고리즘도 등장한다.

• 알고리즘을 공부할 때에는 핵심적인 방법론만 이해하고 껍데기는 버리는 것이 좋다. 이해한 뒤에는 그 알고리즘이 정말 최선인지 의심을 하는 과정이 필요하다.

• <문제> 정수 array 가 주어지는데 이 배열이 순서대로 정렬되어있다면 1을, 아니면 0을 리턴하는 함수를 작성하라

  • 반복문을 작성하여 현재 요소가 다음 요소보다 크면 곧바로 0을 리턴하고, 그렇지 않고 반복문을 끝까지 완료하면 1을 리턴하도록 작성한다.

  • 하지만 이 알고리즘이 최선인가? 늘 고민하고 의심해봐야한다.

• 검색 알고리즘과 최적화 문제

  • 정렬과 검색은 늘 붙어다닌다. 효율적인 정렬은 검색을 필요로 하는 경우가 많고, 효율적인 검색은 정렬을 필요로 한다.

• <문제> 집합A가 집합B의 부분집합인지 여부를 확인하기 위한 알고리즘을 작성하라

  • 나의 답안

    • 집합 A의 요소들을 하나씩 뽑아 집합 B의 요소들과 하나씩 비교해본다. 이때, A의 요소를 포함하지 않는 경우가 한 건이라도 있다면 바로 false 를 리턴한다.

  • 좀 더 괜찮은 답안

    • 집합A와 집합B를 각각 정렬한다.

    • 집합 A의 첫 요소가 집합 B에서 존재하는 index를 확인한다. 이제 집합 A의 2번째 요소부터는 index 이후부터 탐색하면 된다. 탐색의 범위가 훨씬 줄어드는 것이며 각 집합의 요소를 한번씩만 스캔하면 된다.

• 이진트리검색

  • <문제> 63층 빌딩에서 떨어진다고 했을 때, 떨어지면 죽지 않을 층 중 최고층은 어디일까. 5번은 떨어져도 다시 살아날 수 있지만, 그 이상은 영혼을 잃게 된다. 5번 안에 맞추면 온 세상을 갖을 수 있다.

    • 이진트리검색을 이용하면 5번 안에 맞출 수 있다. 답이 17층이라고 한다면, 아래와 같은 순서로 탐색할 수 있다.

      • 64/2=32층 (죽는다) → 32/2=16층 (산다) → 24층 (죽는다) → 20층 (죽는다) → 18층 (죽는다)

      • 답은 17층이 된다.

• 다양한 검색 알고리즘

  • B트리, B+/-트리, 해싱, 문자열 내부의 패턴 검색하는 스트링 매칭 알고리즘, KMP 알고리즘, 보이어-무어 알고리즘, 래빈-카프 알고리즘

  • 그래프에서 경로찾는 문제 또한 경로를 찾는 것에 해당한다.

  • 네이버, 구글 등의 검색 알고리즘

• 결국, 알고리즘은 가독성과 효율성에 대한 고민이며 이는 최적화 과정에 의해 달성된다. 하지만 동적알고리즘의 경우, 이러한 최적화 과정에 의해 달성되기 어렵다.

• 동적 프로그래밍

  • 피보나치 알고리즘

    • 1170년 이태리의 수학자 레오나르도 피사노의 별명인 피보나치를 따라 붙여진 이름. 이전 수와 현재수를 더하여 다음수를 구하는 방식의 수열을 의미한다.

    • 하지만 피보나치수열은 과연 최선인가?

    • 성능적으로 볼 때 피보나치 알고리즘은 for나 while 루프를 돌리는 것이 더 빠르고 효율적이지만 미학적으로 보았을 때에는 재귀함수를 쓰는 것이 더 간결하다. 성능과 미학이 반드시 일치하지는 않는다.

  • 알고리즘의 효율성을 향상시키기 위해서 알고리즘의 수행 도중에 계산한 결과를 테이블 같은 곳에 저장해 두었다가 재활용 하는 기법이다. 하지만 이용하는 것이 까다롭다.

  • 활용 예시

    • 행렬의 곱셈을 수행하는 계산, 이진트리, 최단경로찾기 등을 최적화하기

    • 이론적 알고리즘의 성능개선

• 해시 알고리즘

  • <문제> 집합A가 집합B의 부분집합인지 여부를 확인하기 위한 알고리즘을 작성하라

    • 집합 B의 원소들을 테이블에 저장한 뒤, 집합 A의 원소들을 하나씩 꺼내서 그것이 테이블에 존재하는지 확인한다.

  • 해시의 어원

    • 다진 고기 요리, 뒤범벅, 뒤죽박죽, 잡동사니, 쓰레기, 마리화나 등

    • 주어진 데이터를 잘 가공하여 해시값으로 만들어 사용하기 편하게 만든다는 의미

  • 해시값은 데이터를 저장하는 해시 테이블에서 키로 사용된다. 이 키값만 있다면, 테이블에서 키값에 해당하는 데이터는 정말 짧은 상수 시간안에 찾을 수 있다. 심지어는 데이터의 양이 늘어나도 검색 시간에 거의 차이가 없다.

  • 하지만 해시 알고리즘 역시 단점이 있다. 속도가 빠른 반면에, 해시 테이블만큼 큰 메모리 공간을 차지하게 된다.

    • 원래 알고리즘의 영역은 속도가 빠르면, 공간을 희생하고, 메모리 공간이 적게 들면 속도가 느린 법이다.

    • 자신이 사용하는 알고리즘의 속도와 공간을 분석하여 효율성을 점검하는 것은 프로그래머라면 해야할 필수적인 일이다. 단순 노가다만하는 코더와 침착하게 로직에 접근하는 프로그래머는 바로 이러한 작은 습관부터 시작된다.

• 사운덱스 검색 알고리즘

  • 사운덱스 검색 알고리즘은 사람이름을 일정한 코드로 변환해주는 알고리즘인데, 제 2차세계대전 기간에 군인들의 개인 기록을 관리하는데 쓰였고, 이후 미국의 인구 통계 조사 때에도 사용되었다고 한다. 요즘에는 여러가지 소프트웨어 속 철자확인기 엔진에도 사용된다고 한다.

  • 사운덱스 검색 알고리즘의 규칙은 다음과 같다.

    • 제일 첫글자를 남기고 그 이후는 글자는 a, e, o, h, i, u, w, y를 모두 제외한다. 반복되는 철자는 하나만 남기고 지운다.

    • 남은 글자 중에서 일정한 규칙에 따라 번호를 매긴다. (b는 1, c는 2, d는 3 … 등)

    • 남은 글자들이 3자리 미만이라서 숫자가 부족할 경우 0으로 채우고, 3자리 이상일 경우에는 3자리까지만 자른다.

    • 예를 들어 Gauss 라는 이름을 사운덱스 알고리즘에 의해 코드로 변환한다고 한다면 제일 첫글자 G를 남기고 그 이후의 a와 u는 제거한 뒤, ss는 반복되므로 s로 간주하고 2를 부여한다. 남은 두 자리는 0으로 채워 최종적으로 G200이라는 코드를 추출한다.

  • 결국 최적화 알고리즘이다. 실수로 초래되는 문제의 범위를 축소시켜주고, 검색 속도를 빠르게 해준다는 장점이 있기 때문에 다소 혼동의 여지가 있더라도 계속 사용한다.

• 메르센느 소수

  • 메르센느는 14세기 프랑스의 철학자이자 수도승사이며, 데카르트의 스승이라도 불릴 정도로 평소 철학과 수학에 심취해있었다고 한다.

  • 당시 “p가 소수이면, 2^p - 1 역시 소수이다.”라는 명제는 거짓으로 밝혀져 있었는데, 메르센느는 이것을 하나의 수식을 깔끔하게 표현하고 싶었다. 하지만 명제 자체에 그렇지 않은 케이스가 너무 많았기 때문에 그렇게 표현할 수 없었다.

  • 후에 메르센느 사후 사람들이 아래와 같이 표현함으로서 메르센느의 수학과 철학에 대한 열정을 기렸다고 한다.

    • “어떤 수 p가 소수일때, 2^p -1 역시 소수이면, 그 수를 메르센느의 수라고 한다.”

• 프로그래머가 느끼는 성취감의 본질

  • 메르센느 소수 중 가장 큰 수를 찾기 위해 일명 메르센느 소수 마니아들이 집결한 공간(GIMPS)이 인터넷 상에 존재한다.

    • https://www.mersenne.org/primes/

  • 그들은 이 실용적이지 않은 작업을 위해 고가의 슈퍼컴퓨터를 지원받을 수 없었다. 대신 전 세계에 흩어진 무명의 PC와 워크스테이션을 네트워크로 연결해서 그들의 통합된 컴퓨팅 파워를 이용하기로 했다.

    • 서버는 수 많은 클라이언트들에게 검색할 숫자를 주고, 결과를 수집하여 데이터베이스를 축적해나간다고 한다.

  • 이 발상이야말로 최적화의 끝판왕이라고 생각된다.

• 문학적 프로그래밍

  • 문학적 프로그래밍은 1980년대에 도널드 커누스 교수에 의해 던져진 화두이다. 프로그래밍 분야를 예술의 일종으로 보는 시각이다. 이러한 독특한 해석은 많은 프로그래머들의 영감을 자극했고, goto의 존재와 역할, 구조적 프로그래밍, 객체지향까지 지어지는 패러다임의 혁명에 영향을 주었다.

  • ACM 저널에서 <프로그래밍 펄>이라는 컬럼을 연재했던 존 벤틀러 교수는 이러한 신선한 시각이 좋았고, 이를 소개하는 내용을 쓰고 싶었다. 커누스 교수에게 이를 소개하고자 적절한 예시 알고리즘 문제를 통해 설명을 해달라고 했더니, 커누스 교수는 오히려 “문학적 프로그래밍”은 모든 상황과 알고리즘에서 가능하니, 오히려 자신에게 문제를 주면 문학적 프로그래밍의 방법으로 해결해주겠다고 답했다고 한다.

  • 그래서 벤틀러 교수가 낸 알고리즘 문제가 바로 이것이다.

    • 영어로 쓰여진 텍스트가 있다. 이 텍스트를 읽고 그 안에서 가장 빈번하게 등장하는 단어 상위 10개를 출력하는 프로그램을 작성하라.

  • 이 문제에 대해 우리는 두 가지의 알고리즘을 비교함으로써 커누스 교수의 답을 생각해볼 수 있다.

    • 알고리즘 1

      • hash(w) 함수는 단어 w에 대해서 유일무이한 하나의 해시값을 반환한다.

      • count[] 배열에는 각 단어의 횟수를 나타내는 정수값을 저장한다.

      • word[] 배열에는 단어를 저장한다.

      • 텍스트를 읽으면서 count[hash(w)] 값을 +1 하고, count 값이 0이면, word[hash(w)] 배열에 그 단어를 추가한다.

      • 이후 count[] 배열을 정렬한 다음, 순서대로 10개의 값을 찾고, 그 10개에 대응하는 단어를 word[] 에서 찾는다.

    • 알고리즘 2

      • 첫번째 검색할 때에는 count[hash(w)]만 저장한다.

      • 두번재 검색할 때에는 특정 기준 상수 C보다 큰 경우만 word[hash(w)]에 저장한다.

      • 검색 종료 후, count[] 를 정렬하여 상위 10개를 찾고, 그 10개 값에 해당하는 단어를 word[]에서 찾는다.

  • 두 알고리즘을 비교해보면, 알고리즘 1은 한번만 읽는 대신 불필요한 연산 (word배열에 모든 단어를 추가하는 등)이 존재하고 공간도 많이 쓴다. 대신 알고리즘 2는 검색을 두 번 하지만, 효율적으로 배열 공간을 사용하며 불필요한 연산을 줄인다.

  • 영어 문장에서 단어가 1회이상 반복될 확률이 절반 이하라는 점을 고려해본다면, 2번 알고리즘이 훨씬 효율적이라는 것을 알 수 있다.

  • 벤틀리는 다음과 같은 질문들 독자에게 던졌다고 한다.

    • “조용한 밤에 의자에 앉아서 편하게 프로그램을 읽으면서 시간을 보냈던 가장 최근은 언제인가”

  • 벤틀리는 이에 없다고 답했다고 한다. 업무를 위한 코드 읽기 이외에 조용히 프로그램을 읽었던 기억 말이다.

  • 문학적 프로그래밍의 서문에서 카누스 교수는 다음과 같은 말을 했다고 한다.

    • “컴퓨터 프로그램을 작성하는 일은 재미있다. 그리고 잘 작성된 프로그램을 읽는 것도 재미있다. 세상에서 가장 즐거운 일 중 하나는 여러분이 작성한 컴퓨터 프로그램을 다른 사람들 혹은 여러분 자신이 읽고 기쁨을 얻는 것이다. 컴퓨터 프로그램은 또한 유용한 작업을 수행할 수도 있다. 세상에서 가장 큰 성취감을 맛보는 순간은 여러분이 창조한 무엇이 사회의 부와 진보에 기여한다는 사실을 깨닫는 순간이다. 어떤 사람들은 컴퓨터 프로그램을 작성함으로써 돈을 벌기도 한다. 따라서 프로그래밍은 세 가지 측면에서 결실을 맺는 행위이다. 미학적으로, 인류학적으로, 그리고 경제적인 면이 바로 그러한 결실에 해당한다.”

3장. 하드코어 - 유클리드 알고리즘 & RSA 알고리즘

• 유클리드 알고리즘

  • 유클리드 알고리즘은 두 수 m과 n이 존재할 때, m과 n사이의 최대공약수를 구하는 알고리즘이다.

    • 보통 m이 n보다 크거나 같다고 가정하고 시작하는데, 만약에 n이 m보다 크면 그냥 두 수를 바꿔주면 된다. → swap(m, n)

  • 지금까지도 최대공약수를 구하는 가장 기본적인 알고리즘으로 꼽힌다.

• 재귀의 마술

  • 기존 gcd() 알고리즘에서 함수의 시작시 swap 부분이 존재하는 것이 어쩐지 깔끔하지는 않다. 이 부분을 개선하고 싶다면 재귀함수를 떠올려볼 수 있겠다.

  • 최대공약수를 구하는 gcd 함수에서 n=0일 경우, m값을 리턴하도록 하고, 그렇지 않다면 다시 gcd(n, m%n) 함수를 호출하여 리턴하도록 하면, 재귀함수를 이용하여 깔끔하게 최대공약수를 구할 수 있다.

  • 보통 재귀함수의 경우, 호출시, 원래 호출되었던 시점을 기억하기 위해 시스템 스택에 복귀 위치를 쌓는다. 따라서 너무 많이 호출될 시에 성능이슈가 있다.

  • 하지만 꼬리재귀처럼 return 구문에서 재귀함수를 호출하고 끝낸다면, 굳이 돌아갈 시점을 스택에 쌓을 필요가 없다. 재귀함수를 사용함으로써 발생되는 문제를 방지할 수 있는 것이다.

  • 재귀함수는 미학적으로 아름답고 간결하지만, 성능상 안좋다는 단점이 있고, for나 while 반복문이나 커스텀한 stack 함수는 성능상으로는 뛰어나지만 코드가독성이 재귀함수에 비해 떨어진다는 단점이 있다. 두 부분은 어떤 것을 우선시하느냐의 문제이지만, 꼬리재귀의 경우, 이같은 재귀함수의 단점마저 보완하기 때문에 효과적인 해결책이 될 수 있다.

• RSA 알고리즘의 창시자, 리베스트, 샤미르, 에이들맨

  • 오늘날 우리가 널리 사용하고 있는 공개키-개인키 개념(PKC)을 구현한 RSA 암호화 알고리즘은 MIT공대의 젊은 학자들인 Rivest, Shamir, Adleman 의 이니셜을 따서 만들어졌다.

  • 이들은 선배 학자인 Diffie와 Hellman, Merkle 이 정식화한 PKC(Public Key Cryptography)라는 혁명적인 개념에 영감을 받아, 이 개념을 현실세계에 구체화 할 수 있는 알고리즘으로 만들기 위해 노력했다.

  • 이들이 고민하던 것은 공개키로 문서를 암호화하면, 오로지 개인키가 있어야만 해독할 수 있는 알고리즘을 만드는 것이었다. 그리고 그들은 해냈다.

• RSA 알고리즘

  • p와 q는 소수이다. n=pq를 찾는다.

  • p와 q에서 각각 1을 빼서 곱한다. 그것을 pie라고 부른다.

    • pie = (p-1)(q-1)

  • 다음 조건을 만족하는 e를 찾는다.

    • 1 < e < pie, gcd(e, pie) = 1

  • 다음 조건을 만족하는 d를 찾는다.

    • 1 < d < pie, ed = 1 (mod pie)

  • (n, e)는 공개키가 되고, (n, d)는 개인키가 된다. p, q, pie와 같은 값들은 공개되지 않도록 한다.

  • 히딩크 감독과 코엘류 감독 사이에 비밀문서를 주고받는다고 가정해본 예시

• <문제> 빈 방안에 물이 반정도 있는 컵이 있다. 이 물이 절반을 넘는지 아니면 절반보다 부족한지 알아내는 방법은 무엇일까. (방이 비어있으므로 그 어떤 도구도 이용할 수 없다. 물을 마시거나 증발시키는 등 비정상적인 방법도 안된다.)

• 세 줄짜리 펄 프로그램

  • RSA 알고리즘을 이용한 암호화와 해독의 과정

  • 폴란드식 표기법과 역폴란드식 표기법

  • 유닉스 시스템의 계산기 dc 는 바로 역폴란드식 표기법을 따르기 때문에 입력시 주의해야한다.

  • 참고

    • 국제 엉망진창 C프로그램 경연대회

      • https://www.ioccc.org/index.html

  • 두 줄짜리 RSA 알고리즘

4장. 클래식 - N개의 여왕문제

• N개의 여왕문제

  • 가로 세로 모두 N개의 칸이 있는 체스판 위에 N개의 여왕을 올려놓되 서로 공격해서 잡을 수 없도록 놓을 수 잇는 방법은 모두 몇개인가?

  • 대표적인 퇴각검색 기법을 이용하는 문제

  • 가로 세로 길이가 4인 체스판 예시

    • 우선 (1,1)에 첫번째 여왕을 둔다고 가정한다.

    • 체스에서 여왕은 가로, 세로, 대각선으로 이동할 수 있으므로, 해당 규칙을 고려하여 두번째 말을 놓는다.

    • 만약에 진행하다가 경우의 수가 안나오면, 다시 이전 단계로 “퇴각”하여 다시 시도해본다.

    • 그렇게 되면 첫번째 단계까지 퇴각하게 되어 결국 아래와 같은 답을 구할 수 있다.

      • (1,2), (2, 4), (3, 2), (4, 3)

• N개의 여왕문제에서 우리가 사용한 퇴각검색기법은 사실 트리나 그래프를 탐색하는 방법과 매우 유사하다. 특히나 트리에서 깊이우선탐색, deepest first search DFS의 경우와 매우 비슷하다.

• 재귀와 스택

  • 위의 퇴각탐색을 실행할 때에 가장 중요한 것은 이미 가본 길을 가지 않는 것, 이미 체크한 수를 다시 체크하지 않는 것이다. 이때 우리가 쓸 수 있는 것이 재귀나 스택이다.

  • 재귀함수는 회귀지점을 저장하기 위해 스택 구조를 사용한다. 따라서 호출 횟수가 일정 수가 넘어가게 되면, 재귀함수는 성능상 급격하게 안좋아지고, 이는 속도뿐만아니라 메모리 공간의 효율성 측면에서도 그러하다.

• 재프 소머즈의 알고리즘

  • N개의 여왕문제를 구현한 많은 코드들이 있지만 재프 소머즈의 알고리즘은 퇴각검색 알고리즘의 절묘함, 비트 연산자와 재귀가 아닌 스택을 이용해서 알고리즘의 속도를 최적화 하고 있기 때문에 주목할만하다.

  • 비록 가독성은 그리 좋지 않지만, 그래도 위와 같은 점에서 주목할만하디.

• 비트 연산자 복습하기

  • & : 논리곱 - 둘다 참이면 1, 둘중 하나라도 거짓이면 0

  • | : 논리합 - 둘 중 하나라도 참이면 1, 둘다 거짓이면 0

  • ^ : 배타적 논리합 - 서로 다르면 1, 서로 다르면 0

  • : 오른쪽 시프트. 이진수를 오른쪽으로 한 칸 이동 ⇒ 2로 나누는 것과 같은 의미

  • << : 왼쪽 시프트. 이진수를 왼쪽으로 한 칸 이동 ⇒ 2를 곱하는 것과 같은 의미

  • ~ : 비트의 부정. 0은 1로, 1은 0으로 바꾸는 연산자

• 2의 보수

  • 2의 보수 체계에서 0으로 시작하는 이진수 : 양수

  • 1로 시작하는 이진수는 음수

• 제프 소머즈 알고리즘 분석

2. 느낀점

• 알고리즘의 유래에 대해서 자세하게 알 수 있는 책이었다. 정말로 누워서 읽을 수 있을 정도로 쉽게 설명이 되었고, 어려운 알고리즘이라는 개념이 이렇게 읽기 쉽게 쓰여졌다는 점에서 저자인 임백준 님의 내공을 감히 상상해볼 수 있었다.

• 백준 저지의 그 백준이 바로 이분이라는 사실을 책의 중반부에 이르러서야 알게 되었다....!

• 이 책을 읽은 뒤로는 알고리즘을 알아가는 과정이 한결 재미있어질 것 같다.

• 프로그래머의 자세에 대해서도 한 번 더 가르침을 받게 되었다. 나는 진짜 프로그래머가 아니구나, 더 날카롭고 꼼꼼해져야하며, 프로그래밍이라는 행위 자체를 좀 더 즐기도록 노력해봐야겠다고 생각하게 되었다.