백준

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. 학생 감지하기 선생님들이 놓인..

1. 개요 안녕하세요. 이 문제의 유형은 그리디입니다. 이 문제는 유형을 구분하기에도 조금 힘들었던 문제였습니다. 이유는 발상이 어려운데요. 문제의 데이터 크기 조건을 확인하지 않으면 knapsack 문제로 해석도 가능합니다. 가능한 모든 데이터가 10억이라 DP로 풀이할 시 MLE와 TLE를 피할 수 없습니다. 2. 문제 풀이 우선 입력으로 들어오는 저울추의 무게를 오름차순으로 정렬합니다. 그 다음 만들 수 있는 숫자의 범위를 결정해야 합니다. 만들 수 있는 최소 무게는 모든 저울추를 제외한 경우인 0입니다. 따라서 처음 가능 범위는 [ 0, 1 )입니다. 이제 정렬된 저울추의 무게 리스트를 순회하면서 무게 1을 만들 수 있는지 비교해야 합니다. 1이 아닌 임의의 자연수 K에 대해서 [ 0, K ..

1. 개요 안녕하세요. 이 문제의 유형은 플로이드-와샬에 유니온파인드를 곁들인 응용문제였습니다. 구현 자체는 쉬운데 문제에 함정이 있어 주의해야 합니다. 그래프는 무방향 비연결 그래프가 주어지는데 각 컴포넌트마다 자동으로 문제에서 설명한 위원회가 됩니다. 이제 문제 풀이 로직 구현을 설명해 보겠습니다. 2. 문제 풀이2 - 1. 의사전달시간 구하기 문제에서 요구한 내용을 구현하기 위해서는 의사전달시간이 최소가 되어야 합니다. 그리고 인접행렬만 주어져있을 때에는 각 위원회에서 누가 대표가 되는지 모르기 때문에 모든 정점에서의 최단의사전달시간을 구해야 합니다. 정점의 개수가 최대 100개이므로 플로이드-와샬을 수행해도 시간복잡도에 문제는 없습니다. 따라서 플로이드-와샬을 수행하시면 됩니다. 2 - 2. 위..

1. 개요 안녕하세요. 이번 문제의 유형은 스택을 사용한 구현 문제입니다. 여러 가지 구현을 요구하는 유형에서 흔히 발생하는 맞왜틀에 걸려서 풀이하는데 오랜 시간이 걸렸습니다. 이런 문제의 유형은 풀 때에는 여러 가지의 테스트 데이터를 준비해서 단위 테스트를 수행하는 방법을 사용해봐야 할 것 같습니다. 처음 생각했던 방식이 맞았다면 불필요한 시간 소요가 되겠지만 맞왜틀을 시전 중이라면 빠르게 수정이 가능해 풀이에 용이할 것 같습니다. 2. 문제 풀이 문제 풀이는 단순합니다. 문제 설명대로 스택을 준비해서 요구한 명령어를 수행하는 로직을 구현하시면됩니다. 저는 조금 더 시간이 소요될 수 있으나 가독성과 코드 수정 용이함을 위해서 일부 명령어 수행부와 명령어 수행 가능 검증 기능을 분리해서 구현했습니다. 주..

1. 개요 안녕하세요. 이 문제의 유형은 다익스트라입니다. 다익스트라란 가중치 그래프에서 임의의 정점을 출발점으로 지정해 다른 정점까지의 최단 거리를 빠른 시간 내에 구할 수 있는 알고리즘입니다. 로직 구현 자체에는 BFS와 큰 차이점은 없습니다.  문제를 해석해보시면 간선을 순서대로 하나씩 추가하다가 정점 s와 정점 t가 간선을 통해 방문할 수 있는 상태가 되면 간선 추가를 중지합니다. 그 후 추가했던 간선들의 가중치 합을 구하려고 합니다. 여기까지만 읽었다면 다익스트라를 적용할 수 있는지는 확신이 들지 않습니다. 하지만 다음 문장에 s와 t가 연결되는 시점에서 추가된 간선의 가중치 합이 최소가 되도록 추가할 간선의 순서를 조정한다고 합니다. 즉, 저희는 입력으로 주어지는 순서대로 간선을 추가할 필요가..