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. 모든 사람들이 만나는 시간. 모든 사람들이 만나려면 도착점에 먼저 들어온 사람은 가장 늦게 도착한 사람이 올 때 ..
Algorithm
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번 배열에 비행기..
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/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. Logic 완전탐색으로 이 문제를 풀게되면 2^40을 하면 약 1조정도가 나와 당연히 시간초과가 당연히 뜰것같았다. 그래서 시간복잡도가 O(logN)인 이분탐색을 써서 풀면되겠다는 생각을 했다. 이분탐색을 input의 반을 나눠서 왼쪽과 오른쪽 부분에 대해 탐색을 돌고 0~n/2까지의 구간의 부분수열의 합을 map에 넣어준다. n/2~n까지의 구간의 부..
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. Logic 기본 DFS, 백트래킹 문제지만 시간복잡도때문에 메모이제이션을 활용하여 시간복잡도를 줄여줘야 한다. 즉 DFS와 DP를 합친 문제. 여기서 dp배열이 의미하는 것은 input[ny][nx]까지 갈 수 있는 경우의 수이다. 그리고 원래 DFS에서는 갔던 곳을 또 가지 않도록 무한루프에 빠지지 않도록 vis배열을 갱신해줘야 하지만 여기서는 항상 작은곳으로만 가기 때문에 vis배열을 갱신해 ..
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..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1. Logic 이 문제를 풀 때 중요한 키포인트는 두 가지 이다. 1. 1번 건물의 건설이 완료되어야만 2번과 3번 건물의 건설을 시작할 수 있다. 2. 2번과 3번의 건설을 동시에 진행 될 수 있다. 1번 건물의 건설이 다 끝나고 2번과 3번 건물을 건설하지만 3번 건물을 지을동안 2번 건물이 완성되더라도 아직 3번 건물이 다 안지어졌기 때문에 4번 건물을 짓지 못한다. 이 말은 항상 최..
