알고리즘/문제

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. 연합된 각각의 도시들의 인구..

https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 🌿 - 문제 설명 📌- 풀이 다양한 풀이 방법이 있겠지만 여기서는 일단 BFS, 비트마스킹을 사용해서 풀었고 Room 객체 배열을 만들어서 각자 배열에 부모의 번호, 방의 크기, 초기값에 대한 정보를 담았다. 0,0부터 BFS를 돌면서 부모가 누구인지 각각의 배열에 담으면서 -> 1과 2번을 구했고 이런식으로 부모의 위치에 해당 방의 크기값이 저장 된다. 다시 한번 반복문을 돌면서 해당하는 ..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🌿 - 문제 설명 📌- 풀이 플로이드 워셜로 전체 그래프에서 갈 수 있는 곳을 전부 map에 기록을 하고 시작 지점에서 각각 지점까지 전부 갈 수 있다면 YES, 한 곳이라도 못간다면 NO를 출력하는 방식으로 풀었다. 플로이드 워셜로만 풀었는데 다른 풀이들을 찾다보니 Union_Find로 문제를 푸는 방식들이 많아서 그것들을 참고해서 다시 풀어봤다. 유니온 파인드에 대한 설명은 여기 블로그에 자세..

https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 🌿 - 문제 설명 https://skygood95.tistory.com/38 백준 14466 문제를 이해하는데 시간이 오래 걸렸던 문제 기본적으로 이렇게 소와 다리가 위치하고 있다. 주황색 소에서 하늘색 소로 가는 경우는 다리를 이용하지 않고 이렇게 이동할 수 있다. 그러나 주황 skygood95.tistory.com 이 분이 그림으로 설명을 잘해주셔서 ..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 🌿 - 문제 설명 간단하게 정리하면 외부 공기랑 접촉한 치즈들 중 C로 표시된 치즈를 녹이고 전부 다 녹는데 걸리는 시간을 구하는 문제이다. 토마토 문제랑 유사해서 토마토 문제들을 풀어보고 이 문제를 풀어보면 조금 더 쉽게 풀 수 있다는 생각이 든다. https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N..