재원블로그 재원블로그

이 문제는 dfs를 이용하여 풀었다. 트리의 지름을 구할 때에는 우선 어느 한 점을 잡아 dfs를 돌려 가장 먼 곳(노드 수 or 가중치)의 노드를 찾고, 그 노드에서 한번 더 dfs를 돌려 가장 먼 곳을 찾으면 된다. 이를 그대로 코드로 구현하면 정답이 나온다. #include #include #include #include using namespace std; #define MAX 100000 int V; vector edges[MAX + 1]; int leaf; int maxCost; bool visited[MAX + 1]; void findLeaf(const int start, const int cost) { visited[start] = true; for (int i = 0; i < edges[..

이 문제는 구현으로 풀었다. 문제 카테고리를 보면 분리 집합, 그래프 등이 나오는데 입력 크기가 작아 구현으로도 풀렸다. 이 문제의 핵심은 진실을 아는 사람이 한명이라도 있는 파티에서는 진실을 말할 수 밖에 없고, 그 파티에 참가한 모든 사람이 진실을 알게 된다는 것이다. 그러나 위의 핵심을 가지고 풀어도 정답이 나오지 않을 때가 있는데, 이는 진실을 알고 있는 사람이 입력 마지막에 전부 몰려있는 경우이다. 이 경우 파생되는 인원들을 제대로 체크하지 않고 넘어갈 수 있기 때문이다. 그래서 진실을 알고 있는 사람들을 마킹하는 함수를 M번 반복하여 정답을 찾을 수 있었다. 만약 파티가 10개이고, 맨 마지막에만 진실을 알고 있는 사람이 있는 파티가 존재한다고 가정하면 최악의 경우 각 루프마다 한명씩 추가가 ..

이 문제는 투 포인터를 이용해서 풀었다. 배열의 최대 길이가 10만이므로, O(N log N) 이하의 알고리즘을 고안해야 한다. 투 포인터를 사용할 경우 최대 2번씩밖에 각 요소를 접근하지 않으므로, O(N) 시간이 걸려 시간 안에 맞출 수 있다. #include #include using namespace std; #define MAX 100000 int N, S; int arr[MAX]; int input() { cin >> N >> S; int acc = 0; for (int i = 0; i > arr[i]; acc += arr[i]; } return acc; } bool isBaseCase(const int acc) { if (acc < S) { cout

이 문제는 그리디, multiset을 이용해서 풀었다. 이 문제에서 핵심 아이디어는 비싼 보석을 가장 작은 가방에 넣는 것이다. 보석의 경우 가격이 비싼 순으로, 같다면 가벼운 순으로 정렬을 해주고, 가방의 경우 multiset에 집어넣었다. multiset을 처음 사용해봤는데, set과 다르게 중복을 허용하고 나머지는 같다. 또한 set, multiset 모두 기본적으로 오름차순 정렬이 되어있다고 한다. 보석을 순회하면서 multiset.lower_bound()를 통해 가장 적합한 가방을 찾고, 이를 빼주면 된다. #include #include #include #include #include #include #include using namespace std; int N, K; bool compare..

이 문제는 크루스칼 알고리즘을 이용해서 풀었다. 최소 스패닝 트리를 만드는 알고리즘에는 프림, 크루스칼 등이 있는데, 구현하기 쉽고 직관적인 크루스칼을 이용해서 풀었다. #include #include #include using namespace std; #define MAX 10000 struct node { int a; int b; int cost; }; int parent[MAX + 1]; void init(int V) { for (int i = 1; i > V >> E; vector nodes; for (int i = 0; i > a >> b >> c; node temp = { a, b, c }; nodes.push_back(temp); } s..

이 문제는 그리디 알고리즘으로 풀었다. 완전 탐색으로 가능해 보이지만, 직접 코드를 작성해보니 시간 초과가 났다. 각 단어에서 알파벳을 검사하고, 해당 위치에 대해 가중치를 10^n 단위로 매겼다. 이를 각 알파벳에 더해주고, 해당 가중치로 내림차순 정렬하여 순서대로 9부터 숫자를 매겼다. 이 방법으로 정답을 맞출 수 있었다. #include #include #include #include #include #include using namespace std; #define MAX 10 #define ALPHA 26 int N; string words[MAX]; map cost; map mappedNum; int calcPower(int power) { if (power == 0) { return 1; }..

이 문제는 그리디 알고리즘, 우선순위 큐를 사용하여 풀었다. A + B가 최소가 되게 하는 두 카드를 매번 고르면서, 카드들이 1개만 남을 때까지 반복하면 된다. 이 때 최소가 되게 하는 두 카드를 O(log N) 시간에 뽑을 수 있는 자료구조는 우선순위 큐이므로, 이를 이용하여 풀었다. #include #include using namespace std; #define MAX 100000 int N; int cards[MAX]; int solve() { priority_queue minPQ; for (int i = 0; i 1) { int a = minPQ.top(); m..

이 문제는 구현 문제이다. 문제 설명 자체가 좀 어려운데, 간단하게 말하면 해당 위치의 배열 값으로 위치를 계속 바꿔가면서, 순환되는 숫자들을 그룹으로 묶고, 그 그룹들 중 가진 숫자가 큰 두개의 그룹의 숫자를 곱한 값을 리턴하면 된다. 기본으로 주어지는 cards는 인덱스가 0부터 시작해 문제가 복잡해질 것 같아 새로 card 배열을 만들고 인덱스와 카드 숫자가 일치하도록 만들었다. #include #include #include using namespace std; #define MAX 100 int card[MAX + 1]; int maxSize; void init(vector& cards) { for (int i = 0; i < cards.size(); i++) { card[i + 1] = car..