문제 풀이/백준 (BOJ)

[백준/BOJ] 2166번: 다각형의 면적 ( 벡터의 외적, CrossProduct ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2166 풀이 이 문제는 다각형의 면적을 소수점 첫째 자리까지 출력하는 문제입니다. 다각형의 면적을 구하는 가장 간단한 방법은 다각형을 삼각형으로 분해해서, 삼각형을 면적을 합하는 방법입니다. 그러나, 이러한 방식은 볼록 다각형의 경우에만 사용할 수 있는 방법입니다.  위의 이미지 같은 오목 다각형의 경우, 면적을 구하려면 전체 다각형을 삼각형으로 나눠서 더한 면적에서, 흰 부분의 삼각형 면적을 빼야 합니다.그런데, 어떤 기준으로 푸른 부분의 삼각형은 더하고, 흰 부분의 삼각형을 뺄 수 있을까요? 그 기준은, 삼각형을 이루는 변을 벡터로 변경했을 때 생성되는 벡터들이 회전하는 방향입니다.  푸른색 부분의 삼각형들을 이루는 벡..

2024. 7. 8.

문제 풀이/백준 (BOJ)

[백준/BOJ] 4386번: 별자리 만들기 ( Prim 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/4386 풀이이 문제는 주어진 별들을 모두 지나는 트리의 최소 거리의 합을 출력하는 문제입니다. 다른 말로 하자면, 별들 간의 거리를 최소로 하는 최소 신장 트리를 구하고, 그 신장 트리의 거리의 합을 출력하는 문제라고 할 수 있습니다. 최소 신장 트리를 구하는 알고리즘은 Kruskal과 Prim 알고리즘이 있습니다.이 글에선 Prim 알고리즘을 사용했습니다. Kruskal 알고리즘은 다른 문제 풀이에서 볼 수 있습니다. [백준/BOJ] 1197번: 최소 스패닝 트리( Minimal Spanning Tree ) - C++ 문제 풀이문제 설명 문제 링크: https://www.acmicpc.net/problem/1197 풀이이..

2024. 7. 5.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1197번: 최소 스패닝 트리( Minimal Spanning Tree ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1197 풀이이 문제는 그래프가 주어졌을 때, 그 그래프로부터 최소 신장 트리의 가중치 합을 출력하는 문제입니다. 여기서, 최소 신장 트리( Minimal Spanning Tree )는 주어진 그래프에서, 모든 정점을 지나는 트리 중에 가장 작은 가중치 합을 가진 트리를 말합니다. 이 최소 신장 트리를 구하는 알고리즘으로 Kruskal과 Prim 알고리즘이 있는데, 이 글에선 Kruskal 알고리즘을 사용했습니다.이 알고리즘은 가중치가 작은 간선을 우선적으로 선택하여, 신장 트리를 구성하는 알고리즘입니다.그 과정에서, 가중치를 기준으로 간선을 정렬해야 하고, 추가되는 간선이 순환 경로를 만드는지를 검사하는 기능이 필요합니다...

2024. 7. 4.

문제 풀이/백준 (BOJ)

[백준/BOJ] 4195번: 친구 네트워크 ( Union-Find 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/4195 풀이이 문제는 주어진 두 사람이 친구 관계를 맺었을 때, 이 두 명이 속한 친구 집합의 인원수를 출력하는 문제입니다. 여기서는 Union-Find 알고리즘을 사용해서 문제를 풀었습니다.Union-Find은 분리 집합들을 결합하고, 주어진 원소가 속한 집합을 찾아내는 방법에 관한 알고리즘입니다. Union-Find 알고리즘은 여기에 정리하였습니다. [C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘분리 집합( Disjoint Set )이란분리 집합이란 전체 집합의 원소들을 교집합이 없도록 분할한 부분 집합들을 말합니다. 예를 들면, SNS에서 A란 사람과 친구 관계를 가진..

2024. 7. 4.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1717번: 집합의 표현 ( Union-Find 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1717 풀이이 문제는 원소 a, b가 같은 집합에 포함되어 있는지, 아닌지를 출력하는 문제입니다. 얼핏 보면 굉장히 간단한 문제 아닌가 하는 생각이 들 수 있는데,완전히 복잡하지는 않지만, 그렇다고 직관적으로 접근하면 시간을 잡아먹을 수도 있는 문제입니다. 여기서는 Union-Find 알고리즘을 사용했습니다.이 알고리즘은 여기에서 볼 수 있습니다. [C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘분리 집합( Disjoint Set )이란분리 집합이란 전체 집합의 원소들을 교집합이 없도록 분할한 부분 집합들을 말합니다. 예를 들면, SNS에서 A란 사람과 친구 관계를 가진 사람..

2024. 7. 3.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1967번: 트리의 지름( diameter ) - C++ 문제 풀이

문제 설명  문제 링크: https://www.acmicpc.net/problem/1967 풀이이 문제는 주어진 트리에서 가장 긴 지름을 출력하는 문제입니다.여기서, 트리의 지름이란 트리에서 임의의 두 노드 사이의 경로의 길이를 말합니다. 우선, 가장 긴 지름을 얻을 수 있는 두 노드는 모두 리프 노드임을 알아야 합니다.리프( leaf ) 노드란 트리에서 가장 아래에 위치한 노드를 말합니다. 가장 간단한 트리를 가지고, 지름을 구하는 것부터 시작하겠습니다.그리고, 간선의 가중치는 1로 가정합니다.  위의 이미지에서, 가장 긴 지름은 2 노드에서 루트( root ) 노드를 지나, 3 노드 도달하는 경로의 길이라는 것을 알 수 있습니다. 이를 리프 노드 관점으로 다르게 표현하면,가장 긴 지름은 리프 노드에서..

2024. 6. 29.

문제 풀이/백준 (BOJ)

[백준/BOJ] 11725번: 트리의 부모 찾기 ( 깊이 우선 탐색 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/11725 풀이이 문제는 트리를 구성하는 각 노드의 부모 노드 번호를 출력하는 문제입니다. 먼저, 입력된 데이터로부터 트리를 구성하고, 루트(root)인 1번 노드부터 연결되어 있는 노드들을 탐색해서, 부모 노드를 기록했다가 출력하면 될 것입니다.주어진 데이터가 트리라고 했으므로, 분리된 노드는 고려하지 않아도 됩니다. 이 문제에선, 깊이 우선 탐색( DFS ) 방법을 사용했습니다. 깊이 우선 탐색에 관한 내용은 여기에서 볼 수 있습니다. [백준/BOJ] 24480번: 깊이 우선 탐색 2 ( DFS, Depth-First Search ) - C++ 문제 풀이문제 설명 문제 링크: https://www.acmicpc.net/p..

2024. 6. 28.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1450번: 냅색문제 ( meet in the middle 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1450 풀이이 문제는 가지고 있는 N개의 물건 중에 무게 C를 넘지 않도록 뽑는 방법의 수를 출력하는 문제입니다.이때, N의 최대 값은 30입니다. 만약, N을 30이라고 가정하면, 주어진 물건 중에서 가방에 넣는 방법의 수는 $2^{30}$입니다.왜냐하면, 물건 당, 그 물건을 가방에 넣거나, 넣지 않거나 두 가지지 방법이 있기 때문입니다. 이 가짓수 중에서, 뽑은 물건들의 무게 합이 무게 C보다 작거나 같은 개수를 구하면 되는 문제입니다. 그러나, $2^{30}$은 백만이 넘는 큰 수입니다.따라서, 이런 방식으로 풀면 당연히 시간제한을 넘을 수 없습니다. 그래서, 이 문제에선 "중간에서 만나기( meet in the m..

2024. 6. 27.

문제 풀이/백준 (BOJ)

[백준/BOJ] 3273번: 두 수의 합 ( 투 포인터, two pointers 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/3273 풀이이 문제는 주어진 수열에서 합했을 때 x가 되는 숫자 쌍의 개수를 구하는 문제입니다.여기에서는 투 포인터 알고리즘을 이용해서 풀이했습니다. 투 포인터( two pointers ) 알고리즘은 정해진 구간을 탐색할 때, 두 개의 포인터를 사용해서 탐색 범위를 좁히는 과정을 통해 문제를 해결하는 방식을 말합니다. 예를 통해서, 투 포인터가 어떤 식으로 문제를 해결하는지 알아보겠습니다. 수열 1, 2, 3, 4, 5가 주어지고, 합했을 때 7이 되는 숫자 쌍을 찾는다고 해봅시다.탐색을 수열의 시작과 끝에서부터 시작합니다.  두 포인터가 가리키는 숫자 1과 5의 합은 7보다 작습니다.좀 더 큰 숫자를 찾아야 합니다.그런데..

2024. 6. 23.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1707번: 이분 그래프 ( 깊이 우선 탐색, DFS 활용법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1707 풀이이 문제는 주어진 그래프가 이진 그래프( Bipartite Graph )인지 판단하는 문제입니다. 이진 그래프는 그래프의 모든 정점을 두 그룹으로 나눌 수 있는 그래프를 말합니다.예를 들어, 한 정점이 그룹 1에 속하면, 그와 인접한 모든 정점은 그룹 2에 속해야 합니다. 만약, 모든 정점을 두 그룹으로 나눌 수 있다면, 모든 정점을 인접한 정점과 다른 색상으로 칠할 수 있다는 얘기가 됩니다. 이와 비슷한 문제로 4색 문제가 있습니다.4색 문제는 평면을 유한 개의 부분으로 나누어 각 부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네 가지 색으로 충분하다는 정리입니다. 이 문제 풀이는 깊이 우선 ..

2024. 6. 21.