Tech Diary Tech Diary

[백준(BOJ)] 퍼거슨과 사과(2942) C++ 문제 : BOJ_2942번 퍼거슨과 사과 문제 설명 수학, 유클리드 호제법 두 수인 R,G가 주어지면, 두 수를 모두 나눌 수 있는 수와 그 수로 R,G가 나누어진 값을 출력하는 문제입니다. Solution 결국 최대공약수를 구하고 그 최대 공약수의 약수를 구해야하는 문제임으로 유클리드 호제법을 이용해 최대공약수를 구하고, R,G가 최대 10억이기 때문에 단순한 반복문으론 시간초과 임으로 루트 N번까지만 보면되는 약수의 성질을 이용하여 루트 N번만에 구할 수 있습니다. Description 루트 N번만에 구하기 위해, (최대공약수/주어진 약수)를 최대공약수로 다시 나눠서 출력해야합니다. (이 때 주어진 약수 == (최대공약수/주어진 약수)인 경우 주의!)..

[백준(BOJ)] ACM Craft(2252) C++ 문제 : BOJ_2252번 줄 세우기 문제 설명 위상정렬, bfs 위상정렬을 이용해서 순서를 출력하는 기본적인 문제입니다. N 명의 학생 중 서로 줄을 세운 M 개의 경우의 순서만 고려하고 줄을 세운 관계가 아니라면 아무 순서나 상관없이 출력할 수 있습니다. Solution 순서대로 배열하기 위해 indegree를 이용한 위상정렬을 해줘야 하므로, indegree라는 배열을 만들어 순서를 벡터에 연결해줄 때마다 배열의 수를 올려주며, 큐에 집어넣을 때는 들어오는 모든 간선을 탐색한 경우에만 push 해주는 방식으로 소스를 짜야 합니다. #include #include #include using namespace std; int stu, rel, ind..

[백준(BOJ)] ACM Craft(1005) C++ 문제 : BOJ_1005번 이모티콘 문제 설명 위상정렬, dp, bfs 각 건물마다 그 건물을 짓기 위해서 먼저 지어져야 하는 건물들이 존재하고, 먼저 지어야 하는 건물이 없는 건물부터 시작하여 지정된 거물을 지을 때까지 걸리는 최소 시간을 작성하는 문제입니다. 건물에 대한 앞뒤 관계가 있고, 사이클이 아니기 때문에 indegree를 이용한 위상정렬 문제입니다. 그리고 먼저 지어야 하는 모든 건물이 지어져야 다음 건물이 지어지므로, dp를 활용하여 건물이 지어질 수 있는 최소 시간을 구할 수 있습니다. Solution 한 건물이 지어지는 시간을 모두 입력받고(wait[]), 최종적으로 그 건물이 지어질 수 있는 최소 시간에 대한 배열을 만든 뒤(res..

[백준(BOJ)] 이모티콘(14226) C++ 문제 : BOJ_14226번 이모티콘 문제 설명 bfs 처음에 한 개의 이모티콘이 있고 이모티콘을 클립보드에 저장할 때 count +1 이모티콘을 붙여넣기 할 때 count +1(클립보드가 비어있으면 안 됩니다.) 현재 이모티콘의 수를 -1 할 때 count +1 일 때 주어지는 수의 이모티콘 개수가 될 때까지 최소 count를 구하는 문제입니다. Solution 최솟값을 구해야 되기 때문에 bfs를 써야 하는데 좀 까다로운 문제입니다. 매 회 수 마다 이모티콘 수 -1, 클립보드 복사, 클립보드 붙여넣기의 세 가지 경우의 수로 queue에 push 해야 되지만, 현재 이모티콘의 수와 클립보드에 저장된 이모티콘의 수에 따라 경우의 수가 모두 달라지기 때문에 ..

[백준(BOJ)] 새끼치기(17291) C++ 문제 : BOJ_17291번 새끼치기 문제 설명 위상정렬, DP(다이나믹 프로그래밍) 1년에 한 마리였던 벌레가 매년 분열하고 1)홀수 연도에 분열했던 벌레는 3번 분열 시 사망 2)짝수 연도에 분열했던 벌레는 4번 분열시 사망 임으로, 해당 년도에 살아있는 벌레들이 언제 분열했는지를 저장해야 됨으로 2중 dp를 통해 풀 수 있습니다. Solution 이중 배열을 dp[현재 연도][태어난 연도] = 벌레 수 로 정해서 풀어봅시다. 2중 포문을 통해 매년마다 dp[현재 연도][현재 연도] = dp[현재 연도-1][태어난 연도] 로 분열된 벌레를 저장해준다. 기존에 남아있던 벌레는 홀수 3년, 짝수 4년 안에 분열된 벌레라면 dp[현재 연도][분열된 연도] = ..

