백준

1. 개요 안녕하세요. 오늘 문제의 유형은 재귀입니다. 아주 유명한 웰노운 알고리즘인 하노이타워를 다루는 문제입니다. 그런데 문제가 있습니다. 입력으로 주어지는 원판의 개수가 최대 100개까지 주어지는데요. 문제는 하노이타워를 첫 번째 장대에서 다른 장대로 이동시키는데 필요한 최소 이동 횟수를 출력하도록 되어있습니다. 하노이타워의 시간복잡도는 원판의 개수를 n이라고 했을 때, O(2^n - 1)입니다. 즉 pow(2, 100) - 1이라는 매우 큰 수를 출력해야합니다. 이는 8 byte 변수로도 담을 수 없는 큰 수라 C++로 풀이를 시도하면 큰 수 구현을 직접해야하므로 번거롭습니다. 2. 문제 풀이 저는 큰 수를 계산하고 출력하기 위해 C++ 대신 자바를 사용하여 풀이했습니다. 자바에서 제공하는 Big..

1. 개요 안녕하세요. 이 문제의 유형은 너비우선탐색입니다. N을 버튼 A, B를 눌러 T횟수 안에 G를 만들면 되는 문제입니다. 2. 문제 풀이 우선 버튼 A, B에 해당하는 함수를 만들었습니다. 거리테이블을 다음과 같은 정의로 선언하시면 됩니다. d[cur]: N에서 cur로 만들기 위해서 버튼을 누른 최소 횟수 이제 너비우선탐색을 사용해서 N부터 거리배열을 채우시면 됩니다. 3. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef..

1. 개요 안녕하세요. 이 문제의 유형은 브루트포스입니다. 저는 다이나믹 프로그래밍을 사용해서 풀었습니다. 그러나 윗면과 아랫면이 여러 개 맞는 경우는 없고 모두 결정되어있기 때문에 브루트포스로 풀이해도 상관없을 것 같네요. 2. 문제 풀이 dp 테이블은 다음과 같이 구성했습니다.d[i][j]: i 번째 주사위의 j 번째 면이 윗면일 때 1...i까지 쌓은 주사위 탑의 옆 면의 최댓값 그 다음은 j 번째와 j의 반대편 면을 제외한 옆면의 최댓값을 찾아서 더해주시면 끝입니다. 3. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef ..

1. 개요 안녕하세요. 이 문제의 유형은 union-find입니다. 문제를 읽어보면 비연결 그래프가 주어지는데 어째서 union-find가 유형인지 궁금하신 분들도 있을 겁니다. 문제를 요약하자면 다음과 같습니다. 무방향 비연결 그래프가 주어진 다음, 두 정점이 그래프 내에서 같은 컴포넌트에 위치해 있는지 판단해 보라는 문제입니다. 보통 이런식으로 주어지는 문제는 그래프에서 bfs/dfs를 통해 flood fill 기법을 진행하여 컴포넌트를 분리해 풀이하는 것이 정석인데 이 문제의 경우 입력 크기 제한이 매우 큽니다. 정점은 1,000,000개이고 간선은 100,000개입니다. bfs/dfs를 돌리면 최악의 경우 TLE를 받을 수 있습니다. 정점의 개수를 N, 간선의 개수를 M이라고 한다면 시간복..

1. 개요 안녕하세요! 이 문제의 유형은 기하학 + 이분탐색입니다. 문제에서 주어진 닮음비를 바탕으로 하나의 식을 찾은 다음, 높이는 피타고라스로 구해야됩니다. 2. 문제 풀이2 - 1. 닮음비로 수식 찾기이렇게 변수를 결정하게되면 삼각형의 닮음비를 이용해 수식을 구해볼 수 있습니다. c : h1 = a1 : (a1 + a2)c : h2 = a2 : (a1 + a2) 위와 같은 닮은비를 이용해 수식을 계산하면 다음 아래와 같이 값을 정리할 수 있습니다.이와 같은 방법으로 a2도 구할 수 있습니다. a1 + a2를 k라고 해봅시다. k는 우리가 구하고자하는 너비가 됩니다. 따라서 두 수식을 더해봅시다.우변의 분자를 (a1+ a2)로 묶어서 정리해봅시다.이 다음 좌변, 우변에 공통으로 들어간 (a1 + a..

1. 개요 안녕하세요. 이 문제의 유형은 비트마스킹 + 그리디입니다. 저는 그리디만을 사용해서 풀이했습니다. 납득이 되는 풀이는 사실 비트마스킹을 사용하는 방법인데요. 저는 빙빙 돌아서 그리디만 사용했습니다. 2. 문제풀이 N개의 물병과 한 번에 들 수 있는 물병의 개수 K가 주어집니다. 물병을 합치는 로직은 결국 이진수의 원리와 같습니다. 물병 안에 차있는 물은 항상 2의 거듭제곱만큼만 채울 수 있죠. 저는 K - 1번의 루프를 통해 N보다 작거나 같은 2의 거듭제곱 중 가장 큰 수를 골라 N에서 빼주었습니다. 이는 K - 1개의 물통에 채울 물을 결정하는 로직입니다. 남은 물의 양 X가 2의 거듭제곱이거나 0이면 상점에서 물을 구매할 필요가 없고, 2의 거듭제곱이 아니라면 남은 물의 양보다 큰 2..

1. 개요 안녕하세요. 이 문제의 유형은 너비 우선 탐색 + 경로 추적입니다. 대부분은 2차원 배열이나 그래프 자료구조를 가지고 너비 우선 탐색을 수행하지만 이 문제의 경우 1차원 배열에서 너비 우선 탐색을 돌려야합니다. 사실 3차원 배열에서 너비 우선 탐색을 돌리는 것과 마찬가지로 이동 배열 하나를 두고 수행하시면 쉽게 풀이할 수 있습니다. 2. 문제 풀이2 - 1. 너비 우선 탐색 저는 이전에 숨바꼭질 시리즈를 풀어본 적이 있는데 그 때마다 순간이동에 대한 처리를 어려워했습니다. 물론 구현이 어렵지는 않지만 깔끔하게 작성할 수 있는 방법을 찾다가 포기했었죠. 이번엔 C++의 함수 포인터 배열을 사용하여 구현해보았습니다. 각 이동마다 함수를 선언해야한다는 불편함이 있지만 이동 방법이 많지 않아 괜찮아..

1. 개요 안녕하세요. 이 문제의 유형은 브루트포스, 백트래킹입니다. 모든 경우의 수를 도입해 보고 정답을 구할 수 있는지 확인해 보시면 됩니다. 이 문제에서 경우의 수는 N * N 크기의 복도 빈칸 세 곳을 결정하는 개수를 의미하겠죠. N은 6 이하까지 가능하니깐 최악의 경우는 36C3이 됩니다. 또 세 곳만 결정하면 되니깐 삼중 for loop로 풀이하셔도 무방합니다. 하지만 벽을 세울 곳이 5가지나 그 이상이라면 백트래킹이 더 간편하겠죠. 2. 문제 풀이2 - 1. 벽 위치 결정하기 위 설명과 같이 삼중 for loop나 백트래킹을 사용해서 빈 칸 세 곳을 벽으로 결정하시면 됩니다. 최악의 경우 시간복잡도는 O(36C3) = O(28,560)가 됩니다. 2 - 2. 학생 감지하기 선생님들이 놓인..