문제 풀이/백준 (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] 15649번, 15651번: N과 M (백트래킹 기법) - C++ 문제 풀이

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

2024. 5. 11.

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

문제 풀이/백준 (BOJ)

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

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

2024. 4. 30.

문제 풀이/백준 (BOJ)

[백준/BOJ] 12789번: 도키도키 간식드리미 - C++ 문제 풀이

문제 설명 문제 링크: http://www.acmicpc.net/problem/12789 풀이사람수 N명이 입력된 후, 사람들이 가지고 있는 번호표가 입력된다. 물론 입력되는 번호표는 섞여있다. 간식을 받을 차례가 아닌 번호표를 가진 사람들을 대기열에 잠시 비켜 있도록 하면서,  번호 순서대로 간식을 줄 때 N명 모두 간식을 받을 수 있는가를 판단하는 문제이다. 대기열은 한 줄로 되어있고, 대기열에 가장 나중에 합류한 사람이 먼저 간식을 받을 수 있다고 했으므로 stack 구조를 고려하는 것이 합리적이다. 이 글에서 처리한 방식은 다음의 같다. 1. 현재 줄에서 제일 앞에 있는 사람의 번호가 이번에 간식을 받을 번호면 간식을 받고 다음 사람 차례로 넘어간다.    그렇지 않은 경우 대기열을 검색한다. 2..

2024. 4. 26.

문제 풀이/백준 (BOJ)

[백준/BOJ] 24511번: queuestack - C++ 문제 풀이

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

2024. 4. 24.

문제 풀이/백준 (BOJ)

[백준/BOJ] 18258번: 큐 2 ( Queue 자료 구조 사용하기 ) - C++ 문제 풀이

문제 설명 문제 링크: http://www.acmicpc.net/problem/18258 풀이문제에서는 큐(queue)를 구현해서 문제를 풀라고 되어있지만, std::queue 클래스를 사용해서 문제를 풀었다.문자열을 읽어서 그 문자열에 따라 std:: queue 클래스의 각 기능을 사용하면 간단히 처리된다.한번 큐(queue)를 구현해 보라는 문제인 거 같다. 나머지 글도 대부분 queue 자료 구조와 std::queue 클래스 사용법에 대하여 적을 생각이다. 큐(queue)는 컨테이너의 한 종류로서 큐에 맨 먼저 입력된 데이터가 먼저 출력될 수 있는 자료 구조입니다.맨 먼저 입력된 데이터가 먼저 출력되어야 하는 FIFO (First Input First Out) 구조로서, 자료 접근에 제한된 기능을 ..

2024. 4. 23.