KPU CE

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

그래프의 탐색이란 루트부터 아래 노드들 까지 모든 정점을 방문하는 것이다. 깊이 우선 탐색(DFS)이란? 깊이 우선 탐색은 트리나 그래프에서 한 루트로 최대한 깊숙이 들어가서 탐색한 후 다시 돌아와 다음 루트도 깊이 탐색하는 방법이다. 일반적으로 재귀 호출을 사용하여 구현한다. 단순 검색 속도는 BFS보다 느리다. 장점 1. 목표 노드가 깊이 있으면 빨리 구할 수 있다. 2. 매번 기억하는 노드가 하나이므로 저장 공간의 수요가 적다. 단점 1. 목표노드가 없는 경로의 깊이 빠질 수 있다.-> 시간이 많이 걸릴 수도 있다. 알고리즘 설명 그림과 같이 루트가 1인 트리가 있다. 루트가 1이므로 루트 1에 대하여 DFS를 하면 최대 노드 3까지 내려가게 된다. 다음 루트는 이제 노드 2가 되어서 노드 2에 대..

문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제해결 1. 다이나믹 문제이지만 재귀를 이용하여 풀었다. 2. 각 DAY마다 재귀를 이용하여 상담이 가능한 날짜를 탐색했다. 코드 1234567891011121314151617181920212223#include using namespace std;int N,Max = 0;int ary[16][2];void DFS(int node,int count){ if(count >= Max){Max = count;} for(int i = node;iN){continue;} DFS(ary[i][0]+i,count+ary[i][1]); } ..

문제 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 이 문제는 나도 다른 사람의 풀이를 보고 알았다. 다이나믹 프로그래밍은 너무 어려운듯하다. 문제해결 1. 10,20,10,30,20,50 이 수열A로 있으면 맨 처음 인덱스인 10의 대한 dp[0] = 1(길이) dp[1] = 2 dp[2] = 1 이런식으로 한다. 2. 처음 인덱스부터 자기자신 전까지 탐색를 한다..

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

문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 해결 1. 인접 리스트로 정점들을 저장한다. 2. 1~N까지 방문하지 않은 노드들을 DFS 한다. 3. 방문할 때 마다 cnt를 해준다. 코드 1234567891011121314151617181920212223242526272829303132333435#include #include #define Max 1001using n..

문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 1. DFS를 이용하여 1~N까지의 숫자를 탐색한다. 2. ex) 1에 대하여 탐색한다면 1에 대하여 깊이 탐색한 후 지나는 모든 노드들을 visit 한다. 3. visit이 true이면 map [1][j] = 1로 인접 행렬을 만든다. 코드 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 ..

최소 공통조상이란? 두 노드의 조상이 처음으로 같은 경우를 최소 공통 조상이라고 한다. 지금부터 최소 공통 조상을 구하는 알고리즘을 알아보도록 하겠다. 위와 같이 트리가 하나 있다. 여기서 1이 루트라 하고 각 깊이를 구하면 다음과 같다. 여기서 노드 3과 노드 8의 최소 공통 조상은 그림과 같이 노드 2인 것을 알 수 있다. 하나 더 예시를 보자면 노드 8과 노드 10의 최소 공통 조상은 노드 10인 것을 알 수 있다. 바로 본론으로 들어가자면 최소 공통 조상 알고리즘은 1. 두 노드의 깊이를 확인한다. 2. 만약 하나가 다른 노드보다 작다면 깊이-1을 해준다. 3. 만약 깊이가 같다면 두 노드 모드 깊이 -1를 해준다. 4. 깊이-1 해주면서 만약 노드가 같아지는 지점을 찾는다. 5. 같아지는 지점이..

인접 행렬 위와 같이 무방향으로 노드들이 이어져 있다. 이제 이 그래프를 저장하는 2차원배열 ary[6][6]를 만들어준다. 그리고 노드a과 노드b가 이어져있다는 것을 배열로 표현해준다면 ary[a][b] = true, ary[b][a] = true 로 표현해줄 수 있다. 하지만 여기서 단방향 그래프로 만들고 싶으면 예를 들어 a->b인 노드이면 ary[a][b] = true 라고만 해주면 된다. 이렇게 표현하게 된다면 위의 그림은 ary[6][6]의 크기의 배열이 필요하다(ex. ary[5][4] = 1) 이걸 배열로 나타낸다면 아래와 같다. [0] [1] [2] [3] [4] [5] [1] 0 1 0 0 0 [2] 1 0 1 0 0 [3] 0 1 0 0 1 [4] 0 0 0 0 1 [5] 0 0 1 ..