PS
-
백준 1538 공 칠하기문제 2023. 7. 8. 20:59
https://www.acmicpc.net/problem/1538 1538번: 공 칠하기세준이는 가방을 하나 가지고 있다. 이 가방 속에는 N개의 공이 들어있다. N개의 공엔 색이 칠해져 있다. 세준이는 이 가방에서 서로 다른 두 개의 공을 하나씩 차례대로 고른다. 그 후에 두 번째www.acmicpc.net순서를 고려하지 않고 $N$을 자연수의 합으로 분할하는 방법 한 가지는 가방 속 공의 상태와 대응된다. 이 '상태'를 적절히 표현해보자. 예를 들어 $N=5$일 때, 아래와 같은 7가지 상태가 가능하다.$$(5), (3, 2), (4, 1), (2, 2, 1), (3, 1, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1)$$어떤 상태 $\sigma$에서 시작했을 때의 기댓값을 $D_\si..
-
백준 1187 숫자 놀이문제 2023. 7. 8. 15:46
https://www.acmicpc.net/problem/1187 1187번: 숫자 놀이2N - 1개(N = 2k, 1 ≤ k ≤ 10)의 정수가 있다. 주어진 수 중 임의로 N개를 뽑았을 때 이 합이 N으로 나누어떨어지도록 하는 N개의 수를 출력하는 것이 문제이다. 답이 여러 개일 경우 아무거나 한 개www.acmicpc.net$N$이 2의 거듭제곱 꼴이므로 적절히 재귀적인 아이디어를 사용하면 될 것이라는 추측이 가능하다. 풀이는 다음과 같다. 1. 전체 수들을 짝수와 홀수로 분류하면 한 쪽은 짝수 개, 한 쪽은 홀수 개 존재할 것이다.2. 이때 기우성이 같은 수끼리 더해서 새로운 수를 만들면 총 ${{2N-2} \over {2}} = 2 \cdot {{N} \over {2}} -1$개의 짝수를 얻는..
-
UCPC 2023 예선 후기대회 2023. 7. 2. 02:32
작년 이맘때 solved.ac 디스코드에서 UCPC 이야기를 하는 대학생들을 보면서 뭔가 부러웠던 적이 있었다. 그렇기에 대학생이 된 올해 UCPC는 꼭 참여하고 싶었고, 얼마 전 짜여진 ICPC 팀원들과 참여하게 되었다. 팀원은 이예린(abra_stone) 누나와 이서현(seorii) 형. 팀명은 딱히 생각나는 게 없어서, 이서현 형이 팀명을 정하는 도중 보낸 이모티콘에서 딴 "안아줘요"로 정했다. 우리는 아직 팀 대회는 커녕 팀 연습도 해본 적 없었기에 대회 시작 직전에야 작전 논의를 시작했다. 어디선가 본 후기글을 떠올려 이서현 형이 3k, 내가 3k+1, 이예린 누나가 3k+2번 문제를 잡기로 했다.(00:02)A번이 노솔 방지용 브론즈길래 빠르게 AC. 3k+1 규칙에 의해 D번으로 넘어갔다. ..
-
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++ 문법을 알고 있다는 가정 하에 읽을 수 있는 글이 될 것이다(별 찍기 같은 연습문제는 생략한다는 뜻이다). 또한 생략하는 알고리즘이 종종 존재할 수 있기에 이 시리즈를 공부함과..