[종만북 요약] 1~3. 문제 해결 시작하기 (PS 문제 해결 단계와 좋은 코드를 위한 조언)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)을 읽으며 유용한 내용을 정리해 보도록 하겠습니다. 모든 내용을 요약하는 것은 아니며, 대회에 포커싱을 맞춘 부분은 다루지 않을 수도 있습니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 프로그래밍은 문제 해결이다.

2. 간결하고 모듈화된 코드를 짜라. 이는 버그를 줄여주고 디버깅 효율을 높여준다.

3. 자주 범하는 실수에 대한 유형을 알아두자.

---

프로그래밍은 문제 해결이다.

1장에서는 알고리즘에 대한 코딩에 대한 저자의 철학과, 앞으로 다룰 주제에 대한 간략한 맛보기(?)가 제공된다. 거기에 배운 지 오래되어 기억의 저편에 묻혀 있거나, 생각해보면 좋은 꿀팁들에 대해서도 조언을 아끼지 않는다. 이번 글에서는 그런 다양한 조언들 중, 메모할만 한 것들을 기록한다.

예시 문제 : 록 페스티벌 (난이도: 하, 문제 ID : FESTIVAL)

 

프로그래밍 대회에서 배울 수 있는 것들

1. 시간과 메모리 제한을 항상 염두에 두게 됨
2. 정담과 오답의 여부가 훨씬 명확히 가려짐
3. 성능 정보가 바로 제공되어 빠른 수정에 유용
4. 프로그램의 작은 부분에 집중할 수 있는 계기가 마련
5. 경쟁은 실력을 늘리는 좋은 동기가 됨

 

프로그래밍 문제를 해결하는 6가지 스텝

문제 해결 전략에는 다음과 같은 것들을 고려하면 좋다.

• 비슷한 문제를 풀어본 적이 있는가?
• 단순한 방법으로 풀어볼 수 있을까(예를 들어 Brute-force)?
• 내가 문제를 푸는 과정을 수식화할 수 있을까(대표적으로 DP)?
• 문제를 단순화할 수 없을까?
• 그림으로 그려볼 수 있을까?
• 수식으로 표현할 수 있을까?
• 문제를 분해할 수 있을까?
• 뒤에서 생각해서 문제를 풀 수 있을까(문제에 내재된 순서를 바꿔보기)?
• 순서를 강제할 수 있을까?
• 특정 형태의 답만을 고려할 수 있을까?

 

좋은 코드를 짜기 위한 원칙

• 간결한 코드를 작성하기 : 간결할수록 오타나 버그가 생길 우려가 적고, 디버깅이 쉬워진다.
• 적극적으로 코드 재사용하기 : 코드를 모듈화하여 사용하기
• 표준 라이브러리 공부하기
• 항상 같은 형태로 프로그램을 작성하기
• 일관적이고 명료한 명명법 사용하기
• 모든 자료를 정규화해서 저장하기 : 예를 들어, 유리수를 표현한다면 9/6 과 3/2 는 같은 값이므로 동시에 존재해서는 안된다.
• 코드와 데이터를 분리하기 : 예를 들어 각 월에 대한 정보를 담는다면, Switch 문 대신 배열을 쓰는 것이 더 낫다.

 

 

자주 하는 실수

• 배열 범위 밖 원소에 접근 : 아래 코드를 보자.
• int array[10], t; // 아래는 어떤 결과가? array[10] = 10; // 런타임 에러도 발생하지 않는 찾기 어려운 버그 발생!
• 일관되지 않은 범위 표현 방식 사용하기 : [a, b) 를 주로 사용하며, [a, b], (a, b], (a, b) 등을 혼용하여 사용하는 것을 자제하자.
• Off-by-one 오류 : 0 이 시작점인지, 1 이 시작점인지 체크하기
• 컴파일러가 잡아주지 못하는 상수 오타 : 간혹 상수값으로 설정한 데이터가 잘못되었을 수도 있다.
• 스택 오버플로 : 재귀 호출의 깊이가 너무 깊어지지 않도록...
• 다차원 배열 인덱스 순서 바꿔쓰기
• 잘못된 비교 함수 작성 : 아래 성질을 알아두자.

그런 관점에서, 왼쪽 코드는 4번 조건을 만족하지 못하고 있다. 이를 올바르게 수정하면 오른쪽 코드처럼 바꿀 수 있다.

 

• 최대, 최소 예외 잘못 다루기 : 대표적으로 소수 판별 프로그램에서는, 1과 2에 대해 모두 고려를 해 주어야 한다.
• 연산자 우선순위 잘못 쓰기

if (b & 1 == 0) /* ... */

// 위 문장은 사실 아래와 동치이다 :

if (b & (1 == 0)) /* ... */

 

• 너무 느린 입출력 방식 선택 : cin 보다 printf 가 더 빠르긴 하다.
• 변수 초기화 문제
• 산술 오버플로 문제
  • 너무 큰 결과 : int 대신 long 사용을 고려
  • 너무 큰 중간값 : 계산 과정에서 너무 큰 값이 나오지 않도록 연산 순서를 조정
  • 너무 큰 무한대 값 : 때로는 INT_MAX 같은 값 대신, 987,654,321 같은 Magic Number 를 쓰는 것도 고려하기
  • 자료형의 프로모션 : 정수형보다는 실수형이, 부호 있는 정수형보다 부호 없는 정수형이 우선됨을 기억하자

 

실수 연산의 어려움

실수 연산의 경우, 오차가 생기기 때문에 값의 엄밀한 비교가 생각보다 어렵다. 이 경우, 실수 연산에 있어 절대 오차와 상대 오차를 전부 고려하는 것이 좋다.

...때로는 실수 연산을 아예 하지 않을 수 있는 방법을 찾는 것이 나을 때도 있다! 😅

 

 

읽을거리

범위 표현이 왜 [ ) 인지, 그리고 index 를 왜 0 부터 읽어야 하는지에 대한 다익스트라 선생님의 생각

클린 코드 (깨끗한 코드를 위한 방법론)