본문 바로가기

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

 (260)
[백준 / BOJ] 1253 좋다 문제 출처 : www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net N개의 수열이 주어진다. 이때, N개의 수 중에서, 어떤 수가 다른 수 두개의 합으로 나타내진다면, 그 수를 좋다 라고한다. 좋은수가 몇개인지 구하는 문제다. (위치가 다르면 값이 같아도 다른 수 이다.) 풀이 완전탐색으로 풀경우 O(N^3)이 되어서 시간초과가 난다. 시간초과를 피하기 위해, 이분탐색으로 풀은 문제다. 로직은 간단한데, 수열 N에서 i번째수를 Ni라 할때, 1. 좋은 수 인지 판단할 수 Ni를 하나 지정한다..
[백준 / BOJ] 1202 보석 도둑 - (유니온 파인드, 이분탐색) 문제 출처 : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 상덕이는 보석을 털기로 결심했다. 보석점에 총 N개의 보석이 있고, 각 보석은 M의 무게, V의 가격을 갖고있다. 상덕이는 K개의 가방을 갖고있고, 각 가방에는 최대 Ci무게의 보석을 담을수있다. 이때, 각 가방에는 최대 한개의 보석만 담을수있다. 상덕이가 홈칠수있는 보석의 최대 가격을 출력하는 문제다. 풀이 보석의 수 N..
[백준 / BOJ] 10775 공항 문제 출처 : www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 공항에 G개의 게이트가 있으며, P개의 비행기가 순서대로 들어온다. 각 비행기는 1~Pi번째 게이트에 도킹할수있으며, 만약 1~Pi번째 게이트가 다른비행기로 차있어 도킹하지못한다면, 공항이 폐쇄된다. 공항이 폐쇄되기 전까지 최대 몇개의 비행기를 도킹할수있는가 구하는 문제다. 풀이 유니온 파인드를 이용해 풀은 문제다. 비행기와 게이트가 최대 10만까지 갈수있으므로,..
[백준 / BOJ] 16985 Maaaaaaaaaze 문제 출처 : https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 미로를 나타내는 5*5크기의 판이 5개 주어진다. 판의 각 칸에는 이동할수없는칸 0, 이동할수있는칸 1이 있다. 5개의 판은 자유롭게 쌓을수있고 각 판마다 자유롭게 90도 회전또한 가능하다. 이때, 판을 적절히 쌓고 적절히 회전해서 5*5*5크기의 미로를 탈출하는 최소 이동횟수를 구하는 문제다. 입구는 5*5*5크기의 그리드의 각 모서리이며 출구는 입구와 면을 ..
[백준 / BOJ] 8980 택배 문제 출처 : https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net C만큼의 용량을 실을 수 있는 트럭이 있다. N개의 마을이 있으며, A마을에서 B마을로 용량 D의 택배를 보낼려고한다. M개의 보낼 택배의 시작장소, 도착장소 용량이 주어질때 트럭 한 대로 보낼 수 있는 최대한 많은 택배의 양을 구하는 문제다. 풀이 모든 경우를 봐줄경우, 구현에 따라 최악의 경우 2^M번 반복하므로 완전탐색으로는 시간안에 풀기 힘들다. 그리디를 ..
[백준 / BOJ] 1256 사전 문제 출처 : www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net "a","z"로만 이루어진 문자열이 수록된 사전이있다. 사전에 있는 문자열은 모두 알파벳 순서로 정렬되어있다. "a"의 갯수 N, "z"의 갯수 M이 주어질때, K번째 문자열이 무엇인지 찾는 문제다. 풀이 수학 문제였다. N과 M이 각각 100까지 갈수있기때문에. 완전탐색으로 모든 가지를 만들며 풀경우 약 10^60번 반복하며 시간안에 절대 풀지못한다. 조합을 이용해 찾고자하는 칸 만큼 건너뛰면서 K번째 문자열을 찾아야했다. 아이디어는 다음과 ..
[백준 / BOJ] 1248 맞춰봐 문제 출처 : www.acmicpc.net/problem/1248 1248번: 맞춰봐 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 www.acmicpc.net 규현이는 -10 ~ 10 까지 총 21개의 숫자를 알고있으며, 이 수를 구간합으로 나타냈다. S[i][j] 는 i번째 숫자부터 j번째 숫자까지의 구간합이며 이 값이 양수면 +, 음수면 -, 0이면 0이 된다. S[i][j]의 각 원소들이 모두 주어졌을때 원래 수열이 무엇인지 찾는 문제였다. 풀이 완전탐색(백 트래킹)으로 풀리는 문제였다. 각 칸에 숫자를 넣어보고 숫자를 넣을수있다면, 재귀를 호출..
[백준 / BOJ] 1613 역사 문제 출처 : www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net n개의 사건의 개수, k개의 사건의 전후 관계, s개의 알고싶은 사건의 전후관계가 주어진다. 이때, 알고싶은 사건을 각각 A,B라 했을때 A사건이 B사건 보다 먼저 일어났으면 -1 아니라면 1 알수없다면 0을 출력하는 문제다. 풀이 플로이드 와샬로 풀리는 문제다. 사건의 전후 관계의 개수k 가 최대 50000이므로 사건의 전후관계를 파악할때마다 매번 탐색을 해주면 시간초과가 난다. 전처리를..

티스토리툴바