https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 이 문제는 그래프 순회 문제이다. DFS를 통해 해결해야한다. 이미 지나간 파티에서도 거짓말을 못하는 파티를 검사해야하기 때문이다. #include #include #include #include using namespace std; int N,M; int visited[51]; int party[51][51]; int graph[51][51]; vector truePerson; void searchGrap..
Baekjoon Review
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. 알고리즘은 다음과 같다. 수의 변화는 전 요소와 5번째 전 요소를 합한 값과 같다. 이는 6번째 요소부터 규칙을 가지기 때문에 이를 코드로 변화시키면 된다. #include #include using namespace std; int N; long long dp[101]; int main() { int T; cin >> T; for (int i = 0; i < ..
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. 알고리즘은 다음과 같다. 주어진 입력을 배열에 담는다. dp[0]을 배열의 0번째 요소로 초기화한다. 이때 maxNum도 배열의 0번째 요소로 초기화한다. 배열을 순회하며 dp에 값을 누적시키고, 누적합과 배열의 i번째 요소 중 큰 값을 dp에 저장한다. 이는 누적합을 구할 때 자를 부분을 선정하는 것이다. dp는 3, -1, 3, 7, 3, 9, 14, ...으로 ..
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. 문제의 조건은 아래와 같이 변한다. 1 2 3 4 5 6 7 1 2 4 7 13 24 44 위 표를 통해 점화식을 세워보면 if N > 3 dp[N] = dp[N-1] + dp[N-2] + dp[N-3]이 성립한다. #include using namespace std; int N; int dp[11]; int main() { int T; cin >> T; dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int j = 4; j < 11;..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. 가방에 물건을 넣을 수 있는 조건은 아래와 같다. 현재 무게가 K이하면 계속해서 가방에 넣을 수 있다. DP배열을 이용하여 1번째 물건부터 i번째 물건까지 담을 수 있는 가장 최대 가치를 저장한다. 예제의 주어진 입력으로 이차원배열 DP를 채워보면 아래와 같은 결과가 나온다. 4 7 6 13..
https://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를 통해 해결할 수 있다. 문제의 점화식은 아래와 같다. 현재 검사하고하는 수 A가 배열에 저장된 수 B보다 클 경우 또한, 현재 배열에 저장된 수 B의 count가 최대 값이 아닌 경우 최대 값을 변경 현재 검사한 자리 수의 counter를 최대 값 + 1로 변경 #include #include #inc..
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 이 문제는 큐를 사용해서 해결할 수 있다. 알고리즘은 다음과 같다. N명이 원을 이루며 앉아있고, K번째 사람을 제거해야한다. 이는 K번째 요소를 큐에서 제거하는 방식으로 해결할 수 있다. 즉, counter를 통해 K번째 pop 했는지 검사한다. K번 pop하지 않았다면 다시 큐의 뒤에 삽입한다. #include #include using namespace std; int N, K; int main() { cin >> N >> K; queue q; vector result; int co..
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 DP를 통해 해결할 수 있다. 알고리즘은 다음과 같다. 입력된 두 개의 문자열을 비교하면서 LCS(최장 공통 부분 수열)을 찾는 문제로, 가능한 수열을 하나하나 비교하면 시간 초과이기 때문에, dp를 이용하는 문제이다. 입력 값으로 표를 만들어 보면 아래와 같은 표가 만들어진다. A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2..
