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..
분류 전체보기
그리디 알고리즘은 개념은 굉장히 단순하다. 말 그대로 탐욕적으로, 눈 앞의 가장 큰 이익을 추구하는 기법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 예제) 500원, 100원, 10원 동전이 무수히 많다고 가정할 때 가장 적은 수의 동전을 이용해서 1410원을 만든다고 하자. 이때 사용하는 동전의 개수는 몇개인가? 이 문제를 접했다면 일반적으로 최대 500원의 개수를 사용할 것이다. 그래서 500원짜리 2개로 1000원을 만들고, 100원짜리 4개로 400원을, 10원 동전 1개로 10원을 만들어 1410원을 완성할 것이다. 따라서 이 문제의..
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..
