알고리즘/PS 공부 방법
혹시 영어 잘 하시나요?
이 질문은 다양하게 해석될 수 있습니다. 학교에서 영어 등급이 높은지, 수능에서 영어 등급이 높은지, 영어 회화를 잘 하는지 등의 의미로 말이죠. 저는 영어 회화를 잘 하는지의 의미로 질문한 거였습니다. 사실 학교 영어나 수능 영어만 하신 분들은 여기서 잘 한다는 답변이 나오기 힘듭니다. 그 이유는 학교 영어 및 수능 영어와 영어 회화는 방향성 자체가 다르기 때문입니다. 특히 학교 영어는 문법을 잘 알아야 높은 점수를 받을 수 있습니다. 하지만 문법만 잘 알고 있다고 영어 회화가 잘 되는 것은 아니죠.
프로그래밍 언어도 '언어'입니다. 이전 페이지의 프로그래밍 공부 방법에서는 주로 프로그래밍 언어 자체에 대해서만 다뤘습니다. 영어로 따지면 영어 문법인 셈이죠. 영어 문법만 가지고 영어 회화를 잘 할 수 있는건 아니듯 프로그래밍 언어 자체에 대한 지식만 가지고 프로그래밍을 잘 할 순 없습니다, 여기서 필요한 것이 알고리즘과 자료구조입니다. 알고리즘과 자료구조를 깊이 있게 공부하면 이들을 자유롭게 변형하고 사용하며 더 수준 높은 프로그래밍을 할 수 있게 됩니다. 명심하세요, 프로그램 = 알고리즘 + 자료구조입니다. 프로그래밍 언어에 대한 지식만 가지고 프로그램을 만들기 힘듭니다.
이 페이지에서는 여러분이 알고리즘과 PS를 어떻게 공부하면 좋을지에 대해 다룹니다.
근데 PS는 뭔가요?
PS는 Problem Solving의 약자로, 주어진 문제를 최대 메모리, 시간 제한과 같은 제약 환경 속에서 알고리즘을 짜고 프로그래밍을 통해 해결하는 것을의미합니다.
어떤 언어를 사용해야 하나요?
사실 알고리즘/PS에 중요한건 알고리즘이지 언어는 아닙니다. 보통은 Python, C++, Java가 많이 사용됩니다. 혹은 사용하기 편한 다른 언어를 사용하셔도 상관 없습니다.
취업을 앞둔 분들은 보통 채용공고에 있는 언어를 주로 준비해가시는 편입니다.
어떤 책이나 자료를 통해 배워야 하나요?
자유롭게 기여해주세요!
만약 여러분이 이 부분에 추가하고 싶은 책이나 자료가 있다면 언제든지 추가해주세요! 맨 아래 GitHub에서 이 페이지 수정하기 버튼을 통해 이 페이지를 수정하실 수 있습니다. 수정 후 풀 리퀘스트를 남겨주세요.
아래 2권은 알고리즘이나 PS와 관련하여 평가가 좋은 책들입니다.
자신에게 맞는 책 찾는 법
아래 있는 책이 아니더라도 서점에 가서 몇 권을 골라 읽어보면서 자신에게 가장 잘 맞는 책을 찾으시는 것을 추천드립니다. 또한, 컴퓨터 관련 서적에서 흥미가 있는 책이 있으면 구매해보시는 것을 추천드립니다.
알고리즘 트레이닝 2판 - 프로그래밍 대회 입문 가이드
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략
이 외에도 후술할 CodeUp을 운영하고 계시는 분이 직접 집필하신 책도 있어 해당 책으로 먼저 입문하셔도 좋습니다.
어떻게 공부해야 하나요?
온라인 저지(Online Judge)를 활용해봅시다
온라인 저지는 프로그래밍 문제를 온라인을 통해 풀어보고 자동으로 채점까지 해주는 서비스를 의미합니다. 국내에서 운영되고 있는 대표적인 온라인 저지는 아래와 같습니다.
CodeUp (코드업)
알고리즘의 기초 문제부터 정보올림피아드의 기출 문제까지 풀어보실 수 있는 알고리즘 트레이닝 사이트입니다. 현직 정보 선생님이 운영하고 계시며 직접 집필하신 도서도 있습니다. 이 도서로 공부하셔도 좋습니다.
Baekjoon Online Judge (백준 온라인 저지)
아마 국내에서 가장 유명한 온라인 저지일겁니다. 작성 시점 기준 총 30283문제(채점이 가능한 문제는 29186문제)로, 세계적인 수준의 문제 수를 보유하고 있습니다. 또한 71개의 언어를 제공하고 있으며 난해한 프로그래밍 언어까지 지원한다는 특징이 있습니다. 고등학교, 대학교 대회의 기출문제는 물론 국내외 대회나 유저 대회의 문제까지 풀어보실 수 있습니다.
solved.ac
온라인 저지는 아니지만 위의 Baekjoon Online Judge의 문제들에 태그와 난이도를 붙이는 프로젝트이자 서비스입니다. 백준을 이용하는 많은 사람들이 이용하고 있으며 문제를 풀면서 여러분의 티어를 올려볼 수 있습니다.
JUNGOL (정올)
매년 정보올림피아드 대상 수상자를 배출하고 있는 한글과컴퓨터학원에서 운영하는 알고리즘 트레이닝 사이트입니다. 정보올림피아드나 다른 프로그래밍 대회 문제들을 풀어보실 수 있습니다.
프로그래밍 언어를 익히고 문제를 풀어봅시다.
바로 위의 섹션과 이어지는 내용입니다.
여러분이 프로그래밍 언어를 익히면서 풀어볼 수 있는 기초 문제로는 아래와 같은 문제가 있습니다.
기초 100제
정보컴퓨터 교사 연구회/카페에서 만든 문제입니다. C언어나 파이썬을 공부하고 계신다면 꼭 풀어보시기 바랍니다.
단, 위 문제들을 풀 때 참고, 설명, 예시 등은 최대한 보지 않고 풀어보세요.
solved.ac의 새싹 문제
프로그래밍 언어 사용에 익숙하지 않는 분들을 위한 문제입니다.
백준 단계별로 풀어보기
백준의 단계별로 풀어보기로 프로그래밍 또는 알고리즘 공부를 하면서 한 단계씩 풀어봅시다. 절취선 위쪽 단계까지 138문제입니다.
문제를 풀다가 막힌다면?
이 경우 어떻게 해야 할지는 사람마다 다르지만, 초보일 때는 일반적으로 1시간 이상씩이나 감이 잡히지 않는다면 더 이상의 고민은 의미가 없다는 의견이 많습니다(반대로, 감이 잡혔거나 잡힐락 말락 하거나 구현 중인 경우에는 계속 해봅시다). 특히 프로그래밍을 처음 시작하셨고 기초 100제를 풀고 계신 경우 [기초-종합] 또는 [기초-1/2차원배열] 문제가 생각보다 난관이 될 것입니다. [기초-종합]은 제목에 사용해야 하는 프로그래밍 문법이 숨었고, [기초-1/2차원배열]은 생각을 많이 요구하는 문제가 많이 때문입니다.
이런식으로 막힌다면 CodeUp의 질문 게시판, 백준의 질문 검색을 이용해보시거나 구글링을 해봅시다(코드업 1234번, 백준 1234번과 같은 형식으로 검색하시면 됩니다.). 이러한 풀이들을 참고하는 것은 좋습니다. 하지만 먼저 본인은 어떤 접근 방법을 사용했는지, 이 접근이 왜 떠오르지 않았는지 생각해봐야 합니다.
문제를 다 풀었다면
회고를 해봅시다. 먼저 어떻게 이 문제를 풀었는지 돌이켜보고, 더 개선할 수는 있었는지 확인하세요. 이 문제는 이러한 방법으로 풀면 된다, 이러한 방법으로 풀면 틀리거나 조건에 맞지 않거나 시간이 오래 걸리거나 메모리를 너무 많이 잡아먹는다는 깨달음도 얻을 수 있어야 합니다.
풀다가 막히는 것과 같이, 구글링을 통해 다른 사람들의 풀이를 보는것도 좋습니다. 이 문제는 이렇게도 풀 수 있구나 이러한 깨달음을 얻을 수 있습니다. (예를 들어, CodeUp의 기초 100제 중 마지막 문제인 [기초-2차원배열] 성실한 개미 문제는 처음 풀 때 힘들게 고민하다가 직관적으로 생각해낸 풀이를 적용하여 정확한 풀이를 받았는데, 해당 문제에 있는 2개의 모범 소스와 제 풀이에 큰 차이가 있었습니다. 이 경우 해당 모범 소스를 참고하며 문제를 푸는 또 다른 방법을 깨달을 수 있습니다.)
구구절절 써놨지만...
수학 문제를 풀 때, 적어도 학교/학원 선생님도 위와 비슷한 말씀을 하신 적이 있을겁니다(너무 안 풀리면 답지를 보는 것도 공부다, 답지나 선생님 풀이와 자신의 풀이를 비교해봐라 등). 사실 문제를 다루는 태도는 수학 문제와 이 문제가 크게 다르지 않다고 생각합니다.
이 알고리즘을 사용할 수 있을까?
알고리즘의 수행 시간을 예측하기란 엄청나게 어렵습니다. 이 코드가 실행될 CPU는 어떤 클록 속도를 가질지, 이 코드가 어셈블리/기계어가 된다면 어떤 ISA(명령어 집합) 아래에서 몇 개의 Instruction이 될지, CPU나 메모리의 여러 성능은 어떨지, ...
다행인 점은 C/C++ 기준으로 수행시간을 어느정도 예측 가능한 방법이 있습니다. 이 방법은 대회 참가자 사이에서 많이 사용하는 방법으로 알려져 있고, 알고리즘 문제 해결 전략 책에도 '주먹구구 법칙'이라고 소개가 되어 있는 방법입니다.
채점 환경의 여러 제약 조건 속에서...
컴퓨터는 1초에 1억회의 연산을 수행할 수 있다.
...고 가정할 수 있습니다.
시간 복잡도 중 Big O는 해당 알고리즘의 점근적 상한을 의미합니다. 따라서 수행 시간이 1초인 문제에 대해
일 때: 은 연산 횟수가 25억회이므로 못 풀지 않을까? 일 때: 은 연산 횟수가 50만회밖에 안되니까 풀 수 있지 않을까?
와 같은 예측이 가능합니다. 하지만 이렇게 계산했더니 3억회 정도가 나왔다면 어떨까요?
사실 1초에 1억회도 정확한게 아니고, Big O는 계산할 때 최고차항 이외의 항을 제외하고 상수도 모두 없애고, 알고리즘이 메모리 처리가 느린 등 이 법칙이 정확하지 않을 이유는 많습니다. 위의 3억회 정도도 경우에 따라 통할 수도 있죠.
그렇기에 알고리즘 문제 해결 전략 책에는 이 법칙을 적용할 때 1억의 10% 이하, 1억의 10배 이상에 해당할 때에만 적용하라고 조언하고 있습니다.