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 배열 두..