복습 정리 노트

백준 BOJ 2573번 : 빙산 Solved.ac 난이도 : Gold IV 알고리즘 분류 : DFS 주어진 각 좌표에 빙산들의 높이가 주어지고, 빙산은 인접한 4개의 칸 중에서 물(즉, 높이가 0)인 칸들의 수만큼 단위 시간 1마다 감소한다고 할 때, 빙산이 두 덩어리로 분리되는데 걸리는 시간을 구하는 문제입니다. 우선은 빙산이 두 덩어리로 분리되는지 확인할 때 DFS가 필요합니다. 매 시간 턴마다 DFS를 수행하여 빙산이 분리되어 있는지 확인해줍니다. 그 다음 빙산을 녹일 때 앞 칸부터 빙산의 높이를 감소시켜버리면, 예를 들어 빙산의 높이가 0이 되어버리는 경우 다음 빙산의 높이 변화를 계산할 때 필요한 높이보다 1이 더 감소되어 버리게 됩니다. (동시에 녹아야 하는데 앞 칸을 먼저 계산해서 뒷 칸이 ..

이 포스트에서는 백준 Online Judge(BOJ)의 문제들 중에서도 "타일 채우기" 문제들을 풀어보도록 하겠습니다. 타일 채우기 문제란 주어지는 크기의 칸을 정해진 종류의 타일들로 채우는 경우의 수를 구하는 문제입니다. 일반적으로는 DP를 활용하여 해결을 하나, 어려운 문제의 경우에는 다른 전략을 같이 활용하여 문제를 해결할 수 있습니다. 백준 BOJ 2133번 : 타일 채우기 Solved.ac 난이도 : Gold V 알고리즘 분류 : DP 3×N 크기의 칸을 2×1, 1×2 타일들로 채우는 서로 다른 경우의 수를 구하는 문제입니다. 이 때 N ≤ 30입니다. 물론 채운 배열을 돌리거나 뒤집어서 같다고 하여 같은 경우의 수로 치지는 않습니다. 그렇기 때문에 DP를 활용하여 점화식으로 문제를 풀어주면 ..

백준 BOJ 1717번 : 집합의 표현 Solved.ac 난이도 : Gold IV 알고리즘 분류 : 그래프 0 ~ N으로 이루어진 각각의 집합과 M개의 쿼리가 주어질 때, 이 쿼리들을 적절히 수행하는 프로그램을 작성하는 문제입니다. 0 a b 꼴의 쿼리에 대해서는 a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합쳐야 합니다. 1 a b 꼴의 쿼리에 대해서는 a와 b가 같은 집합의 포함되어 있는지를 확인하여 같은 집합이라면 YES, 아니라면 NO를 출력하면 됩니다. 구현 자체는 큰 어려움이 없을 수 있지만 원소는 최대 100만, 쿼리는 최대 10만개가 주어질 수 있으므로 시간 안에 풀이 가능한 효율적인 알고리즘을 구현해야 합니다. 따라서 다음과 같이 구현합니다. 우선 parent 배열을 선언하여 각..

백준 BOJ 6588번 : 골드바흐의 추측 Solved.ac 난이도 : Silver I 알고리즘 분류 : 에라토스테네스의 체 1,000,000 이하의 짝수가 주어질 때, 합이 그 짝수와 같은 두 소수를 구하거나, 또는 그런 소수 쌍이 존재하지 않음을 구하는 문제입니다. 하나의 입력에 테스트케이스가 최대 10만개까지 주어질 수 있으므로, 소수 판별을 미리 해놓고 결과값만 가져오는 방식으로 해결해야 시간 초과를 받지 않고 통과할 수 있습니다. 따라서 에라토스테네스의 체를 활용하여 문제를 풀어주어야 합니다. #include #define MAX 1000001 using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), co..

백준 BOJ 2225번 : 합분해 Solved.ac 난이도 : Gold V 알고리즘 분류 : DP, 조합론 0~N까지의 수 K개를 조합하여 N을 만들 수 있는 경우의 수를 구하는 문제입니다. 이 때 중요한 것은, 수의 순서가 바뀌면 다른 조합으로 고려하며 조합에 0이 들어갈 수 있다는 것입니다. 즉 수 2개로 1을 조합하는 경우의 수는 (0, 1)과 (1, 0)으로 총 2가지입니다. DP로 풀어야 함은 쉽게 파악이 가능한데, 수의 중복 허용과 순서 고려 때문에 경우의 수를 구하기가 쉽지 않습니다. 따라서 상황을 다음과 같이 전환시켜 생각하면 좋습니다. 0 이상의 정수 K개를 조합하여 N을 만들기 → N개의 공을 K-1개의 막대로 경계지어 K개의 묶음으로 나누기 예시를 들면 다음과 같습니다. 위는 4개의 ..

백준 BOJ 2146번 : 다리 만들기 Solved.ac 난이도 : Gold III 알고리즘 분류 : DFS, BFS 위의 그림과 같이 몇 개의 섬으로 이루어진 지도가 주어지면, 섬들 중 두 개를 잇는 가장 짧은 다리(그림에서 빨간색 칸에 해당)의 길이를 구하는 문제입니다. 우선 다리의 길이를 구하는 과정은 BFS로 구현해야함을 떠올릴 수 있습니다. 섬에 해당하는 칸 중에서, 이 칸과 인접한 바다에서부터 BFS를 시작하여 다른 섬에 해당하는 칸이 나올 때까지 반복하면 됩니다. 그런데 생각해보면, 같은 섬으로 돌아오는 것은 문제에서 정의한 '다리'에 해당하지 않으므로, 같은 섬을 구별할 수 있는 장치가 필요합니다. 따라서 탐색을 하기 전에 미리 같은 섬끼리 같은 숫자로 묶어서 표시를 해두어야 합니다. 그렇..

BOJ 11057 오르막 수 Solved.ac 난이도 : Silver I 알고리즘 분류 : DP 수의 모든 자리에서 뒷자리가 앞자리보다 같거나 큰 수를 오르막 수라고 할 때, 길이 N인 오르막 수의 개수를 출력하는 문제입니다. 수가 0부터 시작할 수 있다는 점을 반드시 주의해야 합니다. (보통 자연수는 leading-zero를 제거하고 읽지만, 여기에서는 없애지 않음) 각 수들의 특성을 생각해보면, 어떤 자릿수에서 수가 9에 도달하면 더 이상 증가할 수가 없고 그 뒤로는 9만 와야합니다. 따라서 단순 dp[i]와 같은 1차원 배열을 이용한 dp 계산보다는, 다음과 같이 dp[i][j] : 길이가 i이고 가장 마지막 자리가 j로 끝나는 오르막 수의 갯수 로 정의하여 점화식을 쉽게 세울 수 있도록 만들어주면..

백준 BOJ 6603번 : 로또 Solved.ac 난이도 : Silver II 알고리즘 분류 : 백트래킹 N개의 로또로 뽑힐 수 있는 후보 번호들이 주어지고, 그들 중 6개의 로또가 뽑힌다고 할 때 나올 수 있는 로또 조합들을 오름차순으로 출력하는 문제입니다. 재귀함수를 이용한 백트래킹을 구현하는 대표적인 문제입니다. 다음과 같이 idx, cnt 두 개의 변수를 가지는 재귀함수를 이용하여 DFS를 구현해주면 됩니다. idx는 현재 탐색 중인 인덱스를 의미하고, cnt는 현재까지 뽑은 번호의 개수를 의미합니다. #include using namespace std; int N; vector arr, lotto(6); void DFS(int idx, int cnt) { if(cnt == 6) { for(int..

백준 BOJ 1700번 : 멀티탭 스케줄링 난이도 : Gold I 카테고리 : 그리디 멀티탭 구멍의 수와 전자제품의 총 사용횟수가 주어지며, 사용되는 전자제품의 순서가 주어질 때 멀티탭에서 플러그를 빼는 최소 횟수를 구하는 문제입니다. 다음의 우선 순위에 따라 처리해주면 됩니다. (1) 이번에 사용할 전자제품이 이미 꽂혀있는 경우 : 이 경우는 아무런 변화를 주지 않고 그냥 넘어가면 됩니다. (2) 콘센트가 한 칸이라도 비어있는 경우 : 비어있는 구멍의 번호를 찾아서, 해당 번호에 현재 사용할 전자제품의 번호를 저장해주면 됩니다. (3) (1), (2)가 모두 아닌 경우 현재 콘센트에 연결된 전자제품들 중에서 가장 마지막에 사용될 전자제품의 플러그를 제거해주면 됩니다. 앞으로 남은 order들 중에서 아..

백준 BOJ 1744번 : 수 묶기 N개의 수가 주어졌을 때 두 개의 수를 선택하여 곱으로 만들거나, 아니면 그냥 더해서 그 계산식의 결과의 최댓값을 구하는 문제입니다. (이 때 선택하는 두 수는 순서에 관계없이 선택할 수 있습니다.) 간단히만 생각하면 큰 양수끼리 곱하고, 절댓값이 큰 두 음수끼리 곱해서 큰 양수를 만드는 정도의 그리디적인 풀이를 떠올릴 수 있습니다. 그러나 몇 가지 예외를 생각해야 하는데 다음과 같습니다. (1) 음수가 홀수개인 경우 : 0이 존재한다면 0과 곱해서 0으로 만들 수 있고, 그렇지 않은 경우 그냥 합에 더해주어야 합니다. (2) 양수가 홀수개인 경우 : 그냥 더해주면 됩니다. (3) 1이 존재하는 경우 : x > 0인 x에 대해 x * 1보다 x + 1이 결과값이 더 크..