백준 알고리즘
-
[BOJ/1005] ACM Craft - 풀이 및 코드 (런타임 에러 해결법)백준 알고리즘/Problems 2023. 8. 22. 20:16
1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 풀이 비슷한 문제인 게임 개발(https://highlaw00-dev.tistory.com/44) 문제를 이미 풀었습니다. 완전탐색의 시간복잡도와 사이클의 유무에 관해 포스팅해두었습니다. 이번 풀이에서는 파이썬의 특징으로 인해 발생하는 런타임 에러에 대해 간략히 다뤄보겠습니다. 재귀적으로 선행 건물의 비용을 구해야하기 때문에 재귀를 여러번 할 가능성이 존재합니다. 백준 채점 서버에서는 파이썬의 최대 재귀 횟수가 1000회로 지정되어 있습니다. 본 문제..
-
[BOJ/1504] 특정한 최단 경로 - 풀이 및 코드백준 알고리즘/Problems 2023. 8. 22. 20:07
1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 풀이 1번 노드부터 N번 노드까지의 최단 경로를 구하는 문제입니다. 단, 주어지는 v1, v2 노드를 중간에 반드시 방문해야하는 문제입니다. 노드의 수가 800개 이하이기 때문에 O(N^2)의 알고리즘으로 풀 수 있습니다. 또, 주어지는 간선의 가중치들은 모두 1000 이하의 자연수 라는 조건이 존재합니다. 문제 조건 중, 한 번 지나간 간선이나 정점을 다시 방문할 수 있다는 조건이 있기 때문에 다음과 같이 접근..
-
[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/28417/KAUPC2023] 스케이트보드백준 알고리즘/KAUPC2023 2023. 7. 31. 23:06
28417번: 스케이트보드 2020년부터 올림픽 정식 종목으로 포함된 스케이트보드는 스트리트와 파크 종목으로 나뉜다. 그 중 스트리트는 계단, 난간, 레일, 경사면 등 다양한 구조물을 활용해 기술을 구사하는 종목이다. www.acmicpc.net 문제 과정 KAUPC 2023의 첫번째 문제. 첫 Problem Solve 대회의 첫 문제여서 그런지 굉장히 비효율적인 코드를 작성했다. 주어지는 입력을 순서대로 2개, 5개로 분할하여 서로 다른 배열에 저장 2개의 점수가 저장된 배열은 둘 중에 더 큰 값을, 5개의 점수가 저장된 배열은 상위 2개의 값을 골라내어 그 셋의 합을 출력하면 되는 문제이다. 2개의 점수 중 더 큰 값을 골라내는 것은 어렵지 않고, 5개의 점수가 저장된 배열은 O(NlogN)안에 정렬..
-
[BOJ/7576] 토마토백준 알고리즘/Problems 2023. 7. 25. 13:57
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는..