컬럼/인터뷰
Programming Challenges: 알고리즘 트레이닝 북 - 프로그래밍 스킬은 연습을 통해서만 향상된다
하나의 프로그램을 만드는 과정을 크게 세 단계로 나눠보자면 프로그램 설계 단계, 코딩 단계, 테스트 및 디버깅 단계로 나눌 수 있을 것이다. 셋 다 잘 진행되어야만 좋은 프로그램이 만들어질 수 있긴 하지만, 그 중에서 좋은 프로그램을 만들기 위해 가장 중요한 단계는 설계 단계라고 생각한다. 아무리 코딩을 잘하고 테스트 및 디버깅을 완벽하게 해도, 처음부터 설계가 잘 되지 않았다면 좋은 프로그램이 나올 수가 없다.
프로그램 설계 단계에서 해야 할 가장 중요한 일 가운데 하나로 자료구조와 알고리즘을 결정하는 것을 생각할 수 있다. 많은 프로그래머들이 어떤 프로그램을 짜야 한다고 할 때 무작정 코딩을 시작하는 것을 볼 수 있는데, 언뜻 보면 이렇게 하면 프로그램을 더 빨리 짤 수 있을 것 같지만 사실은 전혀 그렇지 않다. 제대로 된 설계도 없이 건물을 지을 수 없는 것과 마찬가지로, 철저한 준비 없이 바로 코딩을 시작하면 시행착오를 겪으면서 시간도 오래 걸리고 더 힘들게 프로그램을 짤 수밖에 없다. 차라리 작업하던 것을 잠시 접어놓고 설계부터 다시 시작하는 편이 나은 경우도 적지 않게 볼 수 있다.
전산학이 원래 그렇지만, 알고리즘은 그 중에서도 가장 수학, 논리학에 가까운 분야라고 할 수 있다. 알고리즘이란 계산법, 해법, 작도, 정보처리 등의 순서 및 과정을 일컫는 말이다. 따라서 알고리즘은 논리학, 수학에서의 문제 해결 방법이라고 볼 수 있다. 하지만 단순하게 이런 순서 및 과정을 잘 안다고 해서 좋은 프로그램이 나오는 것은 아니다. 결국 컴퓨터에게 이 알고리즘을 지시하려면 그것을 어떤 형태로든지 컴퓨터가 알아들을 수 있는 언어로 구현해야 하며, 그러려면 언어에 대한 이해 및 코딩 실력도 매우 중요하다.
곧 출간될 "Programming Challenges: 알고리즘 트레이닝 북"은 프로그래밍 경시대회, 그 중에서도 가장 큰 세계대회라고 할 수 있는 ACM 국제 대학생 프로그래밍 경시대회(ICPC; International Collegiate Programming Contest)와 국제 정보 올림피아드(International Olympiad in Informatic), 탑코더 경시대회(TopCoder Challenge)를 준비하기 위한 교재 형식으로 만들어진 책이다. 이런 경시대회에서 우수한 성적을 거두려면 알고리즘에 대한 이해와 코딩 실력을 두루 갖추고 있어야 한다. 이 책에서는 각 장에서 다양한 경시대회 유형의 문제를 해결하기 위해 필요한 필수적인 자료구조와 알고리즘에 대해 설명하고, 그 장에서 다룬 내용을 써서 풀 수 있는 문제들을 소개하고 있다. 그리고 C 언어로 여러 핵심적인 알고리즘을 구현해놓았기 때문에 알고리즘을 이해한 후에도 실제 구현에 어려움을 느끼는 독자들에게 좋은 길잡이가 될 수 있을 것이다. (파스칼이나 C++, 자바를 사용하는 사람들도 이해할 수 있을만한 방식으로 구현되어있으므로 C를 잘 모른다고 해서 두려워할 필요는 없다.)
수학 문제를 풀 때 공식을 알고 있다고 해서 무조건 문제가 풀리는 것은 아닌 것과 마찬가지로, 프로그래밍에서도 알고리즘을 알고 있다고 해서, 그리고 어떤 언어의 문법을 알고 있다고 해서 무조건 프로그램을 짜서 문제를 해결할 수 있는 것은 아니다. 결국 연습을 많이 해 봐야 한다. 수학을 공부할 때 문제를 많이 풀어봐야 실력이 느는 것처럼, 프로그래밍에서는 코딩을 많이 해 봐야만 실력을 쌓을 수 있다. 이 책을 제대로 활용하고 싶다면 알고리즘에 대한 내용과 코드만 눈으로 보고 넘어가지 말고 반드시 문제를 풀어보기를 바란다. 남이 짜 놓은 코드를 눈으로 본다고 해서 자신이 나중에 그와 같은 프로그램을 짤 수 있는 것은 아니다. 이 책의 저자들은 독자들이 직접 코드를 짜서 그 프로그램이 맞는지 확인해 볼 수 있도록 온라인 심사위원 사이트(http://www.programming-challenges.com)를 운영하고 있다. 이 사이트에서는 이 책에 나와있는 문제들을 심사해주기도 하며, 자신이 푼 문제들에 대한 결과를 일목요연하게 확인해볼 수도 있으므로 혼자 공부하는 독자들에게도 크게 도움이 될 것이다.
이 책은 경시대회 준비용 책이긴 하지만, 경시대회에 출전할 생각이 아니더라도 프로그래밍을 공부하는 사람들에게는 여러 모로 큰 도움이 될 수 있을 것이다. 많은 사람들이 "프로그래밍을 공부하기 위해서 보는" 프로그래밍 언어 교재에서는 배울 수 없는 알고리즘도 배우고, 복잡한 문제를 해결하는 방법에 대해 곰곰히 생각해볼 수 있기 때문이다. 결국 컴퓨터 프로그램이라는 것은 어떤 문제를 해결하기 위한 도구인데, 이 책을 공부해나가다 보면 문제 해결 능력을 확실히 키울 수 있을 것이다.
마지막으로 "Programming Challenges: 알고리즘 트레이닝 북"에 수록된 낮잠 오래 자기(Longest Nap) 문제를 발췌하였다. 해답을 보지 말고 직접 풀어보기 바란다.
문제) 낮잠 오래 자기(Longest Nap)
PC/UVa ID: 110404/10191, 인기도: B, 성공률: 보통, 레벨: 1
교수들은 각종 업무와 약속으로 가득 찬 복잡한 스케줄 속에서 매우 바쁘게 살아간다. P 교수는 낮잠을 자는 것을 좋아하지만 스케줄이 바쁘다 보니 낮잠을 잘 수 있는 시간이 별로 없다.
하지만 P 교수는 매일 한 번씩은 낮잠을 자고 싶어한다. 물론 그의 스케줄을 감안해서 될 수 있으면 오랫동안 낮잠을 즐길 수 있는 방법을 찾아야 한다. P 교수가 최대한 오랫동안 낮잠을 잘 수 있게 해주는 프로그램을 만들어라.
[입력]
임의 개수의 테스트 케이스가 입력되며 각 테스트 케이스가 하루를 나타낸다.
각 테스트 케이스의 첫번째 줄에는 100 이하의 양의 정수 s가 들어있으며 이 수는 그 날 미리 잡혀있는 약속의 개수를 나타낸다. 그 다음 줄부터 s개의 줄에는 time1 time2 약속 형식으로 잡혀있는 약속이 입력되며, time1은 시작 시각, time2는 끝나는 시각을 나타낸다. 모든 시각은 hh:mm 형식으로 주어진다. 끝나는 시각은 반드시 시작 시간보다 뒤며 시작 시간과 스페이스 한 개로 구분된다.
모든 시각은 10:00 이후, 18:00 이전으로 주어진다. 따라서 결과도 반드시 이 시간 내에 있어야 한다. 즉 10:00 전에 낮잠을 잘 수 없고 18:00 넘어서까지 낮잠을 잘 수도 없다.
약속은 임의의 문자를 열거한 형태로 주어지는데 반드시 한 줄에 입력되어야 한다. 각 줄의 길이는 255 글자를 넘지 않으며 10≤hh≤18, 0≤mm<60이라고 가정할 수 있다. 하지만 약속이 어떤 정해진 순서대로 입력된다고 가정할 수 없고 파일 종료 문자가 나올 때까지 입력을 모두 읽어야 한다.
[출력]
각 테스트 케이스에 대해 다음과 같은 내용을 한 줄씩 출력한다.
Day #d: the longest nap starts at hh:mm and will last for [H0 hours and] M minutes.
d는 테스트 케이스 번호(1에서 시작)를, hh:mm은 낮잠을 자기 시작하는 시각을 의미한다. 낮잠 자는 시간을 표시할 때는 다음과 같은 규칙을 따른다.
1. 총 시간 X가 60분 미만이면 "X minutes"만 출력한다.
2. 총 시간 X가 60분 이상이면 "H hours and M minutes"라고 출력한다. 이때 H는 다음과 같이 결정된다.
H=X÷60(정수 나눗셈), M=X를 60으로 나눈 나머지
단수, 복수는 따지지 않는다. 즉 "1 minutes", "1 hours" 같은 식으로 출력되도록 해야 한다.
낮잠을 잘 수 있는 시간은 시작 시각과 끝나는 시각의 차로 계산한다. 즉 약속이 14:00에 끝나고 다음 약속이 14:47에 시작하면 14:47-14:00=47분 동안 낮잠을 잘 수 있다.
가장 길게 낮잠을 잘 수 있는 시간이 여러 개 있으면 그 중 가장 빨리 시작하는 것을 출력한다. 낮잠을 잘 시간이 전혀 없을 정도로 교수가 하루 종일 바쁜 경우는 없다고 가정한다.
[입력 예]
[출력 예]
해답
약속 시간들을 정렬한 다음, 앞에서부터 읽어 나가면서 중간에 비는 시간을 계산하여 그 최대 값을 찾으면 된다. 시간 계산을 편리하게 하기 위해, 입력 받은 시간 값을 10시 정각을 기준으로 하여 몇 분이 지났는지로 변환해서 처리했다.
프로그램 설계 단계에서 해야 할 가장 중요한 일 가운데 하나로 자료구조와 알고리즘을 결정하는 것을 생각할 수 있다. 많은 프로그래머들이 어떤 프로그램을 짜야 한다고 할 때 무작정 코딩을 시작하는 것을 볼 수 있는데, 언뜻 보면 이렇게 하면 프로그램을 더 빨리 짤 수 있을 것 같지만 사실은 전혀 그렇지 않다. 제대로 된 설계도 없이 건물을 지을 수 없는 것과 마찬가지로, 철저한 준비 없이 바로 코딩을 시작하면 시행착오를 겪으면서 시간도 오래 걸리고 더 힘들게 프로그램을 짤 수밖에 없다. 차라리 작업하던 것을 잠시 접어놓고 설계부터 다시 시작하는 편이 나은 경우도 적지 않게 볼 수 있다.
전산학이 원래 그렇지만, 알고리즘은 그 중에서도 가장 수학, 논리학에 가까운 분야라고 할 수 있다. 알고리즘이란 계산법, 해법, 작도, 정보처리 등의 순서 및 과정을 일컫는 말이다. 따라서 알고리즘은 논리학, 수학에서의 문제 해결 방법이라고 볼 수 있다. 하지만 단순하게 이런 순서 및 과정을 잘 안다고 해서 좋은 프로그램이 나오는 것은 아니다. 결국 컴퓨터에게 이 알고리즘을 지시하려면 그것을 어떤 형태로든지 컴퓨터가 알아들을 수 있는 언어로 구현해야 하며, 그러려면 언어에 대한 이해 및 코딩 실력도 매우 중요하다.
곧 출간될 "Programming Challenges: 알고리즘 트레이닝 북"은 프로그래밍 경시대회, 그 중에서도 가장 큰 세계대회라고 할 수 있는 ACM 국제 대학생 프로그래밍 경시대회(ICPC; International Collegiate Programming Contest)와 국제 정보 올림피아드(International Olympiad in Informatic), 탑코더 경시대회(TopCoder Challenge)를 준비하기 위한 교재 형식으로 만들어진 책이다. 이런 경시대회에서 우수한 성적을 거두려면 알고리즘에 대한 이해와 코딩 실력을 두루 갖추고 있어야 한다. 이 책에서는 각 장에서 다양한 경시대회 유형의 문제를 해결하기 위해 필요한 필수적인 자료구조와 알고리즘에 대해 설명하고, 그 장에서 다룬 내용을 써서 풀 수 있는 문제들을 소개하고 있다. 그리고 C 언어로 여러 핵심적인 알고리즘을 구현해놓았기 때문에 알고리즘을 이해한 후에도 실제 구현에 어려움을 느끼는 독자들에게 좋은 길잡이가 될 수 있을 것이다. (파스칼이나 C++, 자바를 사용하는 사람들도 이해할 수 있을만한 방식으로 구현되어있으므로 C를 잘 모른다고 해서 두려워할 필요는 없다.)
수학 문제를 풀 때 공식을 알고 있다고 해서 무조건 문제가 풀리는 것은 아닌 것과 마찬가지로, 프로그래밍에서도 알고리즘을 알고 있다고 해서, 그리고 어떤 언어의 문법을 알고 있다고 해서 무조건 프로그램을 짜서 문제를 해결할 수 있는 것은 아니다. 결국 연습을 많이 해 봐야 한다. 수학을 공부할 때 문제를 많이 풀어봐야 실력이 느는 것처럼, 프로그래밍에서는 코딩을 많이 해 봐야만 실력을 쌓을 수 있다. 이 책을 제대로 활용하고 싶다면 알고리즘에 대한 내용과 코드만 눈으로 보고 넘어가지 말고 반드시 문제를 풀어보기를 바란다. 남이 짜 놓은 코드를 눈으로 본다고 해서 자신이 나중에 그와 같은 프로그램을 짤 수 있는 것은 아니다. 이 책의 저자들은 독자들이 직접 코드를 짜서 그 프로그램이 맞는지 확인해 볼 수 있도록 온라인 심사위원 사이트(http://www.programming-challenges.com)를 운영하고 있다. 이 사이트에서는 이 책에 나와있는 문제들을 심사해주기도 하며, 자신이 푼 문제들에 대한 결과를 일목요연하게 확인해볼 수도 있으므로 혼자 공부하는 독자들에게도 크게 도움이 될 것이다.
이 책은 경시대회 준비용 책이긴 하지만, 경시대회에 출전할 생각이 아니더라도 프로그래밍을 공부하는 사람들에게는 여러 모로 큰 도움이 될 수 있을 것이다. 많은 사람들이 "프로그래밍을 공부하기 위해서 보는" 프로그래밍 언어 교재에서는 배울 수 없는 알고리즘도 배우고, 복잡한 문제를 해결하는 방법에 대해 곰곰히 생각해볼 수 있기 때문이다. 결국 컴퓨터 프로그램이라는 것은 어떤 문제를 해결하기 위한 도구인데, 이 책을 공부해나가다 보면 문제 해결 능력을 확실히 키울 수 있을 것이다.
마지막으로 "Programming Challenges: 알고리즘 트레이닝 북"에 수록된 낮잠 오래 자기(Longest Nap) 문제를 발췌하였다. 해답을 보지 말고 직접 풀어보기 바란다.
문제) 낮잠 오래 자기(Longest Nap)
PC/UVa ID: 110404/10191, 인기도: B, 성공률: 보통, 레벨: 1
교수들은 각종 업무와 약속으로 가득 찬 복잡한 스케줄 속에서 매우 바쁘게 살아간다. P 교수는 낮잠을 자는 것을 좋아하지만 스케줄이 바쁘다 보니 낮잠을 잘 수 있는 시간이 별로 없다.
하지만 P 교수는 매일 한 번씩은 낮잠을 자고 싶어한다. 물론 그의 스케줄을 감안해서 될 수 있으면 오랫동안 낮잠을 즐길 수 있는 방법을 찾아야 한다. P 교수가 최대한 오랫동안 낮잠을 잘 수 있게 해주는 프로그램을 만들어라.
[입력]
임의 개수의 테스트 케이스가 입력되며 각 테스트 케이스가 하루를 나타낸다.
각 테스트 케이스의 첫번째 줄에는 100 이하의 양의 정수 s가 들어있으며 이 수는 그 날 미리 잡혀있는 약속의 개수를 나타낸다. 그 다음 줄부터 s개의 줄에는 time1 time2 약속 형식으로 잡혀있는 약속이 입력되며, time1은 시작 시각, time2는 끝나는 시각을 나타낸다. 모든 시각은 hh:mm 형식으로 주어진다. 끝나는 시각은 반드시 시작 시간보다 뒤며 시작 시간과 스페이스 한 개로 구분된다.
모든 시각은 10:00 이후, 18:00 이전으로 주어진다. 따라서 결과도 반드시 이 시간 내에 있어야 한다. 즉 10:00 전에 낮잠을 잘 수 없고 18:00 넘어서까지 낮잠을 잘 수도 없다.
약속은 임의의 문자를 열거한 형태로 주어지는데 반드시 한 줄에 입력되어야 한다. 각 줄의 길이는 255 글자를 넘지 않으며 10≤hh≤18, 0≤mm<60이라고 가정할 수 있다. 하지만 약속이 어떤 정해진 순서대로 입력된다고 가정할 수 없고 파일 종료 문자가 나올 때까지 입력을 모두 읽어야 한다.
[출력]
각 테스트 케이스에 대해 다음과 같은 내용을 한 줄씩 출력한다.
Day #d: the longest nap starts at hh:mm and will last for [H0 hours and] M minutes.
d는 테스트 케이스 번호(1에서 시작)를, hh:mm은 낮잠을 자기 시작하는 시각을 의미한다. 낮잠 자는 시간을 표시할 때는 다음과 같은 규칙을 따른다.
1. 총 시간 X가 60분 미만이면 "X minutes"만 출력한다.
2. 총 시간 X가 60분 이상이면 "H hours and M minutes"라고 출력한다. 이때 H는 다음과 같이 결정된다.
H=X÷60(정수 나눗셈), M=X를 60으로 나눈 나머지
단수, 복수는 따지지 않는다. 즉 "1 minutes", "1 hours" 같은 식으로 출력되도록 해야 한다.
낮잠을 잘 수 있는 시간은 시작 시각과 끝나는 시각의 차로 계산한다. 즉 약속이 14:00에 끝나고 다음 약속이 14:47에 시작하면 14:47-14:00=47분 동안 낮잠을 잘 수 있다.
가장 길게 낮잠을 잘 수 있는 시간이 여러 개 있으면 그 중 가장 빨리 시작하는 것을 출력한다. 낮잠을 잘 시간이 전혀 없을 정도로 교수가 하루 종일 바쁜 경우는 없다고 가정한다.
[입력 예]
4
10:00 12:00 Lectures
12:00 13:00 Lunch, like always.
13:00 15:00 Boring lectures...
15:30 17:45 Reading
4
10:00 12:00 Lectures
12:00 13:00 Lunch, just lunch.
13:00 15:00 Lectures, lectures... oh, no!
16:45 17:45 Reading (to be or not to be?)
4
10:00 12:00 Lectures, as everyday.
12:00 13:00 Lunch, again!!!
13:00 15:00 Lectures, more lectures!
15:30 17:15 Reading (I love reading, but should I schedule it?)
1
12:00 13:00 I love lunch! Have you ever noticed it? :)
[출력 예]
Day #1: the longest nap starts at 15:00 and will last for 30 minutes.
Day #2: the longest nap starts at 15:00 and will last for 1 hours and 45 minutes.
Day #3: the longest nap starts at 17:15 and will last for 45 minutes.
Day #4: the longest nap starts at 13:00 and will last for 5 hours and 0 minutes.
해답
약속 시간들을 정렬한 다음, 앞에서부터 읽어 나가면서 중간에 비는 시간을 계산하여 그 최대 값을 찾으면 된다. 시간 계산을 편리하게 하기 위해, 입력 받은 시간 값을 10시 정각을 기준으로 하여 몇 분이 지났는지로 변환해서 처리했다.
/* @BEGIN_OF_SOURCE_CODE */
/* @JUDGE_ID: hoimann 10152 C "simple one" */
#include
#include
#define MAX_APPTS 100
typedef struct {
int start, end;
} appointment;
int str2time(char *hh, char *mm)
{
return (hh[1] - "0") * 60 + (mm[0] - "0") * 10 + (mm[1] - "0");
}
appointment appt[MAX_APPTS + 2];
char line[256];
void main()
{
int num_appts;
int day_number, i, j, min, nap_slot, nap_time;
appointment temp_appt;
day_number = 0;
while (scanf("%d", &num_appts) == 1) {
day_number++;
gets(line);
appt[0].start = 0;
appt[0].end = 0;
appt[num_appts + 1].start = 8 * 60;
appt[num_appts + 1].end = 8 * 60;
for (i = 1; i <= num_appts; i++) {
gets(line);
appt[i].start = str2time(line, line + 3);
appt[i].end = str2time(line + 6, line + 9);
}
for (i = 1; i < num_appts; i++) {
min = i;
for (j = i; j <= num_appts; j++)
if (appt[j].start < appt[min].start)
min = j;
temp_appt = appt[i];
appt[i] = appt[min];
appt[min] = temp_appt;
}
nap_slot = 0;
nap_time = appt[1].start - appt[0].end;
for (i = 1; i <= num_appts; i++)
if (appt[i + 1].start - appt[i].end > nap_time) {
nap_slot = i;
nap_time = appt[i + 1].start - appt[i].end;
}
printf("Day #%d: the longest nap starts at ", day_number);
printf("1%d:%02d and will last for ",
appt[nap_slot].end / 60,
appt[nap_slot].end % 60);
if (nap_time >= 60)
printf("%d hours and %d minutes.\n", nap_time / 60, nap_time % 60);
else
printf("%d minutes.\n", nap_time);
}
}
/* @END_OF_SOURCE_CODE */
TAG :
이전 글 : IT에서 고전을 읽을 필요가 있는가?
최신 콘텐츠