자료구조
-
[백준] 22252 정보 상인 호석 with PythonPS 2022. 5. 18. 02:26
📌 BOJ 22252 정보 상인 호석 💡 조건 관찰하면서 얻은 정보는 총 $Q$ 개이다. 각 정보는 다음의 2가지 중 하나이다. 1 Name k C_1, C_2, ..., C_k : 이름이 [Name]인 고릴라가 k 개의 정보를 얻었으며, 각 가치는 C_1 부터 C_k 이다. 2 Name b : 호석이가 이름이 [Name]인 고릴라에게 b 개의 정보를 구매한다. 이때 고릴라가 가진 정보들 중 가장 비싼 b 개를 구매하며, 고릴라가 가진 정보가 b개 이하이면 가진 모든 정보를 구매한다. 고릴라들이 정보를 얻는 사건과 호석이가 거래하는 정보가 시간순으로 주어진다. 첫 번째 줄에는 쿼리의 개수 Q가 주어진다. Q 개의 줄에 걸쳐서 각 줄에 쿼리가 주어진다. 쿼리는 1이나 2로 시작한다. 1로 시작하는 경우에는..
-
[백준] 12761 돌다리 with PythonPS 2022. 3. 23. 16:33
📌 BOJ 12761 돌다리 💡 조건 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A, B 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배 나 B배의 위치로 이동을 할 수 있다. 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다. 첫 줄에 스카이 콩콩의 힘 A와 B, 그리고 동규의 현재위치 N, 주미의 현..
-
[백준] 11104 Fridge of Your Dreams with PythonPS 2022. 3. 22. 17:22
📌 BOJ 11104 Fridge of Your Dreams 💡 조건 2진수를 읽어 10진수로 출력하는 문제 진수변환 유형의 문제 🖥 소스 코드 from sys import stdin for _ in range(int(stdin.readline())): print(int(stdin.readline().rstrip(), 2))🔖 예제 및 실행결과 예제 5 000000000000000000000001 000000000001010101010101 000000000000000000001010 101011001010101100101101 111111111111111111111111실행결과 1 5461 10 11316013 16777215⌨️ 문제 풀이 int() 함수를 사용해 2진수를 10진수로 출력해준다. in..
-
[백준] 10211 Maximum Subarray with PythonPS 2022. 3. 22. 17:03
📌 BOJ 10211 Maximum Subarray 💡 조건 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제) N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하는 문제. 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000) 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin for _ in range(int(stdin.readline())): n = int(stdin.read..
-
[백준] 8974 희주의 수학시험 with PythonPS 2022. 3. 21. 18:43
📌 BOJ 8974 희주의 수학시험 💡 조건 연습문제 중에 하나가 정수를 적어나가는 것이였는데 수열은 1이 한 개, 2가 두 개, 3이 세 개.. 와 같이 만들어진다. 이제 강민이는 희주에게 두 개의 정수 A, B를 부를텐데, 그럼 희주는 주어진 수열에서 A번째와 B번째 사이에 있는 모든 수들의 합을 말해야한다. 희주에게 문제를 내기 위해 정답을 계산하는 문제 사칙연산, 구현 유형의 문제 🖥 소스 코드 from sys import stdin arr, res = [], 0 a, b = map(int, stdin.readline().split()) for i in range(1, 50): cnt = 0 while cnt != i: arr.append(i) cnt += 1 for i in range(a, b ..
-
[백준] 8911 거북이 with PythonPS 2022. 3. 21. 18:32
📌 BOJ 8911 거북이 💡 조건 2차원 평면 위에서 움직일 수 있는 거북이 로봇을 하나 가지고 있다. 거북이 로봇에게 내릴 수 있는 명령은 다음과 같이 네가지가 있다. F: 한 눈금 앞으로 B: 한 눈금 뒤로 L: 왼쪽으로 90도 회전 R: 오른쪽으로 90도 회전 L과 R명령을 내렸을 때, 로봇은 이동하지 않고, 방향만 바꾼다. 거북이는 항상 x축과 y축에 평행한 방향으로만 이동한다. 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형의 넓이를 구하는 문제. 단, 직사각형의 모든 변은 x축이나 y축에 평행이어야 한다. 거북이는 가장 처음에 (0, 0)에 있고, 북쪽을 쳐다보고 있다. 이 경우에 거북이가 지나간 영역을 모두 포함하는 직사각형은 선분이고, 선분은 한 변이 0인 직사각형으로 생..
-
[백준] 5671 호텔 방 번호 with PythonPS 2022. 3. 18. 18:06
📌 BOJ 5671 호텔 방 번호 💡 조건 선영이는 투숙객에게 불운이 찾아오는 것을 피하기 위해서 반복되는 숫자가 없게 방 번호를 만들려고 한다. 정부는 선영이의 호텔 방 번호는 N보다 크거나 같고, M보다 작거나 같아야 한다는 조건을 걸고 신축 허가를 내주었다. 선영이의 새 호텔에는 방이 최대 몇 개 있을 수 있을까? 두 방이 같은 방 번호를 사용할 수 없다 입력은 여러 개의 테스트 케이스로 이루어져 있고, 한 줄이다. 각 줄에는 문제의 설명에 나와있는 N과 M이 주어진다. (1 ≤ N ≤ M ≤ 5000) 각각의 테스트 케이스에 대해서 N보다 크거나 같고, M보다 작거나 같은 수 중에서 반복되는 숫자가 없는 것의 개수를 출력한다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys impo..
-
[백준] 1758 알바생 강호 with PythonPS 2022. 3. 17. 23:58
📌 BOJ 1758 알바생 강호 💡 조건 손님들은 입구에 들어갈 때, 강호에게 팁을 준다. 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다. 각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다. 사람의 수 N과, 각 사람이 주려고 생각하는 팁이 주어질 때, 손님의 순서를 적절히 바꿔 강호가 받을 수 잇는 팁의 최댓값을 구하는 문제 N은 100,000보다 작거나 같은 자연수이다. 팁은 100,000보다 작거나 같은 자연수이다. 정렬 유형의 문제 🖥 소스 코드 from sys import stdin res, n = 0, int(stdin.readline()) arr..
-
[백준] 12788 제 2회 IUPC는 잘 개최될 수 있을까? with PythonPS 2022. 3. 16. 18:16
📌 BOJ 12788 제 2회 IUPC는 잘 개최될 수 있을까? 💡 조건 대회 개최를 위한 예산을 아끼기 위하여 펜을 구매하지 않고 CTP회원들에게 펜을 빌리기로 하였다. CTP에는 N명의 회원들이 존재하며 각각의 회원들의 필통에 들어있는 펜의 개수는 모두 다르다. 정은이는 여러명의 회원에게 펜을 빌릴경우 펜을 돌려주기에 번거롭다고 생각하여 최소한의 회원들에게 펜을 빌려 참가자들에게 나누어 주려고 한다. 대회에 참가하는 참가자들은 팀을 구성해서 참가하는데 모든 팀원에게 펜을 지급해야한다. 한 팀이 k명의 팀원으로 구성되어 있을때 몇 명의 회원들에게 펜을 빌려야하는지 출력하는 문제. CTP의 회원수 N(1 ≤ N ≤ 1,000) 대회에 참가한 팀의 수 M(1 ≤ M ≤ 1,000) 팀을 구성하는데 필요한 ..
-
[백준] 11899 괄호 끼워넣기 with PythonPS 2022. 3. 16. 18:06
📌 BOJ 11899 괄호 끼워넣기 💡 조건 올바르지 않은 괄호열이 주어질 때, 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 구하는 문제. S의 길이는 1 이상 50 이하이며 불가능한 경우는 주어지지 않는다. 괄호열이란 여는 괄호 ‘(’와 닫는 괄호 ‘)’로만 구성된 문자열을 말합니다. 올바른 괄호열은 아래와 같이 정의할 수 있다. "()"는 올바른 괄호열입니다. A가 올바른 괄호열이라면 "(A)" 역시 올바른 괄호열입니다. A와 B가 모두 올바른 괄호열이라면 "AB" 역시 올바른 괄호열입니다. 문자열, 스택, 자료구조 유형의 문제 🖥 소스 코드 from sys import stdin g = stdin.readline().rstrip() cnt = 0 def solve(s): ..