KPU CE

문제 https://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 알고리즘 풀이 1. 이차원 배열에 값을 입력받는다. 2. ck라는 boolean배열을 하나 만들어서 숫자를 뽑는 것을 체크한다. 3. 전체탐색을 해주면서 카운트를 1씩 올려준다. 4. 만약 카운트가 N의 절반이되면 팀이 반반으로 나뉜것이기 때문에 능력치를 비교해준다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net X문자열과 Y문자열이 있다고 하자. X 문자열은 X(1)~X(i)까지 있다고 하고 Y문자열은 Y(1)~Y(j)까지 있다고 하자. X(i)와 Y(j)가 같은 경우와 다른 경우가 있을 수 있다. -만약 X(i)와 Y(j)가 같은 경우라면 X(1)~X(i-1), Y(1)~Y(j-1)의 LCS길이를 구하면 된다. 그리고 마지막 문자가 추가됨으로써 +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.상담을 할 수 있..

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

이번 시간에는 다이내믹 프로그래밍을 알아보도록 하겠습니다. 다이나믹 프로그래밍은 재귀적으로 문제를 해결할 때 불필요하게 같은 연산을 하는 것을 없애고자 만들어진 알고리즘 기법입니다. 대표적인 예로 피보나치 수열을 예로 들어서 설명하겠습니다. 피보나치수열 피보나치수열은 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-..

문제 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/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 문제 풀이 1. 입력값이 주어지면 무방향 인접 리스트를 이용하여 데이터를 저장한다. 2. 인접 리스트를 모른다면 나의 블로그의 인접 리스트 포스팅을 보고 와야 한다. 3. 인접 리스트로 저장 후 DFS알고리즘을 통해 노드 1~N까지 DFS알고리즘을 돌려준다. 4. 여기서 포인트는 visit 배열과 visited 배열 두..

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제해결 1. 기존 BFS 문제에서 조금 변형된 문제이다. 나이트의 이동 방향를 ck함수에 추가한다. 2. 각 방향에 대해서 이동 가능/불가 여부를 판단한 후 큐에 넣어서 BFS알고리즘을 돌린다 3. 도착지의 x, y값이 나오면 BFS를 끝내고 다음 입력값에 BFS를 돌려주는 간단한 문제이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21..