알고리즘 문제풀이/백준
-
[백준/BOJ] 11053번 가장 긴 증가하는 부분 수열 (C++)알고리즘 문제풀이/백준 2020. 12. 21. 16:59
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net DP 유형의 문제로, LIS(Longest Increasing Subsequence)의 개념을 알게된 문제였습니다. #include #include #include using namespace std; int dp[1001]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0..
-
[백준/BOJ] 1912번 연속합 (C++)알고리즘 문제풀이/백준 2020. 12. 20. 13:41
www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net DP 유형의 문제입니다. n까지 연속되는 합을 더해가다가 0보다 작아졌을 때는 0으로 초기화 후 연속합을 구하는게 포인트입니다. 따라서 이를 점화식으로 나타내면 다음과 같습니다. dp[n] = max(0, dp[n - 1]) + v[n] 마지막으로 1~n까지 각 구간에서의 합 중 최대값을 출력하면 됩니다. #include #include #include using namespace std; int dp[100001]; i..
-
[백준/BOJ] 1149번 RGB거리 (C++)알고리즘 문제풀이/백준 2020. 12. 20. 12:46
www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP 유형의 문제입니다. 입력값의 각 열은 R, G, B 색깔, 행은 집의 수를 의미합니다. 문제의 조건은 결국 같은 색이 인접하면 안된다는 것을 의미합니다. 따라서 n번째 집의 색이 R, G, B 였을 때 n-1의 색이 다른 색이 되게끔, 최소값을 가지게끔 만들면 됩니다. 그런데 색깔에 따라 점화식을 만들어내야하므로, 2차원 dp배열을 이용하면 다음과 같은 점화식을 만들 수 있습니다. d..
-
[백준/BOJ] 14889번 스타트와 링크 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 17:42
www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 삼성 역량 테스트 기출 문제 : DFS(조합) or 순열 next_permutation을 이용하여 팀을 나눠줍니다. (예를들어 0, 0, 1, 1 로 시작) 0은 start팀, 1은 link팀으로 나누어 각각의 합을 구하고 두 합의 차이의 최소값을 찾으면 간단히 해결할 수 있습니다. DFS를 이용하는 경우 조합을 구하여 true는 start팀, false는 link팀으로 나누어 동일하게 해결할 수 있습니다. #include #inc..
-
[백준/BOJ] 2579번 계단 오르기 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 17:14
www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP 유형의 문제입니다. 마지막 계단을 오를 때 다음과 같이 두가지로 경우로 나눠서 생각합니다. 연속 O 도착 연속 X 도착 연속 O 도착인 경우, 그 전 계단을 오른 건 무조건 연속 X 입니다. 왜냐하면 연속이 되어버리면 3계단 연속이 되어버려 문제의 조건을 만족할 수 없게 됩니다. 그래서 연속 O 도착의 점화식은 다음과 같이 나타낼 수 있습니다. dp[n][1] = dp[i - 1][0] + v[i] 그러나 연속 X 도..
-
[백준/BOJ] 2133번 타일 채우기 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 00:03
www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net DP 유형으로 이전에 풀었던 타일링 문제와 비슷한데, 살짝 어려워진 유형의 문제였습니다. 맨 오른쪽 끝에 하나를 놓는 경우 2*d[n - 1], 맨 오른쪽 끝에 두개를 놓는 경우 3*d[n - 2]로 다음과 같은 점화식을 도출해낼 수 있습니다. d[n] = 2*d[n - 1] + 3*d[n - 2] 그러나 주의할 점이 있는데 n = 4일 때 다음과 같이 새로운 모양이 생깁니다. 이러한 새로운 모양이 n이 4부터 짝수일 때마다 2개씩 생기는게, 이러한 경우를 고려하면 다음과 같은 점화식을 도출해낼 수 있습니다. d[n] =..
-
[백준/BOJ] 11727번 2×n 타일링 2 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 00:02
www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 11726번과 거의 비슷한 DP 문제입니다. 맨 오른쪽 끝에 하나를 놓는 경우 d[n - 1], 맨 오른쪽 끝에 두개를 놓는 경우 2*d[n - 2]로 다음과 같은 점화식을 도출해낼 수 있습니다. d[n] = d[n - 1] + 2*d[n - 2] /* Bottom-Up */ #include using namespace std; int dp[1001]; int main(void) { ios_base::sync_with_stdio(false)..
-
[백준/BOJ] 11726번 2×n 타일링 (C++)알고리즘 문제풀이/백준 2020. 12. 18. 23:59
www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net DP 유형의 기본 문제입니다. dp[n]은 가로길이가 n개인 바닥을 채울 수 있는 타일의 경우의 수를 의미합니다. 직접 몇개 그려가다보면, 채울 수 있는 타일의 경우가 1x2 직사각형 하나로 끝나는 경우, 2x1 직사각형 두개로 끝나는 경우 두가지입니다. 즉 dp[n]은 가로길이가 n-1개인 바닥을 채울 수 있는 경우의 수 + 가로길이가 n-2개인 바닥을 채울 수 있는 경우의 수입니다. 따라서 다음과 같은 점화식을 도출해낼 수 있습..