본문 바로가기

algorithm

 (54)
[백준 / 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))이 되..
[백준 / 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] 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] 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이므로 사건의 전후관계를 파악할때마다 매번 탐색을 해주면 시간초과가 난다. 전처리를..
[백준 / BOJ] 10875 뱀 문제 출처 : www.acmicpc.net/problem/10875 10875번: 뱀 가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 www.acmicpc.net 2차원 그리드에서 뱀이 움직인다. 뱀은 1초가 지날때마다, 바라보는 방향으로 한 칸씩 몸의 길이를 늘려가며 움직인다. 뱀은 자신의 몸과 닿거나 2차원 그리드 범위 밖으로 나가면 몸을 늘리며 숨을 거둔다. 뱀이 머리를 회전하는 시간과 방향이 주어질때, 뱀이 언제 숨을 거두는지 출력하는 문제다. 풀이 시뮬레이션 문제다. 문제의 조건을 읽어보면, 그리드의 길이가 가로 세로 각각 최대 4..

티스토리툴바