알고리즘
-
[백준] 17086 아기 상어 2 with PythonPS 2022. 7. 17. 22:03
📌 BOJ 17086 아기 상어 2 💡 조건 N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다. N과 M(2 ≤ N, M ≤ 50) 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다. 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다. 안전 거리가 가장 큰 칸을 구하는 문제. heapq, 우선순위 큐 유형의 문제 🖥 소스 코드 from sys import stdin import heapq n, m =..
-
[백준] 14495 피보나치 비스무리한 수열 with PythonPS 2022. 7. 17. 01:39
📌 BOJ 14495 피보나치 비스무리한 수열 💡 조건 피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다. 자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구하는 문제. 자연수 n의 범위는 (1 ≤ n ≤ 116) 이다. DP 유형의 문제 🖥 소스 코드 from sys import stdin dp = [0 for _ in range(120)] dp[0:3] = [1, 1, 1, 2] for x in range(4, 117): dp[x] = (dp[x - 3] + dp[x - 1]) print(dp[int(stdin.readline()) - 1])🔖 예제 및 실행결과 예제 10..
-
[백준] 10159 저울 with PythonPS 2022. 7. 17. 01:25
📌 BOJ 10159 저울 💡 조건 무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있다. 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.) [1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5] 우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없다..
-
[백준] 14494 다이나믹이 뭐예요? with PythonPS 2022. 7. 14. 23:07
📌 BOJ 14494 다이나믹이 뭐예요? 💡 조건 다이나믹 프로그래밍(동적 계획법), 다이나믹은 이름이 엄청 거창하지만 사실 이름에 비해 개념은 간단하다. 다이나믹의 기본 아이디어는 바로 이전에 계산한 값을 사용해서 (= 이미 계산된 값을 사용해서, 어려운 말로 메모이제이션.) 반복되는 똑같은 연산 횟수를 줄이는 것. 다차원 배열로도 가능하다. 오른쪽, 아래쪽으로만 움직일 수 있을 때, D[1][1]에서 D[x][y]까지 도달하는 경우의 수를 구하는 문제는 일일히 모든 경우를 다 계산할 필요 없이, D[i][j] = (i, j)에 도달하는 누적 경우의 수 = D[i-1][j] + D[i][j-1]를 세워서 해결할 수도 있다. →, ↓, ↘의 세 방향만 사용해서 한 번에 한 칸씩 이동할 때, 왼쪽 위 (1..
-
[백준] 3079 입국심사 with PythonPS 2022. 7. 14. 20:36
📌 BOJ 3079 입국심사 💡 조건 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다. (1 ≤ Tk ≤ 109) 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 상근이와 친구들..
-
[백준] 2548 대표 자연수 with PythonPS 2022. 7. 12. 15:52
📌 BOJ 2548 대표 자연수 💡 조건 정보초등학교의 연아는 여러 개의 자연수가 주어졌을 때, 이를 대표할 수 있는 대표 자연수에 대하여 연구하였다. 그 결과 어떤 자연수가 다음과 같은 성질을 가지면 대표 자연수로 적당할 것이라고 판단하였다. “대표 자연수는 주어진 모든 자연수들에 대하여 그 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수이다.” 예를 들어 주어진 자연수들이 [4, 3, 2, 2, 9, 10]이라 하자. 이때 대표 자연수는 3 혹은 4가 된다. 왜냐하면 (4와 3의 차이) + (3과 3의 차이) + (2와 3의 차이) + (2와 3의 차이) + (9와 3의 차이) + (10과 3의 차이) = 16, (4와 4의 차이) + (3과 4의 차이) + (2와 4의 차이) + (2와 ..
-
[백준] 1939 중량제한 with PythonPS 2022. 7. 12. 15:12
📌 BOJ 1939 중량제한 💡 조건 N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다. 영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다. 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,..
-
[백준] 1068 트리 with PythonPS 2022. 7. 7. 22:19
📌 BOJ 1068 트리 💡 조건 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 문제. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울..
-
[백준] 17103 골드바흐 파티션 with PythonPS 2022. 7. 6. 16:55
📌 BOJ 17103 골드바흐 파티션 💡 조건 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다. 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. 정수론, 소수판별, 에라토스테네스의 체 유형의 문제 🖥 소스 코드 from sys import stdin def prime_list(n): sieve = [False, False] + [True] * n m = int(n ** 0..
-
[백준] 16956 늑대와 양 with PythonPS 2022. 7. 2. 01:20
📌 BOJ 16956 늑대와 양 💡 조건 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다. 목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자. 목장의 크기 R, C가 주어진다. R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다. 1 ≤ R, C ≤ 500 늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에..