본문 바로가기

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

 (260)
[백준 / BOJ] 2056 작업 문제 출처 : www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net N개의 수행할 작업과, 각 작업을 수행하는데 걸리는 시간이 주어진다. 작업에는 선행관계가 있고, 각 작업을 수행하기위해선, 해당 작업의 선행작업을 수행해야한다. 이때, 모든 작업을 수행하는데 걸리는 최소시간을 구하는 문제다. 풀이 재귀와 메모이제이션으로 풀리는문제다. 현재 작업 A를 수행해야하고 A의 선행 작업이 B,C,D라고 할때, B,C,D가 걸리는 수행시간중 최댓값을 가져와서 A가 ..
[백준 / BOJ] 1806 부분합 문제 출처 : www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 수열의 길이 N과 만들어야할 최소 수 S가 주어진다. 수열의 각 원소들의 합이 S이상이 되는 최소 길이를 구하는 문제다. 풀이 N이 최대 10만까지 가기때문에, 최악의 경우 100001 * 50000번 반복해서 시간초과가 난다. 투포인트로 풀었는데, 수열의 인덱스를 나타내는 변수 p1, p2를 선언한다. p1 ~ p2의 합이 S보다 커질때까지 p2를 증가시킨다. 이때, 합이 S보다 ..
[백준 / BOJ] 1719 택배 문제 출처 : www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net n개의 집하장에 택배가있다. 각 집하장에서 다른 집하장으로 이동거리를 최소화하여 택배를 보낼려한다. m개의 집하장 경로와 이동거리가 주어졌을때, 경로표를 만드는 문제다. (경로표는 현재 집하장에서 다른집하장으로 택배를 이동시킬려할때 가장 먼저 거쳐가야할 집하장을 표시한 표이다.) 풀이 플로이드 와샬을 이용해 푸는문제다. dp배열을 pair로 선언해 로 저장해놓는다. 현재 i,j에 저장된 값보..
[백준 / BOJ] 10868 최솟값 문제 출처 : www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net N개의 숫자들을 입력받고 구간 (a,b)를 M번 입력받는다. 구간 a,b사이에서 가장 작은 값을 출력하는 문제다. 풀이 N과 M이 최대 10만이라 모든경우를 다 봐주면 1억번돌아서 시간초과가 나기때문에, 세그먼트 트리를 이용해서 각 구간을 빠르게 찾아줘야한다. 세그먼트 트리에 각 구간의 최솟값을 저장한다. 예제 1의 경우, 구간 1~10 에서의 최솟값은 5, 구..
[백준 / BOJ] 1162 도로포장 문제 출처 : www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 도시의수 N, 도로의수 M, 포장할 도로의수 K가 주어진다. M개의 도로를 K만큼 포장할수있고, 포장한 도로의 비용은 0이될때, 최소비용을 구하는 문제다. 풀이 2206 벽 부수고 이동하기 와 비슷한 느낌의 문제였다. 다익스트라로 풀었는데, 포장횟수가 20까지밖에 안주어지므로 모든경우를 다 봐줘도 시간초과가 나지않는다. check배열을 2차원으로 만들어서, 체크..
[백준 / BOJ] 1395 스위치 문제 출처 : www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net N개의 스위치가 있고 M번의 명령이 주어진다. 명령은 O,S,T의 형태로 주어지는데, O가 1 이라면, S부터 T까지 켜져있는 전구의 갯수를 구하는 명령이고, O가 0이면, S부터 T까지의 전구의 상태를 반전시키는 명령이다. 풀이 구간 합 구하기 2와 비슷하게 풀리는 문제였다. N이 10만, M이 10만이므로, 한번 업데이트시 최악의경우 10만log10만번 ..
[백준 / BOJ] 10999 구간 합 구하기 2 문제 출처 : www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 수의 개수 N, M, K가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 각 구간의 합을 구하는 횟수이다. 앞의 수에 따라서, 변경, 합을 구하면되는데, 1은 변경이고 2는 구간합이다. 예를들어, 1 1 5 10 이 나오면, 1부터 5범위까지 +10을 해주면된다. 풀이 N의 최댓값이 1,000,000이고, M과 K가 각각 1..
[백준 / BOJ] 17087 숨바꼭질 6 문제 출처 : www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 수빈이가 동생'들'과 숨바꼭질을한다. 선영이는 +D, -D만큼 이동할수있다. 선영이의 위치와 동생들의 위치가 주어졌을때, 선영이가 모든 동생을 찾을수있는 최대 D값을 찾는문제다. 풀이 수학문제다. 선영이는 모든 동생을 찾아야한다. 선영이는 항상 +D, -D만큼 움직일수있으므로, 모든 동생과의 거리차들의 최대공약수만큼 움직여야 모든동생들을 찾을수있다. 1. 선영이의 ..

티스토리툴바