백준

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 🌿 - 문제 설명 📌- 풀이 여러가지 방법들을 생각해봤다. 처음부터 아래까지 전부 완전 탐색을 하면 어떨까? 이런식으로 계속해서 완전탐색을 하게 된다면 결과값이 나오게 될 것이다. 하지만 여기서 문제점이 N이 최대 10만까지 이므로 숫자가 늘어날수록 연산해야 할 양이 기하급수적으로 늘어나기 때문에 분명 시간초과가 날 것으로 예상된다. 여기서 다른 방법으로 DP를 생각했다. DP(다이나믹 프로그래밍)이란? htt..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 🌿 - 문제 설명 📌- 풀이 N의 최대치가 50이라 많아봤자 2500개의 도시만 있으므로 BFS를 통해서 탐색해도 시간초과가 나오지 않을 거라 생각해서 BFS로 풀었다. 1. BFS로 탐색하면서 주변의 도시들이 L이상 R이하인지 탐색 2. L이상 R이하라면 큐에 추가해서 연합된 도시를 형성 3. 큐에 추가된 도시들의 수와 합을 구함 -> 평균을 구함 4. 연합된 각각의 도시들의 인구..