백준 알고리즘/Problems
-
[BOJ/1516] 게임 개발 - 풀이 및 코드백준 알고리즘/Problems 2023. 8. 19. 21:06
1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 풀이 1번부터 N번 까지의 각 건물을 짓는데 드는 비용을 출력하면 되는 문제입니다. 단, 건물을 지을 때 특정 건물을 짓고 나서 건물을 지을 수 있는 경우가 있습니다. 즉, 건물을 짓는데 요구되는 요구사항 건물이 존재하는 것이죠. 단순하게 생각하면, 최악의 경우 시간복잡도가 O(N^3)이 됩니다. A라는 건물을 짓기 위해서는 그 건물을 짓기 위한 요구 건물을 미리 지어야 하며, 여러 개의 건물을 동시에 지을 수 있기 때문에 A라는 건물을 짓기 위..
-
[BOJ/2225] 합분해 - 풀이 및 코드백준 알고리즘/Problems 2023. 8. 16. 02:59
2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 문제를 단순하게 생각해서 푼다면 어떻게 풀 수 있을까요? 0부터 N까지의 숫자 중 K개를 더해 합을 N으로 만드는 경우의 수를 백트래킹 기법으로 완전탐색 할 수 있습니다. 완전탐색하게 되면 총 시간 복잡도는 O(2^n)만큼 걸리게 되기 때문에 완전탐색으로는 문제를 다항식 시간 내에 해결할 수 없습니다. 그렇다면 문제가 원하는 경우의 수가 어떻게 생성되는지 알아보겠습니다. 만약 N을 3으로 고정하고 K가 1인 경우를 생각해보면 다음과 같은 결과를 얻을 수 있습니다. 숫자 1개를 사용해 숫자 0~N을 만드는 경우는 모두 1가지 방법 밖에 존재하지 않습니다. 이번엔 K가 2인 경우에..
-
[BOJ/21758] 꿀 따기 - 풀이 및 코드백준 알고리즘/Problems 2023. 8. 12. 00:25
21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 문제 풀이 문제를 단순히 생각하면, 벌통의 위치와 두 꿀벌의 위치를 완전탐색하는 방법이 있지만, 3중 반복문을 사용해야 하기 때문에 시간 초과가 발생하게 됩니다. 또한, 벌통의 위치와 두 꿀벌의 위치가 정해진다고 하더라도 꿀벌의 위치부터 벌통의 위치까지 순회(시뮬레이션)하는 경우, 그에 대한 시간복잡도는 O(N)이기 때문에 최종적으로 O(N^4)의 시간복잡도를 가지게 됩니다. 시간복잡도를 줄이기 위해 문제의 특징을 살펴보겠습니다. 우선, 각 배열에 적혀있는 꿀의 양이 양수이며 꿀벌들은 벌통을 향해서 날라가고 벌통 이후의 꿀들은 채집하지 않습니다. 이러한 조건이 존재하기에 문제의 상황을 다음과 같이 나눠볼..
-
[BOJ/1149] RGB 거리 - 풀이 및 코드백준 알고리즘/Problems 2023. 8. 6. 19:38
문제 설명 과정 N개의 집이 존재하고 해당 집을 채색하는데 드는 비용이 주어지며, 인접한 집은 세가지 색(R, G, B) 중 서로 다른 색깔로 칠할 때, 모든 집을 칠할 때 드는 비용의 최소값을 출력하면 되는 문제입니다. 처음에는 그리디 알고리즘을 사용해서 풀어도 될 것 같은 생각이 들었지만, 다음과 같은 상황에서는 불가능합니다. (탐욕법을 이용하여 최소 비용을 구하려고 하면 아래 사례에선 절대로 최소 비용을 구하지 못합니다) index: 1 2 3 R: 1 9 1 G: 1 10 100 B: 1 10 100 현재 "가장 좋은 대안을 선택" 하였을 때 "그 선택으로 인해 추후 더 나은 선택을 할 수 없다." 라는 점 때문에 탐욕법은 사용할 수 없습니다. 그런데 위와 같은 반례를 작성해보며 이전 선택을 "기..
-
[BOJ/7576] 토마토백준 알고리즘/Problems 2023. 7. 25. 13:57
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는..
-
[BOJ/15686] 치킨 배달백준 알고리즘/Problems 2023. 7. 13. 18:02
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 과정 NxN의 마을 정보가 주어지고, 그 중 최대 M개의 치킨집을 제외한 모든 치킨집을 폐업한다고 할 때 도시 치킨 거리의 최소 값을 구하면 되는 문제입니다. 보기엔 굉장히 복잡해 보이지만 규칙이 숨어있는 문제이기 때문에 다음과 같이 순차적으로 접근해서 문제를 풀어보겠습니다. 행렬(마을 정보)를 입력받는다. 각 집에서 마을에 존재하는 모든 치킨집의 거리를 담은 2차원 행렬을 구합니다. 즉, K번째 행은 마을에 존재하는 K번째 집과 모든 ..
-
[BOJ/9095] 1, 2, 3 더하기백준 알고리즘/Problems 2023. 7. 10. 17:24
문제 과정 4라는 숫자를 1, 2, 3을 이용해 표현하면 다음과 같다 하였다. - 1+1+1+1 - 1+1+2 - 1+2+1 - 2+1+1 - 2+2 - 1+3 - 3+1 위 케이스를 잘 째려보다 보면 이런 생각이 든다. 4라는 숫자는 3에 1을 더해서 만들 수 있고, 2에 2를 더해서 만들 수 있고, 1에 3을 더해서 만들수 있다! 그렇다면 이런 점화식을 얻을 수 있다. f(n)은 n이라는 숫자를 (1, 2, 3)의 합으로 나타내는 방법의 개수를 뜻하는 함수이다. f(1) = 1, f(2) = 2, f(3) = 4 n이 만약 3보다 크다면 f(n)은 다음과 같이 정의된다. f(n) = f(n-1) + f(n-2) + f(n-3) 어째서 f(n) = f(n-1) + f(n-2) + f(n-3) 일까? f..
-
[BOJ/3040] 백설 공주와 일곱 난쟁이백준 알고리즘/Problems 2023. 7. 2. 22:13
목표 과정 아홉 난쟁이의 수 중 합이 100이 되는 일곱 난쟁이를 구하면 되는 문제입니다.반대로, 아홉 난쟁이 중 두 난쟁이를 골라 전체의 합이 100이 되면 되는 문제이기도 합니다. 아홉 난쟁이의 수를 리스트에 담은 후, 모든 난쟁이의 수를 더한 뒤 해당 수와 두 난쟁이의 수의 차를 100과 빠지지 않고 비교하면 되는 문제입니다. 결과 # 리스트에 난장이들의 숫자를 집어넣음 arr = [] for i in range(9): elem = int(input()) arr.append(elem) total = sum(arr) # (0, 1) (0, 2), ... (7, 8) 이런식으로 100에서 해당 인덱스의 수를 빼고 100인지 확인 flag = False for i in range(0, 8): for j ..