복습노트 복습노트

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단을 1계단이나 2계단 오를 수 있는데 최종적으로 n번째 계단에 도달했을 때 획득 할 수 있는 최대점수를 구하는 문제 입니다. 연속적으로 3계단을 밟는건 불가능합니다. 여기서 상태(status)를 표현하는 방법으로 2차원 배열을 사용하였습니다. 현재 밟고 있는 계단이 이전에 1계단을 밟고 왔는지, 2계단을 밟고 왔는지 표현해 주어야합니다. 예를 들어 dp[n][k] 라는 의미는 현재 n번째 계단에 있는데 k계단을 밟고 왔다는 의미입니다. 여기서 점화식을 세워주면 dp..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net n이 주어지면 n을 3으로 나누거나 2로 나누거나 1을 빼든가 해서 1로 되게하는 연산의 합이 최소를 구하는 것입니다. 1 ≤ n ≤ 1000000 예를 들어 n이 10이면 (10 -> 9 -> 3 -> 1) 총 3번의 연산이 최소가 됩니다. bottom-up 방식으로 dp를 이용해 해결하였습니다. 1) n이 2로 나누어떨어지면 dp[n] = dp[n-1]과 dp[n/2] 중에서 작은 값에다가 1을 더해줍니다. 2) n이 3으로 나누어 떨어지면 dp[n] = dp[n-1]과 dp[n/3] 중에서 작은 값에다가 1을 더해줍니다. 3) n이 2와 3 모두 나누어 떨어지면 d..

동적 계획법(Dynamic Programming) 1) 큰 문제를 작은 부분 문제들로 나누어 푸는 방법 2) 점화식 세우기 3) 메모이제이션(Memoization) 기법 사용 ex) 피보나치 수열 [1, 1, 2, 3, 5, 8, 13, 21, 34, ....] F(n) = F(n-1) + F(n-2) HTML 삽입 미리보기할 수 없는 소스 다음과 같은 피보나치 수열을 수행하는데 재귀적으로 이루어지면서 중복되는 함수가 많습니다. 예를 들어 n이 6일때 피보나치 수행도를 보면 F(3)이 3번이나 수행되었습니다. F(3)의 값은 1번만 알면되는데 재귀적으로 탐색하는 과정에서 중복적으로 계산된 것입니다. 이를 방지하고자 메모이제이션 기법을 사용합니다. 메모이제이션(Memoization) 부분문제를 계산한 결과..

문제 23820번: MEX $\textrm{mex}(S)$를 집합 $S$에 포함되지 않은 가장 작은 음이 아닌 정수로 정의한다. 길이가 $n$인 수열 $a_1, a_2, \cdots, a_n$이 주어질 때 $\textrm{mex}\left(\{a_i \times a_j \mid 1 \leq i \leq j \leq n \}\right)$을 구 www.acmicpc.net 수열이 주어지면 수열 각각의 원소들의 곱집합에서 없는 숫자중 가장 작은 정수를 출력하면 됩니다. 예를들어 N이 3이고 수열이 {0, 1, 2} 라면 곱집합은 {0, 1, 2, 4} 가 됩니다. 여기서 없는 숫자중 가장 작은 정수는 3입니다. N의 범위가 1부터 200만 이고 수열 a(i)의 범위 또한 0부터 200만 입니다. 단순히 모든..

문제 14565번: 역원(Inverse) 구하기 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 www.acmicpc.net 덧셈 역원(b)과 곱의 역원(c)으로 구하는 문제 입니다. 예를 들어 n = 26, a = 11이면 11 + b mod 26 = 0 을 만족하는 b와 11c mod 26 = 1을 만족하는 c를 구하는 문제입니다. b = 15 , c = 19입니다. 먼저 덧셈역원 b는 구하기가 매우 쉽습니다. 단순히 n에서 a를 빼주면 바로 그게 덧셈역원 입니다. 이제 곱역원(c)를 구하는게 관..

문제 24040번: 예쁜 케이크 Good Bye BOJ, 2021!이 열리는 오늘, 12월 31일은 종서의 생일이다. $N$ 명의 친구들은 종서에게 생일 선물로 예쁜 케이크를 만들어주려 한다. 여기에서, 예쁜 케이크는 다음과 같은 조건을 만족하는 www.acmicpc.net 직사각형 넓이 n(가로 * 세로)이 주어지면 가로 길이가 각각 1인 세가지 색상 천으로 딱 맞아 떨어지게 포장할 수 있는지 구하는 문제 입니다. 예를 들어 넓이 n이 8이면 (2 * 4) 둘레는 12이므로 세가지 색상천의 길이 3으로 나누어 떨어지므로 포장가능합니다. 따라서 우리는 직사각형의 둘레의 길이가 3의 배수인것을 알 수 있습니다. 가로의 길이는 3a + x 세로의 길이는 3b + y 로 설정해 놓았습니다. 따라서 3a + x..

문제 23888번: 등차수열과 쿼리 등차수열은 연속하는 두 항의 차이가 일정한 수열을 뜻한다. 연속한 두 항 중 뒷항에서 앞항을 뺀 값을 공차라고 한다. 초항이 $a$이고 공차가 $d$인 등차수열이 주어진다. 수열의 $i$번째 원소를 www.acmicpc.net 초항 a와 공차 d가 주어지면 쿼리의 수에 따라 합이나 최대공약수를 출력하는 문제입니다. 쿼리가 1이고 구간 l과 r이 주어지면 [a(l) 부터 a(r)] 까지의 구간에 있는 수열의 합을 구하는 것입니다. 쿼리가 2이면 구간 l과 r이 주어지면 [a(l) 부터 a(r)] 까지의 구강에 있는 수열들의 최대공약수를 구하는것입니다. 먼저 쿼리 1의 해당 구간에 있는 수열들의 합을 구하기 위해서는 prefix sum 알고리즘을 사용하였습니다. HTML ..

소수 1. 모든 자연수는 소인수들의 곱으로 표현 가능 2. 소수는 무한하다 (p1 * p2 * p3 ....* pn + 1) 소수인지 알아보는 방법 n이 합성수라고 가정하면, a * b = n 을 만족하는 (min(a,b) > 1) 인 (a, b)가 존재하므로 min(a, b) HTML 삽입 미리보기할 수 없는 소스 에라토스테네스의 체를 이용 시간 복잡도 : (O(nloglogn)) / 공간 복잡도 : O(n) 앞에서 부터 소수의 배수가 되는 수들을 전부 지워 가가는 것 HTML 삽입 미리보기할 수 없는 소스 최대공약수를 구해주는 유클리드 알고리즘 HTML 삽입 미리보기할 수 없는 소스 gcd(a, b)를 구하는 과정에서 max(a, b)가 절반이하가 되므로 시간복잡도는 O(log n) " 문제 크기가 ..