KPU CE

문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 일단 크게 두가지 경우로 나뉜다. 1. 시간이 초과되서 상담을 그날 상담을 못하는 경우 2. 시간이 초과되지 않아서 그날에 상담을 할 수 있는 경우 일단 1번의 경우이다. 상담을 한다면 N보다 초과되어서 이날의 상담은 하지 못하므로 이날의 최대 dp의 값은 i+1의 값이 된다. -> 이날 상담을 안하고 다음 날 한다. 2번의 경우 1.상담을 할 수 있..

문제1 https://www.acmicpc.net/problem/17122 17122번: 체스 각 테스트 케이스에 대해, 주어진 두 칸이 같은 색이면 “YES”를, 아니면 “NO”를 출력하시오 (따옴표는 제외). www.acmicpc.net 문제 해결 체스판을 직접 3차원 배열로 구현하였다. A~H 부여하고 배열에서 직접 찾아 색깔을 알아내고 표기법2는 입력된 숫자의 위치를 찾아서 색깔을 알아냈다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include #include using..

문제 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 문제 해결 1~K까지 물건을 하나씩 넣어보면서 만약 물건의 무게가 더 크다면 패스 무게가 더 적다면 i-1값과 현재 현재 물건 가치 + 남은 무게의 dp값(하나씩 갱신 하므로 이 dp의 값은 남은 무게의 최대값이다.) 을 비교해서 더 큰 값을 dp에 넣는다. 이 방법을 K까지 반복하게 된다면 마지막 K무게에서의 마지막 물건의 ..

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 해결 스택문제라서 최대한 스택으로 풀어보려 처음에는 선택한 수부터 선택한 수보다 큰 수가 나올 때까지 작은 수들을 스택에 넣은 다음 스택에 있는 수들을 차례대로 꺼내어 꺼낸 수의 인덱스~선택한 수보다 큰수 인덱스 까지 다시 오큰수를 구하는 알고리즘을 구현했는데 38%에서 시간초과가 나서 다른 블로그를 참고해서 풀었다.... 일단 처음 수를 스택에 넣는다. 그 다음수와 현재 수를 비교했을 때 만약 현재..

문제 https://www.acmicpc.net/problem/17124 17124번: 두 개의 배열 정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있 www.acmicpc.net 문제 해결 A[i]를 하나 택하고 A[i]보다 작은 것들 중에 가장 큰 B[j], A[i]보다 큰 것들 중에 가장 작은 B[j]가 답이다. 이것을 구하는데 큰것 작은것 두개의 이분탐색을 만들어서 두개의 절대값을 비교하였다. 만약 작은것 중에 A[i]보다 작은 것이 없으면 B 배열에서 가장 작은 값인 B[1] 만약 가장 큰 값이 없을 경우 문제에서의 최대값인 10..

문제 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 해결 1. 그 자리에서 3을 점프뛰면 앞, 앞앞, 앞앞앞까지 탐색하는데 현재 dp의 값+1과 탐색한 자리에 dp값과 비교해서 작은 값을 선택한다. 2. 만약 그 자리가 끝이거나 넘어서면 결과값의 dp이므로 현재 자리의 dp값과 결과값dp를 비교해서 작은값이 결과값dp가 된다. 코드 12345678910111213141516171819202122232425262728293031..

문제 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 해결 1. 가장 긴 증가하는 부분 수열과 비슷하게 현재 자기 자신의 길이를 dp [i]에 저장했다. 2. A = {10, 30, 10, 20, 20, 10}인 경우에서 가장 긴 감소하는 부분 수열은 30, 20 , 10이다. 3. 처음 10은 뒤에 숫자가 없으므로 자동으로 dp[0] = 1이다. 4. 그다음 30..

이번 시간에는 다이내믹 프로그래밍을 알아보도록 하겠습니다. 다이나믹 프로그래밍은 재귀적으로 문제를 해결할 때 불필요하게 같은 연산을 하는 것을 없애고자 만들어진 알고리즘 기법입니다. 대표적인 예로 피보나치 수열을 예로 들어서 설명하겠습니다. 피보나치수열 피보나치수열은 0,1로 시작하고 그다음 피 보나 치수는 앞에 두 수를 더한 값이 됩니다. Ex) 0,1,1,2,3,5,8,13,21,34,55,89.... 피보나치수열을 재귀적으로 구현했을 경우 코드는 다음과 같습니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 #include using namespace std; int fibo(int n){ if(n == 1){return 1;} else if(n == 0){return 0;} return ..

문제 https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 문제 해결 1. 입력받을 때부터 정렬된 상태이다. 2. 입력받고 그 해당하는 노드가 앞에 몇 명 있는지 확인한다. 3. 만약 앞에 2 사람이 있으면 두 칸 뒤에 앉으면 된다. 4. 하지만 두 칸 뒤에 사람이 이미 있으면 그 다음칸으로 가서 다시 확인한다. 5. 2~3단계를 반복한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

너비 우선 탐색이란? -큐를 이용한 탐색 방법으로 한 노드로부터 이동할 수 있는 노드들을 큐에 넣어서 탐색하는 방법이다. -DFS와 달리 깊이 들어가지 않음으로 구하려는 해가 깊이 들어있지 않을 때 효율적이다. -DFS와 달리 반복문을 통해서 구현한다. 개념 설명 위와 같은 루트가 1인 트리가 있다. 이 트리를 큐의 변화와 탐색 순서를 보면서 이해해보자. -처음 루트 1을 방문했을 때 큐 2 3 트리 -큐에 있는 노드인 노드 2와 노드 3을 방문하고 노드 2와 노드 3에 연결된 노드들을 큐에 넣는다. 큐 5 4 9 6 트리 -큐에 있는 노드들 방문 후 자식 노드들을 똑같이 큐에 넣는다. 큐 7 8 10 트리 -큐에 있는 나머지 노드들 방문 큐 트리 탐색 완료! 탐색 순서 1-2-3-5-4-9-6-7-8-..