https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. Logic 조건대로 계산해보면 피보나치 수열과 같다는 것을 알 수 있다. 그대로 Topdown 방식으로 구현해줬다. 2. Code #include using namespace std; long long dp[91]; long long solve(int n) { if(n == 1 or n == 2) return 1; long long &ret = dp[n]; if(ret != 0) ..
백준
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/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. Logic 외판원 순회란 도시들(노드)이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌도 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제이다. 아래 그래프를 보자. 이 5개의 노드가 있을 때 순회를 할 수 있는 방법은 총 5가지이다. 1 > 2 > 3 > 4 > 5 2 > 3 > 4 ..
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번 배열에 비행기..
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까지의 구간의 부..
