KPU CE

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문자열은 너무 어려운 것 같다. 일단 스택을 사용하여 입력받은 문자들을 스택에 다 넣고 top을 하면서 하나씩 꺼냈다. 만약 ')' 문자가 먼저 오지 않고 '('가 먼저 온다면 NO를 출력 '('와 ')'의 개수가 틀리면 틀리므로 NO를 출력하게 하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..

문제 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.상담을 할 수 있..

문제 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/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/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 ..

문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 문제 해결 1. 인접 리스트로 데이터들을 받는다. 2. 다익스트라 알고리즘을 실행한다. 3. 다익스트라 알고리즘에서 만약 new_val이 더 작으면 trace배열의 trace[next_node] = node 로 해준다. 4. 이렇게 해주면 해당노드의 최단거리의 부모를 알 수 있다. 5. trace배열을 각 노드들 별로 출력해준다. 코드 1234567891011121..

문제 https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 문제해결 1.벡터에 정점과 가중치를 입력받는다. 2.DFS를 통해서 각 노드들마다 부모와 깊이를 알아낸다. 3.LCA알고리즘을 실행한다 3-1. 만약 두 노드가 같으면 출력한다 3-2. 두 노드가 같지 않고 깊이가 같으면 두 노드 다 깊이-1로 이동한다. 3-3 한 노드가 다른노드보다 깊이가 크면 큰 노드가 깊이-1로 이동한다. 4. 두 노드가 같아 질때까지 반복한다. 코드 ide...

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 이 문제는 최소 스패닝 트리 알고리즘을 사용하면 바로 풀리는 문제이다. 문제해결 1.vector v 를 사용하여 가중치,노드1,노드2 순으로 입력받는다. 2.가중치에 대하여 오름차순으로 정렬한다. 3.parent배열을 모두 parent[i] = i로 초기화 한다 (처음에는 모두 부모가 자기 자신이다 -> 모두 다 끊어진 상태로 시작한다,최소스패닝..