[백준(BOJ)] 문제집(1776) C++ 문제 : BOJ_1776번 문제집 문제 설명 위상정렬, bfs, 우선순위 큐 1~N 번까지 문제가 주어질 때, 세 가지 조건이 주어집니다. (1) N 개의 문제는 모두 풀어야 되고 (2) 문제에 대한 정보(M)에 맞게 순서대로 풀어야 되고, (3) 가능하면 낮은 수의 쉬운 문제부터 풀어야 됩니다. 이 문제는 위상 정렬을 이용하여 주어진 문제들끼리의 위상을 파악해야 되는 것도 물론이지만, 이 문제는 3번 문제가 추가되면서 그냥 위상 정렬로만은 풀 수 없는 문제가 되어버립니다. 서로 방향성이 있는 문제는 그 순서에 맞게 풀어야 되지만, 서로 간의 방향이 없는 문제들끼리는 낮은 수의 문제부터 푸는 게 이 문제의 포인트입니다. Solution 이 문제는 우선 bfs와 ..

[백준(BOJ)] 양 구출 작전(16437) C++ 문제 : BOJ_16437번 양 구출 작전 문제 설명 위상정렬, bfs 제목만 귀엽고 문제는 징그러운 양 구출 작전입니다. 문제에 정확히 제시되어 있는 '1번 섬으로 가는 경로는 유일' 을 주의해서 읽어야 하고, 각 섬에 양 혹은 늑대가 있는 데, 섬에 양이 있다면 다음 섬으로 넘어가는 양의 수가 누적되고, 늑대가 있다면 늑대의 수만큼 양의 수가 줄어들고, 양을 한 마리 잡아먹은 늑대는 더 이상 양을 잡아먹지 않기 때문에 늑대의 수도 줄은 것과 같습니다. 문제에서 친절하게 그림을 제시해주었는데, (두 번째 테스트 케이스에 대한 그림) n 번 째 섬과 연결된 섬들의 모든 양이 누적되어 n 번 째 섬에 도착하는 방식입니다. 즉, 양의 누적수를 파악하기 위해..

[백준(BOJ)] 행복한 소수(10434) C++ 문제 : BOJ_10434번 행복한 소수 에라토스테네스의 체 문제 제목과는 달리 사람 참 불행하게 만드는 소수입니다... 이 문제에서는 어떤 수를 주었을 때, 두 가지 조건을 만족하는가를 탐색하는 문제입니다. 어떤 수가 행복한 수 인가? - 행복한 수는 주어진 수의 각 자릿수의 제곱을 곱해서 더 해주고 나온 수를 또 각 자릿수의 제곱을 곱해주는 방법을 반복해서 1이 될 수 있는 수를 의미합니다. 어떤 수가 소수인가? - 여기서 소수 판별을 수마다 해줘야 하는데, 테스트 케이스의 최대수는 1000, 각 테스트 케이스의 최대 번호는 10000이기 때문에 에라토스테네스의 체를 이용하지 않는다면 시간 초과가 되고 맙니다 (에라토스테네스에 대한 자세한 설명은 이 ..