본문 바로가기

알고리즘/시작하기

알고리즘/시작하기 2022. 1. 3. PS를 공부하는 뉴비들을 위한 안내서 문제 풀이(Problem Solving)를 잘 하기 위해서는 어떤 노력을 해야할까요? 시작하기 전에, 제가 대체 뭐하는 사람이길래 이런 글을 쓰는지는 알려드려야 글에 설득력이 생길거라고 생각합니다. 제가 지금까지 걸어온 길은 다음과 같습니다. '15 대학 입학, C언어와 C++ 기초 공부 시작 '15 교내 프로그래밍 대회 대상 --공백기 (군대), 개인 공부-- '19 5월 Codeforces Candidate Master 달성 '19 SCPC 5등상 '19 ACM-ICPC 서울대회 본선 진출 (ANZ1217) '19 11월 Codeforces Master 달성 '20 8월 Codeforces GrandMaster 달성 '20 SCPC 4등상 '20 ACM-ICPC 서울대회 특별상 (INPISA) '22..
알고리즘/시작하기 2020. 4. 23. 분할 정복 (Divide and Conquer) 분할 정복은 큰 문제를 분할하여 단순한 부분 문제로 만든 다음, 각 부분 문제의 답으로부터 전체 문제의 답을 이끌어내는 방식의 알고리즘입니다. 역시 분할 정복 자체만으로 풀 수 있는 문제는 그렇게 많지 않지만, 분할 정복은 다른 많은 알고리즘들의 기본 아이디어가 됩니다. 분할 정복으로 풀 수 있는 문제들의 예를 몇가지 살펴보도록 합시다. https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어..
알고리즘/시작하기 2020. 4. 16. 탐욕법 (Greedy) 탐욕법은 각 단계마다 지역적으로 최적인 선택을 하면서, 결국 전역 최적해를 찾는 방식의 알고리즘입니다. 조금 더 쉽게 말하자면, 각 단계에서 지금 "가장 좋아보이는" 선택을 하는 것을 반복해서, 결국 전체적으로 가장 좋은 선택이 되도록 하는 알고리즘을 말합니다. 하지만 이 방식을 모든 문제에서 쓸 수 있는 것은 아닙니다. 간단한 예를 들어봅시다. 다음과 같은 그래프가 있습니다. 우리는 1번 정점에 있고, 4번 정점까지 최단거리를 구하려고 합니다. 그리디하게 접근해봅시다. 현재 1번 정점에서 거리 5인 2번정점으로 가는 것 보다는, 거리가 2인 3번 정점으로 가는 것이, 현재 "가장 좋아보이는 선택"입니다. 하지만 실제 최단 거리는 그렇지 않음을 쉽게 알 수 있습니다. 따라서 탐욕법을 이용해 문제를 풀고자..
알고리즘/시작하기 2020. 4. 14. 완전 탐색 (Brute Force) 완전 탐색은 문제를 풀 때, 가능한 모든 경우를 살펴보면서 답을 찾는 방법을 말합니다. 일반적으로 가장 간단하고 쉽게 생각할 수 있는 방법이면서도, 제대로 구현했다면 절대 틀릴 수 없는 방법이기도 합니다. PS에 입문하는 사람들이 문제를 풀 때 많이 하는 실수 중 하나는 입력이 작은 문제에 대해 완전 탐색 풀이를 쓸 생각을 하지 못한다는 것입니다. 예를 들어 \(N\)이 최대 1000이고, 완전 탐색으로 \(O(N^2)\)으로 풀 수 있는 풀이가 있다면, \(O(NlogN)\)이나 \(O(N)\)에 동작하는 더 나은 풀이에 대해 생각할 필요가 없습니다. 물론 개인적인 공부를 위해서라면 충분히 가치가 있겠지만, 만약 목표가 지금 앞에 있는 문제를 푸는 것이라면 의미가 없다는 것을 알아야 합니다. 대회에서는..
알고리즘/시작하기 2020. 4. 10. 알고리즘의 시간복잡도 PS를 하는데 시간복잡도 얘기를 안하고 넘어갈 수는 없습니다. 알고리즘의 시간복잡도는 입력의 크기에 대해 알고리즘이 어느정도의 시간을 사용할지 근사적으로 표현한 것을 말합니다. 어떤 문제를 풀고 내 알고리즘이 제한시간 안에 동작하는지 확인해 보려면 알고리즘의 시간복잡도를 계산해보면 됩니다. 시간복잡도는 \(O(\cdots)\)로 표기하고, 입력이 \(n\)일 때 코드가 몇 번 실행되는지 괄호안에 함수를 넣으면 됩니다. 예를 들어, 다음과 같은 반복문은 \(O(n^2)\) 입니다. 1 2 3 4 5 6 7 for (int i = 0; i
알고리즘/시작하기 2020. 4. 10. Problem Solving 시작하기 이 글을 쓰는 시점에서, 제가 PS 공부를 본격적으로 시작한지 딱 1년이 되었습니다. 이제부터 제가 그동안 공부하고 이해한 것들을 이 블로그에 기록해 두려고 합니다. 아직 제 실력이 아주 좋은 편이라고도 할 수 없고, 지식이 많다고도 할 수는 없지만, 혹시 이제 PS의 세계에 발을 들이기 시작한 분들이 계신다면 그분들께 제 글이 도움이 되기 바랍니다. 이 블로그는 C++언어를 기반으로 쓰일 예정입니다. 기본적인 C++문법은 알고 있다는 가정하에 글이 쓰일 것이기 때문에, 언어를 배우기 위한 목적이라면 이 블로그는 적합하지 않습니다. PS에서 많은 사람들이 C++을 사용하는 이유는 간단합니다. 문제를 풀 때 시간과 메모리 제한이 있기 때문에, 실행속도가 빠른 언어가 유리합니다. 이를 위해 C언어를 이용하고..

티스토리툴바