분류 전체보기

[백준 11055번] 가장 큰 증가 부분 수열 (C++)

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 가장 큰 증가 부분 수열은 n이 최대 1,000이므로 백트래킹을 이용하는 경우 시간초과가 발생할 수 있습니다. 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 부분 수열의 첫 원소는 어느 숫자든 가능하며, 이후의 원소는 이전 원소보다 커야합니다. 따라서 시작 원소 이후, 첫 원소보다 큰 원소들에 대해 가장 큰 증가 부분 수열..

[백준 1912번] 연속합 (C++)

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속합 문제는 n이 최대 100,000이기 때문에 모든 구간합(Prefix Sum)을 구하는 경우 (100,000 * 100,001) / 2의 경우의 수에 대해 구간합을 구해야하기 때문에, 구간합의 시간 복잡도가 O(1)이어도 시간 초과가 발생할 수 있습니다. 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 알고리즘은 아래와 같습니다. 기존 수열의 합 + 현재 숫자가 현재 숫자보다 큰 경우 즉..

[백준 2193번] 이친수 (C++)

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이친수 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 다이나믹 프로그래밍은 테이블 정의, 점화식 작성, 초기값 정하기의 과정으로 구분할 수 있습니다. 테이블 정의 이친수에서는 1이 연속으로 나타나지 않는다는 조건이 있기 때문에 0과 1을 구분할 필요가 있습니다. 이진수는 0또는 1로 끝날 수 있으므로, d[i][j]은 i자리이고, j로 끝나는 이친수의 개수라고 정의하였습니다..

[백준 12852번] 1로 만들기 2 (C++)

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1로 만들기 2 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. n에서 선택 가능한 경우의 수는 3가지 입니다. 3으로 나누기 2로 나누기 1 빼기 따라서 n/3, n/2, n-1 중에서 가장 적은 연산으로 1을 만들 수 있는 숫자를 선택하면 됩니다. 또한, 3으로 나누기, 2로 나누기, 1 빼기를 선택할 때마다 이전 숫자를 기록함으로써 경로를 추적할 수 있습니다. 아래는 Bottom-Up 방식의 다이나믹 프로그래밍을 이용한 코드입니다. #include using namespace std; ..

[백준 1149번] RGB거리 (C++)

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 집의 수가 최대 1000개이고, 각 집은 3개의 색을 선택할 수 있으므로, 백트래킹을 이용할 경우 시간초과가 발생할 수 있습니다. 다이나믹 프로그래밍은 테이블 정의, 점화식 작성, 초기값 정하기 구분할 수 있습니다. 테이블 정의 d[i][j]는 i번째 집의 색을 j로 칠할 때, 모든 집을 칠하는 비용의 최솟..

[백준 2579번] 계단 오르기 (C++)

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단 오르기 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 다이나믹 프로그래밍은 테이블 정의, 점화식 작성, 초기값 정하기으로 구분할 수 있습니다. 테이블 정의 d[n][i]은 n번째 계단까지의 최대 점수를 의미합니다. (i는 마지막에 연속된 계단의 개수) 연속된 세 개의 계단을 밟지 않아야 된다는 조건이 있기 때문에 2차원 배열로 구성하였습니다. 점화식 작성 d[n][1]은 연속된 계단의 개수가..

[백준 7795번] 먹을 것인가 먹힐 것인가 (C++)

https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 먹을 것인가 먹힐 것인가 문제는 누적을 이용하여 해결할 수 있습니다. 크기가 1인 A 생명체가 먹을 수 있는 먹이는 크기가 8인 A 생명체가 모두 먹을 수 있습니다. 따라서 생명체 A, B의 배열을 모두 정렬한 다음, 크기가 작은 A 생명체부터 먹을 수 있는 먹이의 개수를 구하고. 다음 크기의 A 생명체는 이전 A 생명체가 먹을 수 없었던 생명체..

[백준 5648번] 역원소 정렬 (C++)

https://www.acmicpc.net/problem/5648 5648번: 역원소 정렬 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니 www.acmicpc.net stoi, atoi 함수의 반환형은 Int형이기 때문에 역원소 정렬 문제에서 사용하면, Out of range 런타임 에러가 발생합니다. 따라서 stol을 사용해야합니다. 직접 stol을 구현하는 방법은 아래와 같습니다. long long stol(string & str){ long long result = str[0] - 48; for(int i = 1; i < str.size(); i++){ re..