본문 바로가기

알고리즘

 (151)
[백준 / 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이므로 사건의 전후관계를 파악할때마다 매번 탐색을 해주면 시간초과가 난다. 전처리를..
[백준 / BOJ] 10875 뱀 문제 출처 : www.acmicpc.net/problem/10875 10875번: 뱀 가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 www.acmicpc.net 2차원 그리드에서 뱀이 움직인다. 뱀은 1초가 지날때마다, 바라보는 방향으로 한 칸씩 몸의 길이를 늘려가며 움직인다. 뱀은 자신의 몸과 닿거나 2차원 그리드 범위 밖으로 나가면 몸을 늘리며 숨을 거둔다. 뱀이 머리를 회전하는 시간과 방향이 주어질때, 뱀이 언제 숨을 거두는지 출력하는 문제다. 풀이 시뮬레이션 문제다. 문제의 조건을 읽어보면, 그리드의 길이가 가로 세로 각각 최대 4..
[백준 / BOJ] 2098 외판원 순회 문제 출처 : www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고한다. 이때, 이미 방문한 도시는 재방문할수없다. 도시를 이동할때 일정한 비용이 필요할때, 외판원이 모든 도시를 거쳐 출발도시로 돌아오는 최소 비용을 구하는 문제다. 풀이 완전탐색으로 풀려고할경우, N이 최대 16이므로, 16 * 15 * 14 ..
[백준 / BOJ] 1052 물병 문제 출처 : www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 지민이는 N개의 물병을 갖고있다. 각 물병에는 물을 무한대로 부을 수 있는데, 처음에 모든 물병에는 물이 1리터씩있다. 지민이는 N개의 물병을 적절히 합쳐 K개이하의 물병으로 만들려하는데, 물병을 합칠때 는 다음 규칙에 따라 합칠수있다. - 같은 물이 들어있는 물병만 합칠수있다. 이때, 물병을 더 이상 합칠수없다면, 1리터의 물이 들어있는 물병을 추가할수있다. K개 이하의 물병을 만들기위해 추가해야할 ..
[백준 / BOJ] 1029 그림 교환 문제 출처 : www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 사람들이 그림을 사고팔려고한다. 모든 그림 거래는 다음 조건을 만족해야한다. 1. 그림을 팔때, 그림을 산 가격보다 크거나 같은 가격으로 팔아야한다. 2. 같은 그림을 두 번 이상 사는 것은 불가능하다. 항상, 1번 사람이 그림을 0원에 샀다고했을때, 그림을 소유했던 사람의 수의 최댓값을 출력하는 문제다. 풀이 완전탐색으로 풀면, 최악의경우 첫 선택 = 15명 두번째 선택 = 14명 세번..

티스토리툴바