문제 풀이/백준 (BOJ)

[백준/BOJ] 4013번: ATM ( SCC, 위상 정렬 응용 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/4013 풀이이 문제는 출발 지점으로부터 방문할 수 있는 레스토랑까지 가는 동안 구할 수 있는 금액의 최대 값을 출력하는 문제입니다. 이 문제를 풀기 어렵게 만드는 것은, 문제를 그래프로 변경 시, 그래프에 순환 경로가 존재한다는 것입니다.그래서, 우선 순환 경로를 제거합니다.그 방법은 강한 결합 요소( SCC )를 구해서, 그 요소의 정점들을 하나의 정점으로 변경하는 것입니다.그렇게 되면, 원래의 그래프가 순환 경로가 없는 방향 그래프( DAG, Directed Acyclic Graph )가 됩니다.  이 과정을 코드로 작성하면 다음과 같습니다. 여기선, SCC를 구하기 위해 타잔( Tarjan ) 알고리즘을 사용하였습니다..

2024. 7. 17.

문제 풀이/백준 (BOJ)

[백준/BOJ] 11660번: 구간 합 구하기 5 ( 동적 계획법 ) - C++ 문제풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/11660 풀이이 문제는 이차원 배열의 부분 구간 합을 구하는 문제입니다. 짐작한 바와 같이, 단순히 (x1, y1) ~ (x2, y2) 구간의 값들을 합해서 답을 제시하면 시간제한에 걸립니다.그래서 구하려고 하는 부분 구간의 합을, 계산하기 쉽고 빠른 전체 구간의 합에서 더 작은 구간의 합을 빼는 방식으로 문제를 풀려고 합니다. 전체 구간의 합은 더 작은 구간의 합으로 만들 수 있고, 그 작은 구간의 합을 저장해 뒀다면 빠르게 합을 구할 수 있습니다.이렇듯, 동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후, 이 계산의 결과를 사용하여 전체의 문제를 빠르게 푸는 방법입니다. S(x, y)를 배열 처음부터 (..

2024. 5. 19.

문제 풀이/백준 (BOJ)

[백준/BOJ] 11659번: 구간 합 구하기 4 ( 동적 계획법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/11659  풀이N개의 숫자로 이루어진 수열에서 부분 구간의 합을 구하는 문제입니다. 언뜻 보면, 언어의 사용법을 묻는 듯한 문제처럼 보입니다.for( int i = a; i 그러나 이런 식으로 문제를 풀면, 제시한 시간이 아주 짧기 때문에 시간제한에 걸립니다. 이 문제는 발상의 전환을 한다면 쉽게 해결할 수 있습니다.  만약 7개의 숫자가 제시되었을 때, 5번째부터 7번째까지 숫자의 합을 구하는 경우를 생각해 봅시다.그럼, 위의 그림처럼 녹색 부분의 숫자의 합을 구하는 방법이 있지만, 전체의 합에서 흰색 부분 숫자의 합을 빼는 방법도 있습니다. 다른 말로 하면, 7번째까지 숫자의 합에서 4번째까지 숫자의 합을 뺀 값을 구하..

2024. 5. 17.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1463번: 1로 만들기 (동적 계획법) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1463 풀이정수 N을 세 가지 연산을 반복 수행하여, 1로 만들기 위해서 필요한 최소한의 연산 수를 계산하는 문제이다.N이 3으로 나누어 떨어지면, 3으로 나눈다.N이 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.어디서부터 시작해야 할지 막막하다.용어를 하나 정의해서 실마리를 잡아보자. C(N)이 위의 세 가지 연산을 통해, 정수 N을 1로 만들기 위한 최소한의 연산 수라고 하자.그럼,C(1) = 0 ( 정수 1을 1로 만드는 데 필요한 연산은 없다 )C(2) = 1C(3) = 1 이 된다. 그리고, 다음 세 가지 C(N) 중 최소 값이 정답이 된다.왜냐하면 처음 수행할 연산을 뺀, 최소 연산 수에 1을 더했을 뿐이므로 ..

2024. 5. 9.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1904번: 01 타일 (동적 계획법) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1904 풀이숫자 N이 주어졌을 때,  N 자릿수의 2진법 숫자를 만들 수 있는 개수를 알아내는 문제이다. 문자를 읽어보면, 0000을 0으로 생각하는 것이 아니라 네 자리 숫자로 계산해야 된다.이렇게 되면 1과 0으로 만들 수 있는 숫자의 수는 2ⁿ이다. 이전의 만들어진 숫자에 1 또는 0을 붙이면 되기 때문이다.이를 식으로 쓰면 F(N) = F(N-1) * 2 = F(N-1) + F(N-1)이 된다.여기서 F(N)은 타일을 가지고 만들 수 있는 N 자릿수의 숫자의 개수이다. 그런데, 이 문제에서는 0 대신 00 카드를 사용해야 한다.00 카드를 써서 N 자릿수 숫자를 만들려면 N-2 자릿수 숫자에 00 카드를 붙여야 된다..

2024. 5. 6.

문제 풀이/백준 (BOJ)

[백준/BOJ] 12865번: 평범한 배낭 (배낭 문제, 동적 계획법) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/12865 풀이N개의 물품 중에서 K 무게를 넘지 않도록 물품들을 배낭에 담았을 때, 담긴 물품들의 최대 가치값의 합은 얼마인가를 물어보는 문제이다. 배낭 문제라고 동적 계획법을 사용하는 유명한 문제이다.동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후, 이 계산한 결과를 사용하여 전체의 문제를 빠르게 푸는 방법이다.이 방법은 부분 문제를 어떻게 규정해야 하는가가 가장 어려운 부분이라고 할 수 있다. 여기서는 부분 문제를 "N-1개의 물품 중에서 K 무게를 넘지 않도록 담았을 때, 최대 가치값의 합은 얼마인가?"로 잡았다.일단, 물품의 수를 계속 줄여가다 1개까지 줄어들면 계산은 아주 간단해진다.그리고 N-1..

2024. 5. 3.

문제 풀이/백준 (BOJ)

[백준/BOJ] 9184번: 신나는 함수 실행 ( 동적 계획법 ) - C++ 문제 풀이

문제 설명 문제 링크: http://www.acmicpc.net/problem/9184  풀이문제 설명에서 말했듯이, 재귀 함수를 사용하면 구현은 쉬우나 결과를 출력하기까지 너무 오래 걸리는 단점이 있습니다.이유를 자세히 들여다보면 같은 결과를 구하는 연산을 반복해서 수행하느라 대부분의 시간을 낭비하고 있다는 점을 알 수 있습니다. 그래서 이 문제는 동적 계획법을 사용하여 푸는 것이 좋겠습니다. 동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후 결과를 저장합니다. 그리고 작은 부분의 문제를 다시 푸는 대신 저장된 결과 값을 사용하여 전체의 문제를 빠르게 푸는 방법입니다. 재귀 함수를 사용하는 방식과 동적 계획법은 더 작은 부분 문제를 해결해서 큰 문제를 해결한다는 점에서 유사한 면이 있습..

2024. 4. 30.