본문 바로가기

All154

[Stack] [BOJ 9012] 괄호 9012번: 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(conc www.acmicpc.net 풀이 문제 : BOJ 9012 괄호 유효한 괄호 (VPS : Valid Parenthesis)를 묻는 가장 기본적인 문제로, 스택을 활용해서 풀 수 있다. 문제에 설명이 복잡하게 나와있지만, 결국 괄호를 알.. 2020. 4. 11.
[DP] [BOJ 2579] 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 문제 계단을 한 번에 최대 2칸까지 올라갈 수 있을 때, (연속된 세 칸을 밟을 수 없다.) n번째 계단에 도달했을 때 얻을 수 있는 최대 점수를 구하는 문제 해석 이 문제에서 "N 번째 계단에서 얻을 수 있는 최대 점수.. 2020. 3. 30.
[DP] [BOJ 11052] 카드 구매하기 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 참고 : 이 문제는 막대 자르기 (rod-cutting 문제와 동일한 문제이다.) 문제 카드가 1개, 2개, 3개, ..., N개가 담긴 카드팩이 있을 때, (카드 팩의 가격은 다를 수 있다.) 카드 N개를 가장 비싸게 살 때의 가격을 구하는 문제 해석, 부분 문제, 시간복잡도 그림을 그려보면 "카드 2개를 사는 최대 가격", "카드 1개를 사는 최대 가격" 등의 부분 문제가 중복됨을 알 수 있다. 이를 좀 더 일반화해보자. N개의 카드를 사는 최대 가격은 (1 2020. 3. 25.
[DP] [BOJ 2163] 초콜릿 자르기 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 문제 N x M 초콜릿을 1 x 1 초콜릿으로 자르는 최소 횟수를 구하는 문제 해석 이 문제는 DP로도 풀 수 있고 수학으로도 풀 수 있는데, 여기서는 DP로 접근해보자. 우선, 초콜릿은 자르면 더 .. 2020. 3. 24.
[DP] [BOJ 1003] 피보나치 함수 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 피보나치 함수의 변형 문제로, f(n)을 호출할 때, f(0)과 f(1)의 횟수를 각각 출력하는 문제 (f = 피보나치 함수) 해석 오늘은 태블릿을 놓고와서 그림은 없다. 이 문제는 처음에 알쏭달쏭하다. 내가 풀어봤던 피보나치 함수는 함숫값만 구하면 됐는데, 호출 횟수를 구하라니? 그리고 사실은 문제가 2개다. 0을 호출하는 횟수와 1을 호출하는 횟수. 그래서 두 문제를 한꺼번에 풀다 보니 헷갈리는 부분이 있다. 하지만 결국 푸는 방식은 완전히 동일하다. 피보나치 함수에서 f[n] = f[n-1] + f[n-2]라는 식으로 풀었던 것처럼, (f(n)에서.. 2020. 3. 22.
[DP] [BOJ 1149] RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 수직선 위의 N개의 집이 있을 때, 인접한 두 집의 색(R, G, B 중 하나)을 같지 않게 칠하는 최소 비용을 구하는 문제. 무식하게 접근하기 + 중복되는 부분 문제 여느 때처럼 모든 경우를 탐색해 보았을 때, 모든 전체 경우의 수는 2 * 3^N이다. N 2020. 3. 20.

티스토리툴바