https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 1. Logic 트리의 지름을 구하는 방법은 먼저 임의의 한 점에서 가장 거리가 먼 노드를 탐색한다. 이후 가장 거리가 먼 노드에서부터 다시 한번 가장 거리가 먼 노드를 탐색했을 때 거기가 트리의 지름이 된다. 2. Code #include using namespace std; int n; vector tree[10001]; bool vis[10001]; int deepestN..
알고리즘
https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 1. Logic 1 ~ n번까지의 정점을 순서대로 다 불을 붙혀보면서 그중에서 전부 연소하는데 걸리는 최소 시간을 구하면 됨. 가장 중요한 모든 그래프를 연소시키는 최소 시간을 구하는 법에 대해 설명할 것이다. 먼저 각 정점에서 모든 정점까지의 최단 경로를 알아햐 한다. 문제의 테스트케이스 1번을 보면 두개의 정점을 연결하는 동일한 간선이 ..
https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 1. Logic 우리가 이 문제에서 구해야 할 점은 2가지이다. 1. 모든 사람들이 만나는 시간. 2. 1분도 쉬지 않고 달려야 하는 사람들이 지나는 도로의 수 : 도착점에 가장 늦게 도착하는 경로의 갯수 이제 구하는 로직을 설명해 볼건데 순서대로 보면 1. 모든 사람들이 만나는 시간. 모든 사람들이 만나려면 도착점에 먼저 들어온 사람은 가장 늦게 도착한 사람이 올 때 ..
https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 1. Logic - 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.라고 문제에서 그러는데 이게 무슨말이지 싶을것이다. 아래 그림을 보자 아무 점 하나를 나는 1로 잡을 것이다. 1에서 경로가 가장 먼 노드를 찾으면 2 + 4 + 5 =11로 4번 노드이다. 이제 여기서 DFS를 다시 돌아서 나오는 정점까지의 거리가 트리의 지름인데 계산해보면 4번노드 -> 3번노드까지..
https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 1. Logic 정렬을 할 때 a에 b를 합친 문자열과 b에 a를 합친 문자열을 비교하여 더 큰 값을 가진 문자열을 비교하여 정렬한다. 2. Code #include using namespace std; int n; vector input; bool cmp(string a, string b) { if(a == b) return a < b; string ab = a..
https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 1. Logic 일단 문제를 이해하는데 너무 시간이 오래걸렸다.. ㅋㅋㅋㅋ 이해가 안가서 알고리즘 분류를 봤는데 유니온파인드여서 대충 풀이는 어떻게 할지 떠올랐지만 확실히 이해가 안가서 다른 블로그들을 참고했다. 일단 우리는 1번부터 g번까지 게이트가 있고 여기에 도킹을 시켜야한다. 배열은 0부터 시작하기 때문에 만약 1번 게이트에 도킹을 하면 0번 배열에 비행기..
1. 유니온 파인드 알고리즘이란? 대표적인 그래프 알고리즘으로 두개의 노드가 같은 집합에 속하는지 판별하는 알고리즘 서로소 집합 또는 상호배타적 집합(Disjoint-Set) 알고리즘이라고도 불린다 노드를 합치는 Union연산과 루트 노드를 찾는 Find연산으로 이루어져있다. 시간복잡도는 트리의 높이만큼 탐색하는 O(logN)을 가지게 된다. Union을 해주는 과정에서 한쪽으로만 노드들이 달리는 사향트리의 형태를 띄게 되면 O(n)이 되어버린다. 2. Default Logic 현재 7개의 서로 관련이 없는 노드가 존재하고 우리는 1, 2 / 4, 5 / 5, 6 노드를 서로 연결하려고 한다. 현재는 아무런 연관이 없기 때문에 각 노드들에 대한 root node는 자기 자신이다. 1번 노드와 2번 노드를..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 1. Logic 이 문제는 유니온파인드 알고리즘으로 풀 수 있다. 그 이유는 한명이 거짓말을 듣게 되면 다른 사람도 거짓말을 알기 때문에 알고있는 사람 모두 노드로 연결하여 처리해 주는 것이다. 그리고 나중에 연결된 노드들에서 진실을 알고있는 사람이 있다면 제외해주면 된다. 2. Code #include using namespace std; int n, m, k; int node[51]; vector par..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 1. Logic 펠린드롬을 확인 할 때 문자를 뒤집어서 봤을 때 똑같으면 펠린드롬인데 이렇게 구현해버리면 시간복잡도가 2000 * 1000000 == 약 20억 정도 나오기 때문에 제한 시간 안에 풀지 못한다. 그래서 나는 재귀를 통해서 인덱스를 +1 -1씩 해주었고 펠린드롬이면 dp[start][end]에 1을 아니면 0을 넣어서 메모이제이션 해줬다. 2. Code #include using namespace std; int dp[2..
https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1. Logic 각 PD들이 뽑은 가수의 순서대로 공연순서를 정하는 것이기 때문에 순서를 정할 때 사용하는 위상 정렬을 사용할 수 있다. 처음 입력을 받을 때만 잘 받아주면 어려움 없이 풀 수 있다. 테스트케이스를 예시로 보면 1 > 4 > 3 순서대로 받아줘야 하기때문에 1 > 4 4 > 3 끊어서 입력받아줘야 한다. 2. Code #include using namespace..
