자료구조
-
[백준] 1890 점프 with PythonPS 2022. 8. 9. 17:33
📌 BOJ 1890 점프 💡 조건 N×N 게임판에 수가 적혀져 있다. N (4 ≤ N ≤ 100) 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로..
-
[백준] 1722 순열의 순서 with PythonPS 2022. 8. 9. 17:18
📌 BOJ 1722 순열의 순서 💡 조건 1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다. 임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 문제 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나..
-
[백준] 1081 합 with PythonPS 2022. 7. 22. 20:06
📌 BOJ 1081 합 💡 조건 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 문제. 0 ≤ L ≤ U ≤ 2,000,000,000 수학 유형의 문제 🔖 예제 및 실행결과 예제 24660 308357171실행결과 11379854844⌨️ 문제 풀이 가장 먼저 문제를 보며 주목해야할 부분은 L과 U의 범위이다. L과 U의 범위는 최대 20억까지로, 일일히 검사했을 때 최악의 경우에는 0부터 20억까지의 모든 수를 검사해야하기 때문에 문제에서 주어진 2초라는 시간 안에 절대 해결할 수가 없다. (1)번에서 정리한대로, 우리는 L과 U의 범위를 입력받아 일일히 숫자 하나씩 검사하는 방법을 피해 각 숫자의 자릿수를 더해 답을 출력해야 한다. L, U 를 입력받아 L보다 크거나 같고..
-
[백준] 1005 ACM Craft with PythonPS 2022. 7. 17. 22:33
📌 BOJ 1005 ACM Craft 💡 조건 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경..
-
[백준] 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와 ..