문제 풀이/백준 (BOJ)

[백준/BOJ] 1725번: 히스토그램 ( 스택 stack 활용법 ) - C++ 문제풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1725 풀이이 문제는 주어진 히스토그램에 넣을 수 있는 가장 큰 직사각형의 넓이를 구하는 문제입니다. 이 문제를 푸는 아이디어는,입력되는 막대의 높이가 줄어들면, 넣을 수 있는 직사각형의 높이가 줄어들므로,줄어들기 전의 직사각형의 넓이가 가장 큰 값의 후보가 된다는 것입니다. 예를 들어, 간단한 경우를 생각해 보죠.[4, 4, 4, 1]의 히스토그램이 입력되었을 때, 가장 큰 직사각형의 넓이를 구하는 과정을 생각해 보면  4가 세 번 입력될 때까지, 직사각형의 높이는 4입니다.그런데, 아직은 계산을 할 필요가 없습니다.다음에 4보다 크거나 같은 높이의 막대가 입력되면, 최대 넓이가 더 늘어나기 때문입니다. 하지만, 다음에 ..

2024. 6. 13.

문제 풀이/백준 (BOJ)

[백준/BOJ] 2630번: 색종이 만들기 ( 분할 정복법 )- C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2630 풀이같은 색상을 가진 정사각형이 나올 때까지 4등분으로 크기를 점점 줄여가며, 같은 색상으로 이루어진 흰색과 파란색 정사각형의 개수를 세는 문제입니다. 이 문제는 분할 정복으로 문제를 푸는 방식을 보여주는 예제 같은 문제라고 할 수 있을 것 같습니다. 분할( Divide and Conquer ) 정복법은 재귀적으로 자신을 호출하면서 조건에 맞을 때까지 그 연산의 단위를 조금씩 줄어가는 방식입니다.큰 문제를 작고 풀기 쉬운 문제로 나눠 푼 후, 그 결과를 조합해 원래 문제의 답을 구하는 방식입니다.대표적인 예시로는 이진 탐색(Binary Search), 퀵 정렬(Quick Sort) 등이 있습니다.그리고 이 문제도 분..

2024. 5. 24.

문제 풀이/백준 (BOJ)

[백준/BOJ] 1629번: 곱셈 ( 분할 정복법 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/1629 풀이자연수 A를 B번 곱한 수를 구하는 문제입니다. 당연히, A, B에 큰 수가 입력됐을 때 글자 그대로 A^B ( A * A * A * A *... )의 계산을 하면 시간제한에 걸립니다. 이런 경우에 분할 정복법을 쓰게 되면 계산 시간을 상당히 줄일 수 있습니다. 분할 정복법은 재귀적으로 자신을 호출하면서 조건에 맞을 때까지 그 연산의 단위를 조금씩 줄어가는 방식입니다. 큰 문제를 작고 풀기 쉬운 문제로 나눠 푼 후, 그 결과를 조합해 원래 문제의 답을 구하는 방식이라고 할 수도 있습니다. 예를 들어, 2^10 = 2^5 * 2^5로 분할할 수 있고, 이제 2^5의 계산만 하면 2^10의 값을 알 수 있습니다.분할..

2024. 5. 24.

문제 풀이/백준 (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] 14889번: 스타트와 링크 (백트래킹 기법) - C++ 문제풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/14889 풀이한 그룹의 사람들 중에서 스타크와 링크 팀으로 나누어 각 팀의 능력치 차이의 최소 값을 출력하는 문제입니다. 짝수인 N 사람들 중에서 M=N/2 사람을 뽑아 팀을 만드는 것부터 해야겠네요.편의상 팀명을 A팀이라고 하겠습니다.주의할 점은 1번과 3번을 뽑는 것과 3번과 1번을 뽑는 것은 같은 것으로 봐야 한다는 거죠.이 경우의 수를 제거하기 위해서, 다음 사람의 번호는 이전 사람의 번호보다 크도록 뽑았습니다.void Pickup( int num, int start){ if ( num == M){ return; // 팀에 필요한 사람을 뽑았음 } int to = N - M + num; ..

2024. 5. 15.

문제 풀이/백준 (BOJ)

[백준/BOJ] 9663번: N-Queen (백트래킹 기법) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/9663  풀이체스에서 퀸은 거리와 상관없이 직선, 대각선에 있는 적을 공격할 수 있는 말입니다.이런 N개의 퀸을 N x N 크기의 체스판에 서로 공격할 수 없도록 배치할 수 있는 방법의 수를 찾는 문제입니다.  위의 이미지는 4x4 체스판 위에 4개의 퀸들이 서로 공격할 수 없도록 배치된 예를 보여주고 있습니다.이 문제는 백트래킹 기법의 전형적인 문제입니다. 백트리킹 기법이란 트리구조 문제의 정답을 찾는 과정에서, 더 이상 진행할 수 없는 노드에 도달하게 되면 이전 노드로 되돌아가 다른 방향으로 정답을 탐색하는 방법을 말합니다.   위의 이미지를 대상으로 탐색 과정을 설명하면,1번 노드부터 시작해서 2번 노드에 도달하여 정..

2024. 5. 11.

문제 풀이/백준 (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.