Lee Jeongan

Development & Study Blog

알고리즘 문제 해결 전략

알고리즘을 공부하면서 문제에 대한 암기보다, 알고리즘 자체에 대한 개념을 학습하기 위해 읽기 시작한 책이다.

1장 문제 해결과 프로그래밍 대회

도입

세상에는 프로그래머라는 하나의 직업명으로 부르기 힘들 만큼 다양한 종류의 프로그래머들이 있다.

같은 직업을 공유하지만, 데이터베이스 프로그래머, 웹 프로그래래머, 게임 프로그래머는 모두 전혀 다른 환경에서 다른 언어와 도구를 써서 프로그램을 작성하고, 전혀 다른 문제를 고민한다.

과연 이런 분야 간의 차이를 뛰어넘는 좋은 개발자의 조건이 있을까?

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

프로그래밍을 하기 위해선 생각보다 더 많은 것들을 알아야 한다.

아무 생각 없이 키보드를 치고 있는 프로그래머 머릿속에서는 사용하고 있는 언어의 특징, 프로그램이 동작할 하드웨어와 운영체제에 관한 지식, 사용하고 있는 라이브러리들에 대한 유의사항들이 회오리치고 있다.

이외에도 고객을 위한 생각과 팀의 커뮤니케이션 등 다양한 능력을 가지고, 최선의 방법을 찾아내는 프로그래머가 되어야 한다.

이 책에선 이런 능력을 문제 해결 능력이라고 부른다.

그러나 문제 해결 능력은 추상적인 기술이기에 훈련하기가 매우 어렵다.

자기 개발을 하고 싶은 프로그래머들은 새로운 언어와 프레임워크, 개발 방법들을 계속 배워 나가지만 이들을 조합하는 방법에 대해서는 배울 곳이 없다.

단지 경험이 생기면서 나아질 것이라고 막연히 짐작할 뿐이다.

좋은 프로그래머가 되기 위한 좀더 나은 방법은 없을까?

프로그래밍 대회

프로그래밍 대회에 참가하는 것은 문제 해결 기술을 연마하기에 가장 좋은 방법이라고 할 수 있다.

다양한 종류의 프로그래밍 대회가 있지만 이 책에서 다루는 대회는 짧은 시간안에 빠르게 작성하는 능력을 겨루는 대회이다.

이때 요구사항은 현업에서 사용하는 형태가 아니라 어떤 값을 읽어서 어떤 값을 계산하는 프로그램의 형태이다.

대회에서 배울 수 있는 것

  • 프로그래밍 대회에서는 GUI를 사용하지 않기 때문에 문제에만 집중할 수 있다.
  • 명시적인 시간 제한과 메모리 제한이 있기 때문에 다양한 알고리즘을 결합하여 최적의 프로그램을 작성해야 한다.
    • 이는 의도적 학습에 가깝다.
  • 정답과 오답 여부가 훨씬 명확히 가려진다. 현업에서는 대개 코드의 정당성을 단위 테스트나 상호 간의 코드 리뷰를 통해 확인 하지만, 대회는 명확한 피드백을 준다. (훈련의 좋은 예)
  • 제풀한 프로그램의 실행 시간이나 메모리 사용량 관련 정보가 실시간으로 제공되기 때문에, 퍼포먼스를 고려할 수 있게 된다.
  • 대회 문제들은 규모가 작기 때문에 대부분 처음부터 다시 짜게 된다. 이 과정에서 평소 대형 프로젝트에서 놓치는 부분들에 집중할 수 있는 계기가 된다. (좋은 코드를 짜는 연습)
  • 경쟁하는 환경이기에 실력을 늘리기 위한 좋은 동기가 된다. (벽을 마주함)

이 책을 읽는 방법

책의 구성

전체 7부로 되어 있으며, 1부와 2부는 후반부에 다루는 주제들을 공부하기 위해 필요한 기본 지식을 다룬다.

이들은 프로그래밍 대회의 문제 해결 방법론, 코딩과 디버깅에 대한 주의사항, 알고리즘의 정당성 증명과 효율성 분석에 대한 내용들을 포함한다.

이 부분을 잘 이해하고 넘어가야 이후에 다루는 주제를 제대로 이해할 수 있다.

책의 나머지 부분은 모두 알고리즘 설계 기법과 자료 구조 등 문제 해결에 필요한 기술들을 소개하고 있다.

실제 문제를 풀어보고 책에 나와있는 방법과 비교하여 최선의 방법을 찾아보려고 노력해볼 것

필요한 배경지식

학부생 대상으로 쓰여진 책이기에 수학이나 전산학, C++, STL을 사용할 수 있다면 문제없다.

입문자를 위한 권장 사항

책 자체가 2권으로 나눠질 만큼 방대한 내용을 담고 있기에, 아직 소개하지 않은 기법이나 도구를 다루는 경우가 많다.

따라서 모든 장을 순서대로 읽기보다 가장 중요하고 기초적인 주제만 우선 소화한 뒤 다시 읽으며 빈 곳을 메꿔가는 쪽이 편하다.

추천 커리큘럼

장 번호 장 제목
2장 문제 해결 전략
3장 코딩과 디버깅
4장 알고리즘의 시간 복잡도 분석
6장 무식하게 풀기
7장 분할 정복
8장 동적 계획법
18장 선형 자료 구조
19장 큐와 스택, 데크
21장 트리의 구현과 순회
22장 이진 검색 트리
23장 우선순위 큐와 힙
27장 그래프의 표현과 정의
28장 그래프의 깊이 우선 탐색
29장 그래프의 너비 우선 탐색
30장 최단 경로 알고리즘

위 순서대로 진행하고 이후에 빈 챕터를 채우는 방식으로 진행해본다.

국내에서 참가할 수 있는 프로그래밍 대회

  • 한국 정보 올림피아드
  • ACM-ICPC
  • 탑코더
  • 구글 코드 잼
  • 기타 온라인 대회와 모의고사들

대회 준비를 위한 조언

  • 가능한 한 많은 문제 풀기
  • 온라인 채점 사이트 이용하기
  • 가능한 한 많은 프로그래밍 대회에 참가하기
  • 팀 단위 연습을 위한 조언
  • 팀 노트북 준비

느낀점

단순 알고리즘을 숙제하듯이 풀기 싫어서 유형을 명확하려고 읽기 시작한 책인데, 상당히 전문적이다.

프로그래머로써 생각해야 하는 부분 (언어가 달라지더라도 알고리즘은 동일)과 문제해결 능력까지 깊게 생각하고 쓴 책이라 도움이 될 듯하다.

프로그래밍 대회까진 생각이 없는데 과연 책을 다 읽어도 생각이 없을지..

이번 알고리즘 스터디에서 책에서 다루는 커리큘럼에 맞게 알고리즘 문제와 유형에 대해서 발표하면서 진행할 예정이다.

댓글남기기

참고