자료구조
-
[백준] 9081 단어 맞추기 with PythonPS 2022. 3. 9. 01:10
📌 BOJ 9081 단어 맞추기 💡 조건 단어를 주면 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하는 문제 케이스의 개수 T (1 ≤ T ≤ 10) 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알파벳으로 이루어진다. 단어의 길이는 100을 넘지 않는다. 구현 유형의 문제 🖥 소스 코드 from sys import stdin for t in range(int(stdin.readline())): string = list(stdin.readline().rstrip()) length = len(string) i, j = 0, 1 for idx in range(1, length): if string[id..
-
[백준] 4811 알약 with PythonPS 2022. 3. 9. 01:02
📌 BOJ 4811 알약 💡 조건 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까? 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 ..
-
[백준] 1822 차집합 with PythonPS 2022. 3. 6. 21:43
📌 BOJ 1822 차집합 💡 조건 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하는 문제. 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다. 지료구조 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) a = set(map(int, stdin.readline().s..
-
[백준] 1788 피보나치수의 확장 with PythonPS 2022. 3. 6. 21:35
📌 BOJ 1788 피보나치수의 확장 💡 조건 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다. n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하는 프로그램. n은 음수로 주어질 수도 있다. n은 절댓값이 1,000,000을 넘지 않는 정수이다. 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. 다이나믹프로그래밍 유형..
-
[백준] 1660 캡틴 이다솜 with PythonPS 2022. 3. 6. 01:17
📌 BOJ 1660 캡틴 이다솜 💡 조건 N은 300,000보다 작거나 같은 자연수이다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다. N개의 대포알로 만들 수 있는 사면체의 최소 개수를 출력하는 프로그램을 작성하는 문제 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) arr = [] num = 0 i = 1 while n > num: num += (i * (i + 1)) // 2 arr.append(num) i += 1 dp = [int(1e9) for i in range(n + 1)] for i ..
-
[백준] 1755 숫자놀이 with PythonPS 2022. 3. 6. 00:49
📌 BOJ 1755 숫자놀이 💡 조건 79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 먼저 온다. 문제는 정수 M, N(1 ≤ M ≤ N ≤ 99)이 주어지면 M 이상 N 이하의 정수를 숫자 하나씩 읽었을 때를 기준으로 사전순으로 정렬하여 출력하는 것. M 이상 N 이하의 정수를 문제 조건에 맞게 정렬하여 한 줄에 10개씩 출력한다. 정렬 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) arr = [] num = 0 i = 1 while n ..
-
[백준] 16935 배열 돌리기 3 with PythonPS 2022. 3. 4. 21:40
📌 BOJ 16935 배열 돌리기 3 💡 조건 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 1번 연산은 배열을 상하 반전시키는 연산이다. 2번 연산은 배열을 좌우 반전시키는 연산이다. 3번 연산은 오른쪽으로 90도 회전시키는 연산이다. 4번 연산은 왼쪽으로 90도 회전시키는 연산이다. 5, 6번은 문제 참고 첫째 줄에 배열의 크기 N, M과 수행해야 하는 연산의 수 R이 주어진다. 2 ≤ N, M ≤ 100, N, M은 짝수 1 ≤ R ≤ 1,000 둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다. 1 ≤ Aij ≤ 108 연산은 공백으로 구분되어져 있고, 문제에서 설명한 연산 번호이며, 순서대로 적용시켜야 한다. 구현 유형의 문제 🖥 소스 코드 from sys im..
-
[백준] 15965 K번째 소수 with PythonPS 2022. 3. 4. 21:29
📌 BOJ 15965 K번째 소수 💡 조건 서브태스크가 존재한다. 2 이상의 자연수 N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때 소수라고 한다. 자연수 K가 주어진다.(1 ≤ K ≤ 500,000) k번째 소수를 구하는 문제 수학, 에라토스테네스의 체 유형의 문제 🖥 소스 코드 BIG_NUM = 10**7 k = int(input()) array = [1 for _ in range(BIG_NUM + 1)] answer = [] for i in range(2, BIG_NUM + 1): if array[i]: answer.append(i) for j in range(i+i, BIG_NUM + 1, i): array[j] = 0 print(answer[k - 1]) 🔖 예제 및 실행결과 ..
-
[백준] 10384 팬그램 with PythonPS 2022. 3. 3. 19:20
📌 BOJ 10384 팬그램 💡 조건 팬그램은 모든 알파벳을 적어도 한 번씩을 사용한 영어 문장을 말한다. 더블 팬그램은 모든 알파벳을 적어도 두 번씩은 사용한 문장을 말하고, 트리플 팬그램은 모든 알파벳을 적어도 세 번씩은 사용한 문장을 말한다. 입력은 여러 줄의 테스트케이스들로 이루어진다. 첫째 줄에 테스트케이스의 수 n이 주어진다. 각 테스트케이스는 영어 소문자와 대문자, 특수기호들로 이루어진다. 팬그램이 아닐 경우 - Not a pangram 팬그램일 경우 - Pangram! 더블 팬그램일 경우 - Double pangram!! 트리플 팬그램일 경우 - Triple pangram!!! 구현 유형의 문제 🖥 소스 코드 from sys import stdin for i in range(1, int(s..
-
[백준] 9742 순열 with PythonPS 2022. 3. 3. 19:08
📌 BOJ 9742 순열 💡 조건 집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 서로 다른 숫자와 문자로 이루어진 집합과 위치가 주어졌을 때, 그 집합의 순열 중 주어진 위치의 순열을 구하는 프로그램을 작성하는 문제 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어지며, 이 값은 3,628,800보다 작거나 같은 자연수이다. 백트래킹 유형의 문제 🖥 소스 코드 from sys import stdin from math import factorial def solve(string..