PS 입문
-
3. 시간복잡도, 공간복잡도, big-O notationPS 입문 2023. 6. 30. 01:55
앞 글들에서 효율적인 알고리즘의 중요성과 효율적인 알고리즘을 만드는 하나의 방법에 대해 알아보았다. 이쯤에서, 효율적인 알고리즘이란 무엇인가? 라는 고민을 해 볼 필요가 있을 것이다. 가장 근본적인 대답은, 프로그램의 실행 시간과 메모리가 적은 알고리즘이 효율적인 알고리즘이라는 것이다. 그렇다면 무엇이 실행 시간과 메모리를 결정하는가? 간단히 말하면 다음과 같다.실행 시간 : 프로그램이 실행되는 동안의 총 연산 횟수에 비례한다. 다양한 연산자의 작동(+, -, &, ||, ...), 값의 대입과 변경 등 기본적인 실행이 총 몇 번 일어나는지 생각해보면 된다. 물론 연산의 종류에 따라(비트 연산은 보통 다른 연산들보다 빨라 정수를 2로 나눈 몫을 계산할 때 /2보다 >>1을 선호하기도 한다), 또 기술적인..
-
2. 다이나믹 프로그래밍(DP)PS 입문 2023. 6. 22. 16:01
다이나믹 프로그래밍을 간단히 말하면, 주어진 문제보다 작은 문제를 풀어놓고 그것을 통해서 큰 문제를 풀어내는 방식의 알고리즘이다. 간단한 예시로는 점화식이 주어진 수열의 특정 항의 값을 구하는 문제가 있다. 잘 알려진 수열 중 피보나치 수열을 생각해보자. 피보나치 수열의 점화식은 다음과 같다. $F_0=F_1=1, F_n=F_{n-1} +F_{n-2} (n \geq 2)$ 이때 "피보나치 수열의 10번째 항($F_{10}$)을 구하시오"라는 질문에 대답하기 위해서는 종이에 "1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89"를 적게 된다. 구현 방식은 사람마다, 상황마다 다를 수 있지만 DP로 문제를 풀 때는 기본적으로 위와 같은 알고리즘을 작성하게 된다고 생각하면 편하다.실제 문제를 보..
-
1. PS란 무엇인가PS 입문 2023. 6. 20. 03:03
이 시리즈에서 다루는 PS는 컴퓨터과학 분야의 Problem Solving의 약자로, 대충 입력이 주어질 때 원하는 시행을 해내는 프로그램을 짜는 일이라고 생각하면 편하다. 이때 프로그램의 실행 시간과 사용 메모리에 제한이 걸려 있어, 이를 만족하는 선에서 가동하는 프로그램을 짜기 위해 우리는 알고리즘을 구상하게 된다.한 게임을 예시로 들어보자. 게임이 시작하면, 참가자에게 1부터 20까지의 정수들로 이루어진 길이 100의 수열을 알려준다. 참가자에게는 큰 종이와 펜이 주어진다. 참가자는 수열을 들은 후 원하는 만큼 준비 시간을 가질 수 있다. 준비 시간이 끝나면, 참가자는 5초마다 한 번, 총 100번의 질문을 받게 된다. 질문은 "$i$번째 수부터 $j$번째 수까지의 합은 얼마인가요?"의 형식으로 주..
-
0. 들어가기에 앞서PS 입문 2023. 6. 20. 02:54
solved.ac의 등장으로 지난 몇 년간 PS의 진입장벽은 상당히 낮아졌다. 솔브닥에서 제공하는 문제별 레이팅 시스템과 사용자들이 투표하는 태그 시스템, 클래스 등 자신에게 맞는 문제를 찾을 수 있는 방법이 늘어났기 때문이다. 그러나 아직도 어떤 순서대로 공부를 해야 하는지, 어떤 방식으로 공부를 해야 하는지 혼란을 겪는 초심자들을 백준 게시판, 에브리타임 등에서 종종 찾아볼 수 있다. 이 시리즈는 나의 PS 과외 경험을 토대로, PS 입문자에게 로드맵을 제공하기 위해 쓰여질 예정이다. 백준/솔브닥 계정이 있고, 기본적인 C++ 문법을 알고 있다는 가정 하에 읽을 수 있는 글이 될 것이다(별 찍기 같은 연습문제는 생략한다는 뜻이다). 또한 생략하는 알고리즘이 종종 존재할 수 있기에 이 시리즈를 공부함과..