본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / BOJ] 1135 뉴스 전하기 문제 출처 : https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 민식이는 회사의 매니저이다. 민식이는 회사의 뉴스를 모든 직원들에게 전하려고한다. 회사의 모든 직원들은 정확히 한명의 선임이 있으며, 자신은 자신의 선임이 아니다. 모든 직원들은 모두 민식이의 간접,직접적인 부하이다. 모든 사람은 자신의 직속부하에게만 뉴스를 전달할수있고, 이때, 1분의 시간이 걸린다. 모든 직원이 뉴스를 전달받는 최소시간을 구하는 문제다. 풀이 그리디로 풀은 문제다. 직..
[백준 / BOJ] 9376 탈옥 문제 출처 : https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 상근이는 감옥에서 죄수 두명을 탈옥시킬려고한다. N*M크기의 감옥이있고, 감옥은 # : 문 . : 빈 공간 $ : 죄수 로 구성되어있으며, 죄수는 항상 2명이다 (문이 있는곳은 지나가기위해 문을 열어야한다.) 모든 죄수를 탈출시키기 위해서 열어야 하는 문의 최솟값을 출력하는 문제였다. 풀이 다익스트라로 풀은 문제다. 처음 문제를보고 그냥 BFS를 돌리면 될것같다고 생각했는데, 한 죄수가 밖으로 ..
[백준 / BOJ] 13907 세금 문제 출처 : https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 주언이는 두 도시를 오가며 무역을 한다. 이때, 도시의 통행료가 가장적은 길로 이동을 하려고한다. 도시들은 양방향으로 연결되어있으며 도로마다 통행료가 존재한다. 나라에서 도로의 통행료를 인상시킬려고한다. 통행료를 A만큼 인상시켰다면, 모든 도로의 통행료는 A만큼 증가한다. 주언이의 최초 최소통행료와, 세금이 오..
[백준 / BOJ] 3197 백조의 호수 문제 출처 : www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 호수에 백조 두마리가 살고있다. 호수의 어떤칸은 얼음으로 덮여있으며, 매일 물과 접촉해있는부분은 녹는다. 백조는 얼음이 없는 위치로 움직일수있을때, 두 마리의 백조가 만나기위해 걸리는 최소 시간을 구하는 문제다. 풀이 BFS와 다익스트라로 푼 문제다. 백조는 움직일때 시간이 걸리지않는것에 유의해야했다. 구현은 백조가 어떤칸에 가기위해선 해당칸까지 가는 경로가 전부 얼음..
[백준 / BOJ] 1102 발전소 문제 출처 : www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 은진이의 회사에는 N개의 발전소가 있다. 은진이가 회사에서 잘때마다 몇몇 발전소가 고장이난다. 이때, 고장난 발전소는 고장나지않은 발전소를 이용해 고칠수있으며, 일정한 비용이 발생한다. 적어도 P개 이상의 발전소가 고장나 있지 않도록 발전소를 고치는 최소비용을 구하는 문제다. 풀이 dp로 풀은문제다. 그리디로는 해결하지못하는데, 현재 경로가 더 많은 비용을 필요로 하더라도 결과적으로 더 작은 비용으로 발전소를..
[백준 / BOJ] 2169 로봇 조종하기 문제 출처 : https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net NASA의 화성탐사로봇은 N*M배열의 화성을 탐사할려한다. N*M배열의 각 칸에는 절댓값이 100을 넘지않는 정수들이 쓰여있고, 이 값은 그 칸을 방문했을때 얻을수있는 가치와 같다. 화성탐사로봇이 (1,1)위치에서 (N,M)위치까지 탐사할때, 얻을수있는 최대 가치를 구하는 문제였다. 풀이 얼핏?보면 그래프 문제같지만, 음수가중치가 존재하므로, dp로 풀어야했던 문제였다. 문..
[백준 / BOJ] 1275 커피숍2 문제 출처 : https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 커피숍 마담 동호는 손님들과 게임을한다. 게임 방식은 다음과 같다. N개의 수가 있으면 동호는 손님에게 3~7번째 수를 묻는다. 이때, 손님이 답은 000 입니다 라고 대답을한다. 그후, 8번째 수를 2로 고친다. 풀이 기본적인 세그먼트 트리로 풀리는 문제였다. 구현은 다음과 같다. 1. 입력받은 정수N개를 세그먼트 트리구조로 저장해놓는다. 2. 쿼리를..
[백준 / BOJ] 2560 짚신벌레 문제 출처 : https://www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 한 생물학자가 새로 발견된 짚신벌레에 대해 연구하고있다. 짚신벌레는 1. 태어난지 a일째 되는날부터 새로운 개체를 생성한다. 2. 태어난지 b일째 되는날부터 새로운 개체생성을 중지한다(a일부터 b-1일 까지 개체를 생성함) 3. 태어난지 d일째 되는날 죽는다. 수조안에 짚신벌레가 한마리 있다할때, N일 지난후 살아있는 짚신벌레 개체수를 구하는 문제다. 풀이 완전탐색으로 풀경우, d*d*N = O(N*(d^2))이 되..

티스토리툴바