#1-1 The Art of Computer Programming - 기초 알고리즘

약 한 달 전에 구매했던 책을 드디어 펼쳐보았다. 

 

컴퓨터 공학에서 공부할 분야들은 많고 많으나,

그중에서도 기본/기초 컴퓨터 공학 지식에 항상 목말라 있어서 이 책을 골랐고

책 초반을 읽어보니 상당히 흥미롭게 구성되어 있어서

기회가 될 때마다 한 챕터씩 읽고 연습 문제에 대한 내 답을 포스팅하려고 한다.

(연습문제 전문을 그대로 적는 것은 저작권에 연관되어 있을 수 있으니 일부만 쓸 예정, 물론 책에 나와 있는 해답도 적지 않을 예정)

그리고 문제를 보고 내가 설명할 수 없거나 전혀 이해가 안 가는 것들은 과감하게 생략하기로 결정했다.

자격시험이나 평가를 받아야 되는 것이 아니니 굳이 무리해서 할 필요도 없으니.

 

초등학교 때였었나..

서점에 가면 서바이벌? 같은 책들을 흥미롭게 보곤 했었다.

만화로 구성되어 있는 책이었는데 스토리가 진행되다가 분기가 발생하게 되고

분기별 선택에 대한 page들이 적혀 있어서 그 page로 가면 이야기가 진행되는.

이 책(시리즈)을 읽는 절차에 대해서도 상기에 언급한 책의 형식(순서도 라고도 할 수 있지만)을 따르고 있어서 옛날 생각도 나고 흥미로웠다.

 

오늘 목표인 1-1. 알고리즘 연습문제에 대한 내 답을 아래와 같이 적어본다.

 

1. a, b, c, d => b, c, d, a로 배치하는 작업은 왼쪽으로 shift 하는 것으로 볼 수 있다. 단순하게 생각하면 t라는 변수를 하나 주고 t <- a, a <- b, b <- c, c <- d, d <- t의 순서로 수행하면 된다. 그런데 치환 횟수를 최소 하려면 어떻게 해야 할까..?

 

2. 유클리드 알고리즘에서 m이 n보다 클 수밖에 없는 이유는 이전의 연산에서 n이 나머지였던 r값으로 대입되기에 그렇다. 또한 m은 나눈 수 n의 값이 대입되기 때문에 n은 무조건 r보다 클 수밖에 없어서 결국 m은 n보다 클 수밖에 없다.

 

3. 자명한 치환을 피하도록 수정할 수 있나? 반드시 필요한 연산들인 거 같은데

 

4. 6099 / 2166 => 2166 / 1767 => 1767 / 399 => 399 / 171 => 171 / 57 => 0, 마지막 n이었던 57이 최대공약수.

 

5. 알고리즘의 다섯 조건 : 처음 읽었을 땐 그냥 그렇구나 하고 넘어갔는 데, 문제 풀려고 하니 다시 정리가 필요해서 아래와 같이 정리

- 유한성 : 무한한 횟수로 수행되는 게 아닌, 언젠간 끝나는 성질(종료 조건이 있음)

- 명확성 : 모호함이 없이 명확하게 정의되어야 하는 성질

- 입력 : 0을 포함한 특정 개수의 입력을 갖고 있는 성질

- 출력 : 1을 포함한 특정 개수의 출력을 갖고 있는 성질

- 효과성 : 이론적으로 사람이 종이 & 연필을 사용해서 유한한 시간 안에 정확히 수행할 수 있도록 단순해야 하는 성질. 알고리즘에 쓰이는 값들이 무한 소수이거나 측정 불가한 물리적 선분의 길이라고 하면 이런 연산들은 효과적이지 않음

 

상기의 다섯 개 조건 중 만족 못하는 세 가지 조건을 찾아보았다.

1. 유한성 : 일단 종료 조건이 없어 보인다. 18번이 종료라고는 하는데 다시 3번으로 간다.

2. 명확성 : 흥미로운가? 아닌가? 등에 대한 주관적인 판단이 있기에 모호함이 존재하므로 명확성이 없다.

3. 출력 : 종료가 없으니 출력도 따로 없는 형태다.

 

나머지 연습문제들은 난이도가 너무 높아 Pass!