계속 수정됩니다.
문제 해결 능력을 기르기 위한 방법 중 효과적인 것이 프로그래밍 대회 참가
프로그래밍 대회들은 주로 짧은 요구사항을 제시하고, 이에 맞는 프로그램을 시간 안에 빠르게 작성하는 능력을 겨루는 대회
문제 형식은 '어떤 값을 읽어들여 어떤 값을 계산하는 프로그램을 작성하시오'
배울 수 있는 것
- 텍스트 출력만 있기 때문에 문제 해결에만 집중 가능
- 명시적인 시간 제한과 메모리 제한. 알고리즘에 사용된 원칙들을 이해하고 변형해야 풀 수 있는 문제들이 많이 출제되기 때문에 이런 주제들을 깊이 이해하는 데 큰 도움이 됨
- 정답과 오답의 여부가 훨씬 명확하여 예외 없고 정확한 프로그램을 짜는 아주 좋은 훈련이 됨
- 논리적 구조가 복잡한 프로그램의 수행 성능을 예측하는 데 익숙해짐
- 작은 규모의 코드를 작성하는 경우가 많아 간결하면서 우아한 프로그램을 짜는 데 시간 투자 가능
- 경쟁이 좋은 동기가 되고 고수 프로그래머들의 코드들과 비교할 수 있음
책의 포인트
- 책의 문제는 직접 풀어볼 것
- 알고리즘을 어떻게 구현했는지 비교
- 더 좋은 알고리즘을 찾아내려 노력
대회 종류
- 한국 정보 올림피아드: 초, 중 고등학생 대상, 4시간 동안 3개의 문제
- ACM-ICPC (ACM 대학생 프로그래밍 경시대회): 3인1팀, 한 대의 컴퓨터, 5시간 8~10문제
- TopCoder: 1시간 15분 3문제. 한 달에 대략 3번. 1년에 한 번 탑코더 오픈 토너먼트 개최
- 구글 코드 잼: 모든 언어 가능
- 기타 온라인 대회, 모의고사(탑코더, 코드포스, 바야돌리드 대학교 온라인 채점 사이트)
대회 준비 조언
- 가능한 한 많은 문제 풀기(개념 이해 후 문제를 풀어 경험 쌓을 것)
- 온라인 채점 사이트 이용
온라인 채점 사이트
- 알고스팟(초·중급자용, algospot.com)
- 백준(초·중급자용,acmicpc.net)
- USACO Training Program(초·중급자용,train.usaco.org/usacogate)
- TopCoder(중급자용, topcoder.com/tc)
- ACM-ICPC Live Archive(중급자용, livearchive.onlinejudge.org)
- Project Euler(중급자용, projecteuler.net)
- SPOJ Online Judge(상급자용, spoj.pl)
팀 단위 연습 조언
- 종이 위에 답안 스케치(자료구조, 함수 역할, 의사 코드)
- 치밀한 역할 분담(코딩 2명, 문제풀이 1명)
- 페어 프로그래밍 연습(작성하면서 생각을 입으로 설명하는 연습, 배열 크기 등 실수하기 쉬운 지점 검토)
- 디버거 없이 디버깅
- 인쇄 대기 감소를 위한 화면 분할
팀 노트북 준비
ACM-ICPC 에서는 참고 자료로써 20여 장 출력물 지참 가능
1. 미리 준비(문제 풀 때 유용한 것 정리)
2. 간단한 형태의 문서화(역할, 실행 전·후 조건)
3. 클래스 형태 준비
4. 적절한 글꼴
읽을거리
- 『Introduction to Algorithms』(한빛미디어)
- 『Programming Challenges』(한빛미디어)
- 『The Art of Computer Programming』(한빛미디어)
문제 해결 과정
문제를 읽고 이해하기
사소한 제약 조건을 잘못 이해해서 풀 수 없게 되는 문제들이 흔하므로 문제가 원하는 바를 완전히 이해하자.
재정의와 추상화
문제를 자신의 언어로 풀어 쓰자.
복잡한 현실 세계의 개념을 본질만 남겨두고 축약하여 다루기 쉽게 표현하자.
계획 세우기
어떤 방식으로 해결할지, 사용할 알고리즘과 자료구조를 선택하자.
계획 검증하기
설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지 증명하고, 수행에 걸리는 시간, 사용하는 메모리가 문제의 제한 내에 들어가는지 확인하자.
계획 수행하기
설계한 알고리즘을 정확하고 효율적으로 구현하자.
회고하기
문제를 해결한 과정을 돌이켜 보고 개선하자.
더 효율적인 알고리즘을 찾거나 간결한 코드를 작성하고, 같은 알고리즘을 유도할 수 있는 더 직관적인 방법을 찾자.
- 코드와 함께 자신의 경험(간단한 해법, 접근 방식, 결정적인 깨달음)을 기록으로 남기자
- 한번에 맞추지 못한 경우 오답 원인을 적자
- 다른 사람의 코드를 보며 생각하지 못했던 통찰을 얻자
문제를 풀지 못할 때는 일정 시간이 지나도록 고민해도 답을 찾지 못할 때는 다른 사람의 소스 코드나 풀이를 참조한다는 원칙을 세우고 이를 지키자.
단 참조를 했을 경우 반드시 복기를 동반하자.
문제 해결 전략
직관과 체계적인 접근
해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지를 짐작할 수 있게 하자.
체계적인 접근을 위한 질문들
비슷한 문제를 풀어본 적이 있던가?
알고리즘 유형을 분류하는 방법을 익히고 그 동작 과정과 원리를 완전히 이해하자.
어느 경우에 사용될 수 있는지 체계적으로 공부해야 한다.
단순한 방법에서 시작할 수 있을까?
시간, 공간 제약을 생각하지 않고 가장 단순한 알고리즘을 만들어 보자.
좀더 효율적인 자료 구조를 사용하거나, 계산 과정에서 같은 정보를 두 번 중복으로 계산하지 않는 등의 최적화를 적용해서 충분히 빨라질 때까지 알고리즘을 개선할 수 있다.
점진적인 개선을 통해 문제를 풀 수 없더라도 단순한 방법은 알고리즘 효율성의 기준선을 정해준다.
내가 문제를 푸는 과정을 수식화할 수 있을까?
손으로 여러 간단한 입력을 직접 해결해보자. 이 과정에서 알고리즘이 어떤 점을 고려해야 하는지 알게 된다. 어떻게 문제를 풀어야 할지 감을 잡기에도 유용하다.
문제를 단순화할 수 없을까?
주어진 문제의 좀더 쉬운 변형판을 먼저 풀어보자.
문제의 제약 조건 제거, 계산해야 하는 변수의 수 감소, 다차원의 문제를 1차원으로 감소하는 방식이 있다.
그림으로 그려볼 수 있을까?
두 개의 정수 쌍들을 다루는 문제가 있다면, 이 정수 쌍을 2차원 평면 상의 좌표로 그려 볼 수 있고, 직선 상의 구간들로 그려 볼 수 있다.
수식으로 표현할 수 있을까?
평문으로 쓰여 있는 문제를 수식으로 표현하자. 수식을 전개하거나 축약하는 등의 순수한 수학적 조작이 문제를 해결하는 데 도움을 줄 수 있다.
문제를 분해할 수 있을까?
복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해하자.
뒤에서부터 생각해서 문제를 풀 수 있을까?
문제에 내재된 순서를 바꿔보자.
A에서 B로 가는 것보다 B에서 A로 가는 것이 빠를 수 있다. (사다리 게임)
순서를 강제할 수 있을까?
순서가 없는 문제에 순서를 강제해서 문제를 풀어보자.
경우의 수를 셀 때 유용하다. 특정 조건을 만족하는 답들의 수를 세는 문제에서 한 가지 답을 두 가지 이상의 방법으로 만들 수 있을 때 답이 중복해서 세어지는데 할 수 있는 일들의 순서를 강제하는 것이 좋은 해법이 된다. (오름차순으로만 본다던지?)
특정 형태의 답만을 고려할 수 잇을까?
정규화(canonicalization)란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법이다.
정규화 기법을 사용하기 위해서는 어떤 답이 주어지더라도 이것을 특정 형태의 답으로 바꿀 수 잇는 변형 과정을 찾아야 한다.
더 읽을거리
- 『어떻게 문제를 풀 것인가(How to Solve It)』(교우사)
코딩의 중요성
간결하고 일관되게 코드를 작성하여 읽기 쉽고 디버깅이 쉽게 하자.
좋은 코드를 짜기 위한 원칙
간결한 코드를 작성하기
- 코드가 짧을수록 오타나 단순한 버그가 생길 우려가 줄어들고, 디버깅이 쉬워진다
- 작성하는 프로그램이 짧다면 융통성 있게 가려 사용하면 유용하다(전역 변수의 광범위한 사용)
- 반복문처럼 자주 타이핑하게 되는 코드의 일부를 매크로로 표현하자
#define FOR(i,n) for(int i=0; i<(n); ++i)
FOR(i, array.size())
FOR(j, i)
// 이런 식으로 하면 증감문 오타같은 경우를 대비할 수 있음실수를 피해 가는 올바른 방법은 foreach 구문 이용! C++11 부터 구간 기반 for문 지원
적극적으로 코드 재사용하기
코드를 모듈화하자. 같은 코드가 세 번 이상 등장한다면 함수로 분리해 재사용한다는 기본 원칙을 만들면 좋다.
한 함수가 두 가지 이상의 일을 해서는 안 된다는 것이 이상적인 코드
표준 라이브러리 공부하기
모든 코드를 직접 작성하는 것은 시간 낭비. 팀원의 이해를 돕기 위해서라도 표준 라이브러리의 사용은 필수.
문자열, 동적 배열, 스택, 큐, 리스트, 딕셔너리 등의 자료 구조, 정렬 등의 표준적인 알고리즘 구현 사용법을 알아두자.
항상 같은 형태로 프로그램을 작성하기
같은 코드를 작성하는 더 좋은 방법에 대해 꾸준히 고민할 필요는 있지만,
자주 작성하는 알고리즘이나 코드 등에 대해서는 한 번 검증된 코드를 작성하고 이것만을 꾸준히 사용할 필요가 있다. 그래야 도구가 아니라 문제에 집중할 수 있다!
일관적이고 명료한 명명법 사용하기
사용하는 언어의 표준 라이브러리에서 사용하는 명명 규악(naming convention)을 익히자.
모호하지 않은 변수명과 함수명을 사용하자.
모든 자료를 정규화해서 저장하기
같은 자료를 두 가지 형태로 저장하지 않는 것이 좋다.
유리수를 예로 들면 항상 약분해서 기약 분수로 표현하는 것이 좋다.
자료를 표현하는 클래스의 생성장에서 정규화를 수행하거나, 외부에서 자료를 입력받자마자 정규화를 수행하는 것이 이상적이다.
코드와 데이터를 분리하기
날짜를 영문 이름으로 출력할 때
if(month == 1) return "January";
...이와 같은 형식으로 작성하면 안 좋다.
코드의 논리와 상관 없는 데이터는 가능한 한 분리하는 것이 좋다.
영문 이름을 별도의 배열에 저장하는 방식이 있다.
자주하는 실수
산술 오버플로
변수의 표현 범위를 벗어나는 값을 사용하는 산술 오버플로.
배열 범위 밖 원소에 접근
배열 크기를 정할 때 계산을 신중히 하자.
인덱스를 0에서 시작하는지 1에서 시작하는지 주의하자.
일관되지 않은 범위 표현 방식 사용하기
자연수 범위 [2, 3, 4, …, 12] 를 표현하고 싶을 때
닫힌 구간: [2, 12]
열린 구간: (1, 13)
반 열린 구간: [2, 13)
C++ STL에서는 반복자(Iterator)로 범위를 표현할 때 첫 원소를 가리키는 반복자와 마지막 원소 다음 위치를 가리키는 반복자를 사용한다. begin() 과 end()
장점
- 첫 번째 값과 마지막 값이 같은 구간을 이용하면 텅 빈 구간 쉽게 표현 가능
- 두 구간이 연속해 있는지 쉽게 알 수 있음. 두 구간 [a, b)와 [c, d) 가 b = c 혹은 a = d 라면 연속함
- 구간 크기를 쉽게 알 수 있음. [a, b) 는 b-a 로 알 수 있음
한 가지 방법으로만 범위를 표현해야 혼란을 초래하지 않음
Off-by-one 오류
반복문에서 < 혹은 > 연산자와 ≤ 와 ≥ 연산자를 혼용할 경우 흔하게 발생한다.
최소 입력이 주여졌을 때 이 코드가 어떻게 동작할지를 되새겨 보면서 프로그램을 짜면 좋다.
컴파일러가 잡아주지 못하는 상수 오타
- 모두 대문자로 출력해야 되는데 첫 문자만 대문자로 출력한 경우
- 100000007 로 나눈 나머지를 구해야 하는데 0을 하나 빼트리는 경우
- 64비트 정수형에 상수를 담으면서 64비트라고 지정하지 않는 경우(C++의 경우 정수형 상수 뒤에 LL을 붙이지 않으면 32비트로 가정)
스택 오버플로
콜 스택이 오버플로해서 프로그램이 강제종료 될 수 있다.
재귀 호출이 깊이가 너무 깊어지면 오는데, 스택 허용량에 대해 알아둘 필요가 있다.
스택 메모리를 절약하기 위해 자동으로 힙에 메모리를 할당하는 STL 컨테이너를 사용하거나 전역 변수를 사용하곤 한다.
다차원 배열 인덱스 순서 바꿔 쓰기
동적 계획법을 위한 메모이제이션 패턴을 사용할 때 잦다.
가능한 한 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋다.
C++의 참조 변수를 사용해 해결하자.
잘못된 비교 함수 작성
정렬할 때 비교 함수를 잘못 작성해서 원하는 순서를 얻지 못할 수 있다.
< 연산자의 성질
- 비반사성: a<a는 항상 거짓
- 비대칭성: a<b가 참이면 b<a는 거짓
- 전이성: a<b가 참이고 b<c가 참이면 a<c
- 상등 관계의 전이성: a<b와 b<a가 모두 거짓이면 a=b. a=b 이고 b=c 라면 a=c
최소, 최대 예외 잘못 다루기
가장 작은 입력과 가장 큰 입력에 대해 제대로 동작할지를 생각해 보자.
연산자 우선순위 잘못 쓰기
if(b & 1 == 0)
// 위 코드는 다음과 같은 의미
if(b & (1 == 0))연산자의 우선순위를 잘 기억하거나, 헷갈릴 경우 괄호로 적절히 감싸자.
너무 느린 입출력 방식 선택
gets() 를 이용해 모든 입력을 문자열 하나로 읽어들여 파싱할 수 있고, cin 등의 고수준 입력 방식을 사용할 수 있지만 cin 은 속도가 느리다.
cin.sync_with_stdio(false) 를 사용하자. (cstdio 의 표준 입출력 함수들과의 동기화 해제)
변수 초기화 문제
초기화를 하지 않고 변수를 그대로 사용하면 두 번째 입력부터는 답이 잘못 나올 수 있다.
예제 입력 파일을 두 번 반복해 쓰는 것이 방법이다.
변수를 적절히 초기화하도록 신경 써서 코딩하는 것이 가장 좋은 방법이다.
디버깅에 관하여
- 프로그래밍 대회에서 작성하는 소스 코드를 대개 길지 않기 때문에, 눈으로 디버깅하는 쪽이 훨신 빠를 수 있다.
- 재귀 호출, 중복 반복문을 많이 사용하는 복잡한 코드는 디버거로 디버깅하기에 적당하지 않다.
- ACM-ICPC의 경우 세 명이 한 대의 컴퓨터를 나누어 써야 하기 때문에, 한 사람이 디버깅으로 컴퓨터를 점유하면 다른 두 사람은 아무 것도 할 수 없다.
디버거를 사용하는 대신 디버깅하는 팁
- 작은 입력에 대해 제대로 실행되나 확인하기
- 단정문(assertion)을 쓴다: 주어진 조건이 거짓일 때 오류를 내고 프로그램을 강제 종료시키는 함수 또는 구문
- 프로그램의 계산 중간 결과를 출력한다.
테스트에 관하여
주어진 예제 입력을 약간 바꿔서 넣어 보거나, 있을 수 있는 가장 작은 입력과 가장 큰 입력을 만들어서 넣어 보고 시간 안에 실행되는지, 답은 잘 나오는지 테스트하자.
스캐폴딩: 다른 코드를 개발할 때 뼈대를 잡기 위해 임시로 사용하는 코드
스캐폴딩으로 코드의 정당성을 확인하거나 반례를 찾는 데 유용하게 쓰자.
임의의 작은 입력을 자동으로 생성해 프로그램을 돌려 보고, 그 답안을 검증하는 프로그램을 짜면 쉽게 테스트할 수 있다.
변수 범위의 이해
산술 오버플로
어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우
일어나는 이유
1. 대부분의 프로그래밍 언어들은 사칙연산 과정에서 오버플로가 나더라도 경고를 하지 않는다.
2. 프로그램의 정당성을 검증할 때 프로그램 논리의 정확성에만 집중하다 보면 산술 오버플로를 고려하지 못할 수 있음.
너무 큰 결과
큰 정수를 다룰 때는 항상 변수의 형태에 주의하는 습관을 가지자.
64비트의 정수를 이용하면서 중간 계산 값을 32비트 정수로 전달할 수 있으니 주의하자.
너무 큰 중간 값
프로그램의 출력 값의 범위는 작지만 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우.
너무 큰 '무한대' 값
최단 경로를 구할 때 길이 없는 경우는 굉장히 큰 값을 더해줘서 min 함수에서 걸러지게 할 수 있다.
무한대 값을 선택할 때는 이 무한대 값들이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴보고 오버플로가 나지 않을 크기의 값을 선택하는 것이 좋다.
987,654,321 은 2의 30제곱에 가까운 매우 큰 값이면서 서로 더해지더라도 32비트 부호 있는 정수에 오버플로를 내지 않고, 오타가 났는지 확인하기 용이하다.
오버플로 피해가기
가장 간단한 방법은 더 큰 자료형 쓰는 것.
자료형의 프로모션
이항 연산자에서 만약 피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러들은 대개 이들을 같은 자료형으로 변환해서 계산한다. 이를 프로모션이라 한다.
C++ 의 프로모션 규칙
1. 한쪽은 정수형이고 한쪽은 실수형이면 정수형이 실수형으로 변환
2. 양쪽 다 정수형이거나 양쪽 다 실수형이면 보다 넓은 범위를 갖는 자료형으로 변환
3. 양쪽 다 int형보다 작은 정수형이면 양쪽 다 int형으로 변환
4. 부호 없는 정수형과 부호 있는 정수형이 섞여 있으면 부호 없는 정수형으로 변환
C++ STL 에서 모든 컨테이너의 size() 는 부호 없는 정수형을 반환한다.
이 때 크기가 0인데 -1 을 한다면 가장 큰 수가 되어버린다.
실수 자료형의 이해
실수 연산의 어려움
1/x * x = 1인 x의 수를 세는 코드를 작성하면 원하는 결과를 얻을 수 없음
실수와 근사 값
컴퓨터의 모든 실수 변수는 정확도가 제한된 근사 값을 저장한다.
IEEE 754 표준
- 이진수로 실수를 표기
- 부동 소수점 표기법
- 무한대, 비정규 수, NaN(Not a Number) 등의 특수한 값이 존재
실수의 이진법 표기
소수점 밑 i번째 자리의 크기는 1/(2^i)
부동 소수점 표기
- 부호 비트: 양수인지 음수인지 여부
- 지수: 소수점을 몇 칸 옮겼나?
- 가수: 소수점을 옮긴 실수의 최상위 X 비트
최상위 비트 1은 생략하므로 가수부가 52비트면 총 53비트 표현할 수 있다.
64비트 실수형: 부호 비트(1), 지수 비트(11), 가수 비트(52), 유효자릿수(15(10))
실수 비교하기
하나. 비교할 실수의 크기들에 비례한 오차 한도를 정한다.
둘. 상대 오차를 이용한다.
대소 비교
비교할 때 항상 두 값이 같은 경우, 즉 두 값이 아주 가까운 경우를 먼저 확인하고 처리해주어야 한다.
정확한 사칙연산
IEEE 표준에 의해 실수 변순들은, 정확하게 표현할 수 있는 값은 항상 정확하게 저장하도록 구현되어 있다.
64비트 실수형의 가수부는 52비트이므로 그 범위까지는 정확하게 표현할 수 있다.
추가적인 자료 구조를 도입해서 정확한 사칙연산을 구현할 수도 있다.
코드의 수치적 안정성 파악하기
프로그램의 실행 과정에서 발생하는 오차가 더 커지지 않으면 수치적으로 안정적이라고 한다.
실수 연산 아예 하지 않기.
- 곱셉과 나눗셈의 순서를 바꾸기
- 양변 제곱하기
- 실수 좌표를 써야 하는 기하 문제에서 좌표계를 가로 세로로 정수배 늘려 정수만을 이용하여 문제 풀기
더 읽을거리
『Clean Code』(인사이트): 변수, 함수의 명명법, 함수의 구성, 주석을 쓰는 법까지 깨끗하고 잘 구성된 코드의 여러 원칙과 적용 예를 보여준다.
실수 비교에 관한 심도있는 내용
