백준

1. 개요 안녕하세요! 오늘 문제의 유형은 트라이입니다. 트라이는 문자열의 문자를 정점으로 하는 트리 자료구조인데요. 이번 문제는 트라이 응용이 필요한 문제였습니다. 저는 트라이를 중첩 구조로 구현하여 문자가 아닌 문자열 값을 가지게 구현한 다음 recursion하게 호출하여 삽입과 출력을 구현했어요! 2. 문제 풀이 문제에 제시된 그림을 통해 개미굴이 트리임을 알 수 있습니다. 여기서 각 트리 정점은 숫자가 아닌 문자열 정보를 가지고 있어야 해요. 그렇다면 문자열로 정점을 분류할 수 있을까요? 정답은 분류할 수 없다입니다. 그림을 확인해 보면 서로 다른 계층에 같은 문자열을 가지고 있음을 알 수 있어요. 그래서 문자열로 정점을 분류할 수 없습니다.  정점을 분리하기 위해서는 다른 논리적인 방법이 필요해..

1. 개요 안녕하세요? 이번에 풀었던 문제의 유형은 다이나믹 프로그래밍입니다. 문제 지문 설명은 단순하군요. 초기값을 주고 하위 수열 원소 두 개를 더해가면서 만드는 피보나치와 비슷한 형태를 가지네요. 피보나치수열은 재귀로 간단하게 구할 수 있습니다. 하지만 시간복잡도가 지수 스케일이라 입력값이 크면 시간제한 안에 구할 수 없습니다.   이 문제도 N이 1e13까지 주어지므로 단순 재귀로는 구하기엔 어려워보입니다. 그렇다고 배열을 선언해서 메모이제이션을 해보려고 해도 배열의 크기가 1e13까지 할당을 해야 하는데 메모리 제한을 우뚝 넘어서서 어렵네요. 어떤 방법으로 메오이제이션을 해야 하는지가 이 문제의 핵심으로 보입니다. 2. 문제 풀이 i >= 1을 만족하는 정수 i에 대해서 A[i] = A[i / ..

1. 개요 안녕하세요. 오늘 문제의 유형은 Minimum Spanning Tree, MST(최소 신장 트리)입니다.  N개의 별을 선으로 직/간접적으로 연결해야 합니다. 정점을 별, 별을 잇는 선을 간선이라고 한다면 별자리는 트리 구조임을 알 수 있어요! 그런데 선을 연결하는데 비용이 드네요? 이 비용을 최소화하여 연결하고 싶다고 하였으니 가중치 무방향 연결 그래프에서 최소 신장 트리를 구해야 한다는 사실을 알 수 있습니다.  간선의 가중치 정보가 실수형입니다. 부동소수점 연산은 연산을 거듭할수록 오차범위가 커지게 되므로 연산 작업을 최소화해서 푸는 것이 좋습니다. 하지만 이번 문제는 입력부터 실수로 주어져 이를 적용하기 어려운데요. 저는 가중치를 sqrt하지 않은 제곱 형태로 저장해서 풀이했습니다. 의..

1. 개요 안녕하세요. 오늘 문제의 유형은 그리디입니다. 저는 이 문제를 naive하게 풀었다고 생각했는데 AC를 받아버렸습니다. 제가 푼 방법이 그리디하게 풀 수 있는 방법이었나봅니다. 2. 문제 풀이 방법은 단순합니다. 현재 들여쓰기 칸 수를 저장하는 배열 a와 올바른 들여쓰기 칸 수를 저장하는 배열 b가 있다고 했을 때, 0  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 vector vl;typedef vector vp..

1. 개요 안녕하세요. 오늘 문제의 유형은 해쉬 + 이분 탐색입니다. 처음엔 해쉬만 사용해 풀이했습니다. 그런데 유형을 까보니 이분 탐색도 있었습니다. 그래서 이분 탐색으로도 풀이해 봤는데요. 로직은 똑같으나 naive하게 구현하느냐 parametric search를 사용하느냐 정도의 차이입니다. 시간 소요는 이분 탐색이 400ms 정도 빠릅니다. 2. 문제 풀이 parametric search를 결정하기 위한 조건을 세워봅시다. 이분 탐색을 사용하여 count에 값을 미리 결정합니다. 그리고 해당 count를 만족하기 위한 문자열를 뽑아줍니다. 문자열 중 중복인 값이 있다면 false를 반환하고 없다면 true를 반환하게 합니다.  중복을 확인하는 것은 unordered_set을 사용합니다. count..

1. 개요 안녕하세요. 오늘 풀이한 문제의 유형은 에라토스테네스의 채 응용문제입니다. 자연수를 소인수분해하는 작업은 모두 소수를 사용하여 진행이 됩니다. 소수를 계산하는 에라토스테네스의 채를 사용한다고 하여도 이를 사용해 자연수를 srqt(k)로 소인수분해를 진행해도 시간제한을 맞추기엔 어려워 보입니다.  핵심은 에라토스테네스의 채를 소수를 구하는 것으로 사용하는 게 아닌 나누어지는 가장 작은 수를 찾는 방법으로 응용이 필요했습니다. 2. 문제 풀이 앞서 설명한 것과 같이, 에라토스테네스의 채를 사용하여 5,000,000 이하의 임의의 자연수 k가 나누어지는 가장 작은 수를 찾아야 합니다. 해당 작업을 통해 sqrt(k) 이하의 수를 순회하면서 소인수를 찾는 로직을 생략할 수 있어 최적화가 가능해지고 T..

1. 개요 안녕하세요. 오늘 풀어본 문제의 유형은 그리디입니다. 하지만 저는 브루트포스로 풀었습니다. 정확한 분석을 한 것은 아니었지만 단어의 개수와 길이, 알파벳의 수가 크지 않아 가능하다고 판단했습니다. 그런데 어째서 가능한지 분석할 필요가 있어 작성해 보겠습니다.  주어진 조건에서 최악의 경우를 상정해 보면 단어의 개수가 10개이고 길이는 모두 8, 서로 다른 알파벳은 10개라고 해봅시다. 알파벳에 0부터 9까지 숫자를 부여하는 것은 순열 계산으로 10!입니다. 그리고 단어를 수로 변환하는 과정은 10 * 8개의 연산을 통해 계산할 수 있으므로 시간복잡도는 O(10! * 10 * 8)입니다. 10! * 10 * 8은 약 2억 9천입니다. 시간제한이 넉넉하게 2초이므로 브루트포스로도 풀이할 수 있습니..

1. 개요 안녕하세요. 이번에 푼 문제의 유형은 너비우선탐색입니다. 하지만 그래프 모델링을 할 때 발상이 필요합니다. 그 이후에는 단순 너비우선탐색입니다. 저도 안일하게 그래프 모델링을 해 MLE를 받았었습니다. 2. 문제 풀이2 - 1. Naive한 그래프 모델링 그래프 모델링을 고민해봅시다. naive하게 구현하자면 각 station을 정점으로 하는 그래프를 준비합니다. 하이퍼튜브로 연결된 각 station들을 이중 for loop로 간선을 추가하면 끝입니다. 하지만 이는 MLE가 발생합니다. 튜브는 최대 1,000개이 각 튜브 내에 1,000개의 station을 모두 연결하게되면 하나의 튜브에서 간선이 1,000,000개가 생성이 되고 최종적으로 그래프의 간선의 개수는 1e9개가 됩니다. 문제의 메..