본문 바로가기

C++156

[백준] 5557번 - 1학년 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 1학년 -> https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net F (Idx, PartialSum) : 0번째 수부터 Idx까지의 합의 개수 DP에 적용할 점화식을 다음과 같다고 하자. 그럼 점화식을 F(Idx + 1, PartialSum + number[Idx + 1]) + F(Idx + 1, PartialSum - number[Idx + 1])로 통해 올바른 등식의 .. 2021. 7. 27.
[백준] 2186번 - 문자판 (C++) 문제 및 풀이 문졔) 백준 - 동적 계획법 (Dynamic Programming) - 문자판 -> https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net F(x, y, index): 점 (x, y)에서 index이후의 부분 문자열을 만들 수 있는 경로의 개수 점화식을 다음과 같이 설정 후, 모든 문자판을 순회하면서 F(x, y, index)의 값을 더한다. C++ 소스코드) 2021. 7. 27.
[백준] 1448번 - 삼각형 만들기 (C++) 문제 및 풀이 문제) 백준 - 그리디 (Greedy) - 삼각형 만들기 -> https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 세 변으로 만들 수 있는 삼각형 중 세 변의 합의 최대를 구하는 문제. N이 100만이므로 O(nC3)으로 완전 탐색이 불가능한다. 최대만 구하면 되므로 모든 변을 내림차순으로 정렬한 뒤, 삼각형을 이룰 수 있는 변 3개가 존재하면 답을 출력한다. C++ 소스코드) 2021. 7. 27.
[백준] 1188번 - 음식 평론가 (C++) 문제 및 풀이 문제) 백준 - 수학 - 음식 평론가 -> https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 예제와 n과 m의 경우의 수를 관찰하며 해결했다. 소시지를 하나로 이어 붙인다. n개의 소시지를 무조건 m명의 평론가한테 주려면 소시지를 최대 m-1번 잘라 m개의 배수개로 토막 낸다. n과 m이 서로소일 때는 m - 1번 자르는 것이 답임을 알 수 있고, 서로소가 아닐 경우에는 m - 1번에서 n-1번 잘린 위치와 m - 1번 잘린 위치의 공통 위치만큼 제외해준다. 이 수는 최대공약수임을 알 수 있다. C++ 소스코드) 2021. 7. 27.
[백준] 9934번 - 완전 이진 트리 (C++) 문제 및 풀이 문제) 백준 - 트리(Tree) - 완전 이진 트리 -> https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 중위 순회(In-Order)가 주어졌을 때, 트리의 개형을 복원하는 문제. 트리의 Root -> Sub Left Tree -> Sub Right Tree 순으로 재귀적으로 탐색하면 해결 C++ 소스코드) 2021. 7. 14.
[백준] 1563번 - 개근상 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 개근상 -> https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net cache[ i ][ j ][ k ]를 길이가 i이고 지각(L)이 j번이면서 끝문자의 연속 결석 회수가 k번으로 정의한다. 가령, 'LOAA'는 cache[4][1][2]의 한 요소이고, 'OALAO'는 cache[5][1][0]의 한 요소이다. 결석은 세번 연속으로 하지 않는 이상 개근상에 영향을 주지 않기 때문에 끝에 연속된.. 2021. 7. 6.
[백준] 1351번 - 무한 수열 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 무한 수열 -> https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 친절(?)하게도 점화식이 주어졌다. N의 범위가 10^12까지이므로 배열로 memoization 하는 것은 불가능하다. 또한 N이 P와 Q로 계속 나누어지기 때문에 10^12까지 인덱싱 하는 것은 비효율적이다. 따라서 map을 이용하여 memoization을 통해 기존 Top-down 방식의 Dp를 구현했다. C++ 소스코드) 2021. 7. 6.
[백준] 18870번 - 좌표 압축 (C++) 문제 및 풀이 문제) 백준 - 정렬(Sorting) - 좌표 압축 -> https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net n이 최대 100만이기 때문에 O(nlogn)으로 짜야한다. 좌표의 값과 인덱스를 저장 후 값에 대하여 오름차순으로 정렬한다. 그 후 ans에 압축 적용된 값을 넣는다. C++ 소스 코드) 2021. 6. 29.
[백준] 10422번 - 괄호 (C++) 문제 및 풀이 문졔) 백준 - 동적 계획법 (Dynamic Programming) - 괄호 -> https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 괄호의 길이가 L인 올바른 문자열의 개수를 구하고자 할 때, L은 다음과 같이 구할 수 있다. solve(n)를 길이가 n인 올바른 문자열의 개수라 하면, 위의 문자열에서는 solve(L) = ∑ {solve(i - 2) * solve(L - i)}임을 알 수 있다. 또한, solve(i - 2)를 구하기 위한 작.. 2021. 6. 29.
반응형

티스토리툴바