백준(BOJ)

[백준/C++] 11660번: 구간 합 구하기 5 ( 동적 계획법 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/11660 풀이이 문제는 이차원 배열의 부분 구간 합을 구하는 문제입니다. 그런데, 짐작한 바와 같이, 단순히 (x1, y1) ~ (x2, y2) 구간의 값들을 합해서 답을 제시하면 시간제한에 걸립니다. 그래서, 구하려고 하는 부분 구간의 합을, 전체 구간의 합에서, 더 작은 구간의 합을 빼는 방식으로 문제를 풀려고 합니다. 이 전체 구간의 합은 더 작은 구간의 합으로 만들 수 있고, 그 작은 구간의 합을 저장해 뒀다면 빠르게 합을 구할 수 있습니다.예를 들어, 숫자 6개의 합을 sum [6] 변수에 저장해 두었다면, 숫자 7개의 합은 sum [6]에 7번째 숫자를 더하는 것으로 간단하게 구할 수 있는 것입니다.이렇듯,..

2025. 4. 22.
백준(BOJ)

[백준/C++] 11659번: 구간 합 구하기 4 ( 동적 계획법 )

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

2025. 4. 22.
백준(BOJ)

[백준/C++] 14889번: 스타트와 링크 ( 백트래킹 기법 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/14889 풀이한 그룹의 사람들 중에서 스타트와 링크 팀으로 나누어 각 팀의 시너지( synergy ) 차이의 최소 값을 출력하는 문제입니다. 먼저, 짝수인 N 사람들 중에서 M=N/2 사람을 뽑아, 한 팀을 만드는 것부터 해야겠네요. 편의상, 이 팀명을 A팀이라고 하겠습니다.( 그러면, 나머지 사람들은 자연스럽게 다른 팀이 됩니다. ) 다음은 A팀 사람을 뽑는 함수로, 사람을 뽑을 때 중첩되지 않도록, 사람들의 번호를 오름차순으로 뽑습니다.여기서, num은 현재까지 뽑은 사람의 수를 말하고, start는 다음에 뽑을 수 있는 사람의 시작 번호입니다.( 예를 들어, 이전에 2번을 뽑았다면, start는 3번 이상의 번호..

2025. 4. 19.
백준(BOJ)

[백준/C++] 15649번, 15651번: N과 M ( 백트래킹 기법 )

문제 설명 ● 문제 링크: https://www.acmicpc.net/problem/15649 풀이이 문제는 1부터 N까지의 수를 가지고 M 길이의 수열을 만들어 출력하는 문제입니다. 그런데, 같은 수를 사용해서 수열을 만들 수 없습니다. 그리고, 15651번 문제는 위 문제와 같은 데, 차이점은 같은 수를 사용해서 수열을 만들 수 있다는 점이 다를 뿐입니다. 그래서, 우선 이 문제를 푼 후, 이를 확장해서 15651번 문제를 해결하겠습니다. 이 문제는 커다란 자루에 N개의 공을 넣고, 한 개씩 뽑아 나열하는 것과 같습니다. 그럼 어떻게 뽑아야 모든 경우의 수열을 만들 수 있을까요? 예를 들어, N = 8, M = 2라고 해보죠. 1. 첫 번째 공을 뽑습니다. 공에 있는 숫자를 기록하고, 자루에..

2025. 4. 19.
백준(BOJ)

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

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

2025. 4. 19.
백준(BOJ)

[백준/C++] 1463번: 1로 만들기 ( 동적 계획법 )

문제 설명 ● 문제 링크: 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) = 1 ( 2를 2로 나누면 1이 되므로 )C(3) = 1 이 됩니다. 그리고, 아래의..

2025. 4. 18.
백준(BOJ)

[백준/C++] 1904번: 01 타일( 동적 계획법 )

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

2025. 4. 17.
백준(BOJ)

[백준/C++] 9184번: 신나는 함수 실행

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

2025. 4. 17.
백준(BOJ)

[백준/C++] 12789번: 도키도키 간식드리미

문제 설명 ● 문제 링크: http://www.acmicpc.net/problem/12789 풀이사람수 N명이 입력된 후, 사람들이 가지고 있는 번호표가 입력된다. 물론 입력되는 번호표는 섞여있다. 이럴 경우, 간식을 받을 차례가 아닌 번호표를 가진 사람들을 대기열에 잠시 비켜 있도록 하면서, 번호 순서대로 간식을 줄 때 N명 모두 간식을 받을 수 있는가를 판단하는 문제입니다. 이 문제 설명에서, 대기열은 한 줄로 되어있고, 대기열에 가장 나중에 합류한 사람이 먼저 간식을 받을 수 있다고 했으므로 stack 구조를 고려하는 것이 합리적일 것입니다. [백준/C++] 28278번: 스택 2 ( stack 자료구조 사용하기 )문제 설명 ● 문제 링크: http://www.acmicpc.net/problem..

2025. 4. 17.
백준(BOJ)

[백준/C++] 24511번: queuestack

문제 설명 ● 문제 링크: http://www.acmicpc.net/problem/24511 설명입력된 숫자들을 받아 queue와 stack 구조 체인을 만든 후에, 입력된 숫자를 이 체인에 통과시켰을 때의 결과 값을 출력하는 문제입니다. 예를 들어, 세 줄에 걸쳐 다음과 같은 숫자들이 입력되었다고 생각해 봅시다. 구조 체인의 크기: 6 queue인지 stack인지 구별하는 플래그: 0, 1, 1, 0, 1, 0 각각의 구조 안에 들어있는 요소 값: 32, 22, 7, 103, 3, 29 그럼 위와 같은 queue - stack 체인을 도식화할 수 있을 것입니다. 그다음 테스트 할 숫자들을 M개 받아들여 체인을 통과시켰을 때의 결과 값들을 출력하면 됩니다. 그런데, 스택에 데이터를 입력하고 원소를 ..

2025. 4. 17.