본문 바로가기

vividswan

Notice

블로그 이전 완료

Recent Posts

Popular Posts

Recent Comments

Link

깃허브

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

c++

Algorithm/BOJ 2022. 3. 5. [BOJ] 폴짝폴짝(1326) [백준(BOJ)] 폴짝폴짝(1326) C++ 문제 : BOJ_1326번 폴짝폴짝 문제 설명 bfs, pair bfs를 이용한 최소 점프 수를 출력하는 문제입니다. 유사한 문제로는 bfs를 활용한 백준 1697번 숨바꼭질이 있습니다. Solution dfs와 bfs를 이용하는 문제들 중 어떤 상황에서 두 개 중 하나를 선택해야 되는지 고민이 될 때가 있는데, 목적지에 도달하는 여러 가지 경우의 수를 다 확인해야 되기보다는 목적지에 도달하는 최소 거리, 최소 시간 등의 문제를 풀 때는 보통 bfs로 풀리는 문제들이 많습니다. Description 징검다리에 쓰여 있는 수 들을 각 징검다리의 번호에 맞는 배열에 넣어준다. pair를 이용하여 도달한 징검다리의 번호를 pair의 first에, 도달하기까지 점프한..

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

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

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

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

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

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

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

이전 1 ··· 3 4 5 6 7 다음

티스토리툴바