문제 풀이/백준 (BOJ)

[백준/BOJ] 4779번: 칸토어 집합( 재귀 함수 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/4779 풀이이 문제는 구간의 중앙 3분의 1 부분을 제거한 나머지 부분들의 길이가 모두 1이 될 때까지, 같은 방법을 반복하고, 그 결과를 출력하는 문제입니다.여기서 주목할 것은, 문제를 풀기 위해 같은 방법을 반복한다는 것입니다.이렇게 문제를 해결하는 방법을 재귀( recursion ) 방식이라고 합니다. 먼저, 위에서 말하는 칸토어 함수는 다음과 같습니다.// 칸토어 집합을 만드는 재귀 함수void Cantor( vector& vec, int s, int e){ int len = e - s; if ( len == 1) // 기저 조건 return; int len3 = len /..

2024. 11. 15.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1976번: 여행 가자( Union-Find 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1976 풀이이 문제는 도시 간의 여행 경로가 주어졌을 때, 도시 간에 도로가 있어서, 이 여행 경로를 따라 여행을 할 수 있는지 여부를 출력하는 문제입니다. 이 문제는 여러 가지 방법으로 해결할 수 있겠지만, 여기서는 Union-Find 알고리즘을 사용합니다.이러한 Union-Find는 원소가 주어졌을 때, 이 원소가 어떤 집합에 속한 지를 판단하는 데 사용되는 알고리즘으로서, 먼저 이에 대한 내용을 알 필요가 있습니다. [C++] 분리 집합( Disjoint Set )과 합집합 찾기( Union-Find ) 알고리즘분리 집합( Disjoint Set )이란분리 집합이란 전체 집합의 원소들을 교집합이 없도록 분할한 부분 집..

2024. 11. 14.

문제 풀이/백준 (BOJ)

[백준/BOJ] 11279번: 최대 힙 ( 우선순위 큐 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/11286 풀이이 문제는 힙( heap ) 구조의 자료구조에 데이터를 입력하고, 0을 입력받으면 가장 큰 원소를 출력하는 문제입니다. 이 글에선 C++ 표준라이브러리의 우선순위 큐를 이용해서 문제를 풀 생각입니다. 우선순위 큐( priority  queue )는 높은 우선순위를 가진 원소가 먼저 출력되도록 하는 자료구조입니다. 여기에선, 가장 큰 값을 가진 원소가 높은 우선순위를 가진 원소가 될 것입니다. 우선순위 큐에 대한 내용은 여기에 정리해 두었습니다. [C++] 우선 순위 큐 ( Priority Queue ) 사용법우선순위 큐 ( Priority Queue )우선순위 큐는 저장하고 있는 원소들을 원소의 우선순위 순으로..

2024. 11. 13.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1541번: 잃어버린 괄호 ( greedy 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1541 풀이이 문제는 수식이 주어졌을 때, 적절한 부분을 괄호로 묶어서, 가장 작은 수식의 값을 구하는 문제입니다. 만약, 55-50+40의 수식이 주어졌을 때, 최소 값을 구하는 방법은 한 가지 방법 밖에 없습니다.55 - ( 50 + 40 )으로 수식을 변경하여 값을 구하는 방법입니다. 따라서, 마이너스 기호를 기준으로 입력받은 수식을 분리해서, 각 부분의 값을 다 더한 후, 첫 번째 부분의 값에서 나머지 부분들의 값을 계속 빼면, 그 값이 최소 값이 될 것입니다. 예를 들어, 100 - 43 + 50 + 74 - 30 + 21의 수식이 주어지면,100 - ( 43 + 50 + 74 ) - ( 30 + 21 ) = -1..

2024. 8. 24.

문제 풀이/백준 (BOJ)

[백준/BOJ] 11438번: LCA 2 ( 최소 공통 조상 구하기 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/11438 풀이이 문제는 그래프가 주어졌을 때, 임의의 두 정점의 최소 공통 조상( lowest common ancestor )을 찾는 문제입니다.여기서, 최소 공통 조상이란, 선택된 두 정점의 조상 중에서 가장 큰 깊이( depth )를 가진 정점을 말합니다. 최소 공통 조상을 구하는 알고리즘은 여기에서 볼 수 있습니다. [C++] 최소 공통 조상( lowest common ancestor, LCA ) 구하기최소 공통 조상( lowest common ancestor )이란최소 공통 조상( LCS )은, 그래프에서 선택된 두 정점의 공통된 조상 정점 중에서, 가장 큰 깊이를 가진 정점을 말합니다.참고로, 노드의 깊이( dep..

2024. 8. 20.

문제 풀이/백준 (BOJ)

[백준/BOJ] 2193번: 이친수 ( 동적 프로그래밍 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2193 풀이이 문제는 숫자의 자릿수가 주어졌을 때, 만들 수 있는 이친수( pinary number )의 개수를 구하는 문제입니다. 적은 자릿수의 이친수로부터 더 큰 자릿수의 이친수를 만드는 과정을 생각해 보면 규칙성을 만들어 볼 수 있습니다. 먼저, 간단히 4 자릿수 이친수를 만든다고 해봅시다.그럼, 3 자릿수 이친수의 끝 부분에 0을 붙이면 이친수의 규칙을 어기지 않고도 4 자릿수 이친수를 만들 수 있습니다. 그런데, 3 자릿수 이친수의 끝 부분에 1은 붙일 수 없습니다. 이렇게 해서 만들어진 4 자릿수의 숫자는 이친수가 아닐 수도 있기 때문입니다. ( 예, 1011 ) 그럼, 1로 끝나는 이친수는 만들 수 없는 걸까요..

2024. 8. 18.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1934번: 최소공배수 ( 유클리드 호제법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/13241 풀이이 문제는 두 숫자를 입력받아 최소공배수( least common multiple )를 구하는 문제입니다. 양의 정수 a와 b의 최소공배수는 최소공배수 = a * b /  최대공약수입니다. 그런데, 이 문제에서는 a * b의 값이 $10^{16}$의 범위를 가지므로, int 타입을 사용하면, 결과 값을 담을 수 없게 됩니다.따라서, 적어도 long 보다 큰 범위를 가진 타입의 숫자를 사용해야 합니다. 여기서는 문제에서 주어진 타입인 long long int를 사용합니다.그런데, 매번 이 긴 타입을 입력하는 것은 불편한 일입니다. C++은 이럴 때를 대비하여 타입의 별명을 만들 수 있습니다.using mtype ..

2024. 8. 18.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1516번: 게임 개발 ( 위상 정렬 사용법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1516 풀이이 문제는 건물 건설에 걸리는 시간을 출력하는 문제입니다.그런데, 이 건설 시간은 한 건물을 건설하는데 사전에 필요한 건물들의 건설 시간을 모두 포함한 시간입니다. 이러한 문제를 푸는 데, 위상 정렬( topology sort ) 알고리즘이 적합합니다.위상 정렬은 어떤 과제를 해결하는데 먼저 수행해야 되는 작업을 나열하는 알고리즘입니다. 위상 정렬에 관한 내용은 여기에서 볼 수 있습니다. [C++] 위상 정렬( Topology Sort )위상 정렬( Topology Sort )이란위상 정렬이란 주어진 DAG( Directed Acyclic Graph )에서 간선의 방향에 따라 모든 정점을 나열하는 것을 말합니다...

2024. 8. 14.

문제 풀이/백준 (BOJ)

[백준/BOJ] 11505번: 구간 곱 구하기 ( 세그먼트 트리 사용법 ) - C++ 문제 풀이

문제 설명 문제 풀이: https://www.acmicpc.net/problem/11505 풀이이 문제는 주어진 숫자 배열의 값들을 변경한 후에, 변경된 값이 반영된 배열의 부분곱을 구하는 문제입니다. 이번 문제는 세그먼트 트리( segment tree )를 사용하는 전형적인 문제입니다.세그먼트 트리는 주어진 데이터에 대한 빈번한 변경에도, 원하는 연산 값을 구하는데, 일정한 수행 능력을 보여주는 자료구조입니다.세그먼트 트리의 값은 수행하고자 하는 연산에 따라 달라지는데, 이 문제에선 원하는 연산이 부분곱을 구하는 것입니다. 세그먼트 트리에 관한 내용은 여기에서 볼 수 있습니다. [C++] 세그먼트 트리( segment tree )에 관한 설명과 사용법세그먼트 트리( segment tree ) 소개세그먼..

2024. 8. 13.

문제 풀이/백준 (BOJ)

[백준/BOJ] 10868번: 최솟값 ( 세그먼트 트리 사용법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/10868 풀이이 문제는 입력된 숫자 배열에서 주어진 구간의 최소 값을 구하는 문제입니다. 이번 문제는 세그먼트 트리( segment )를 사용하는 전형적인 문제입니다.세그먼트 트리는 주어진 데이터에 대한 빈번한 변경에도, 원하는 연산 값을 구하는데, 일정한 수행 능력을 보여주는 자료구조입니다.세그먼트 트리의 값은 수행하고자 하는 연산에 따라 달라지는데, 이 문제에선 원하는 연산이 부분 최소 값을 구하는 것입니다. 세그먼트 트리에 관한 내용은 여기에서 볼 수 있습니다. [C++] 세그먼트 트리( segment tree )에 관한 설명과 사용법세그먼트 트리( segment tree ) 소개세그먼트 트리는 주어진 대량의 데이터에..

2024. 8. 13.