자료구조
-
[백준] 1759 암호 만들기 with PythonPS 2022. 2. 13. 23:18
📌 BOJ 1759 암호 만들기 💡 조건 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성. 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 문자들은 알파벳 소문자이며, 중복되는 것은 없다. 브루트포스, 백트래킹 유형의 문제 🖥 소스 코드 from sys import stdin from itertools import com..
-
[백준] 1236 성 지키기 with PythonPS 2022. 2. 10. 17:54
📌 BOJ 1236 성 지키기 💡 조건 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다. 성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 문제 0 m)만큼 순회하면서 row[i], col[j] 가 각각 False 일 경우 r1, r2 에 각각 + 1을 더해준다. r1, r2 중 가장 큰 값을 출력한다. 💾 느낀점 구현 문제이지만, 어디에 경비원이 있어야 각 열과 행이 모두 True 값을 가지는지 생각하는 것이 헷갈렸다. 브론즈라고 했지만, 구현은 역시 그 이상의 티어로 봐야하는 것 같다. 논리적인 사고력이 약하다는 것을 다시 ..
-
[백준] 14248 점프 점프 with PythonPS 2022. 2. 10. 17:37
📌 BOJ 14248 점프 점프 💡 조건 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 그 위치에서 점프할 수 있는 거리 Ai (1≤Ai≤100,000) 현재위치에서 다른 돌을 적절히 밟아 해당하는 위치로 이동이 가능하다고 할 때, 영우가 방문 가능한 돌들의 개수를 구하는 문제. 탐색 알고리즘유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque n = int(stdin.readline()) arr = [0] + list(map(int, stdin.readline().split())) graph = [[] for _ in range(n + 1)] s = int(stdin.readline()) for i in range(1, n +..
-
[백준] 11655 ROT13 with PythonPS 2022. 2. 10. 00:18
📌 BOJ 11655 ROT13 💡 조건 ROT13은 카이사르 암호의 일종으로 영어 알파벳을 13글자씩 밀어서 만든다. "Baekjoon Online Judge"를 ROT13으로 암호화하면 "Onrxwbba Bayvar Whqtr"가 된다. ROT13으로 암호화한 내용을 원래 내용으로 바꾸려면 암호화한 문자열을 다시 ROT13하면 된다. S를 ROT13으로 암호화한 내용을 출력하는 문제 구현, 문자열유형의 문제 🖥 소스 코드 from sys import stdin for i in list(stdin.readline().rstrip()): if i == ' ': print(' ', end='') elif i.isnumeric(): print(i, end='..
-
[백준] 6603 로또 with PythonPS 2022. 2. 10. 00:10
📌 BOJ 6603 로또 💡 조건 집합 S에서 K개의 숫자를 골라 뽑아 낼 수 있는 경우의 수를 모두 출력하는 문제 입력이 여러개 들어오며, 0이 들어왔을 때 종료 백트래킹, 재귀, 조합유형의 문제 🖥 소스 코드 from sys import stdin from itertools import combinations while 1: data = list(map(int, stdin.readline().split())) if len(data) == 1 and data[0] == 0: break else: a, arr = data[0], data[1:] res = [] for x in list(set(combinations(arr, 6))): if len(set(x)) == 6: temp = sorted(list..
-
[백준] 2535 아시아 정보올림피아드 with PythonPS 2022. 2. 8. 02:20
📌 BOJ 2535 아시아 정보올림피아드 💡 조건 대회참가 학생 수를 나타내는 N, 3 ≤ N ≤ 100. N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사이에 두고 주어진다. 국가 번호는 1부터 순서대로 하나의 정수로 주어지며, 각 학생번호는 각 나라별로 1부터 순서대로 하나의 정수로 주어진다. 점수는 0 이상 1000 이하의 정수이고, 동점자는 없다고 가정한다. 정렬, 구현유형의 문제. 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) grade = [] for i in range(n): a,b,c = map(int, stdin.readline().split()) grade.append((c, a, b)..
-
[백준] 1940 주몽 with PythonPS 2022. 2. 7. 22:35
📌 BOJ 1940 주몽 💡 조건 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 문제 정렬, 투 포인터 유형의 문제 🖥 소스 코드 from sys import stdin from bisect import bisect_left n = int(stdin.readline()) m = int(stdin.readline()) arr = sorted(list(map(int, stdin.readline().split()))) res = 0 visited = set() arr.sort() for i in arr: f = bis..
-
[백준] 1292 쉽게 푸는 문제 with PythonPS 2022. 2. 3. 20:07
📌 BOJ 1292 쉽게 푸는 문제 💡 조건 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 문제 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. 다이나믹 프로그래밍, 수학, 구현유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) arr = [0, 1] for i in range(2, m + 1): for j in range(i): arr.append(arr[-1] + i) print(arr[m] - arr[n - 1])🔖 ..
-
[백준] 16234 인구 이동 with PythonPS 2022. 2. 3. 19:45
📌 BOJ 16234 인구 이동 💡 조건 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100) 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 연합을 해체..
-
[백준] 15658 연산자 끼워넣기 (2) with PythonPS 2022. 2. 2. 17:56
📌 BOJ 15658 연산자 끼워넣기 (2) 💡 조건 N개의 수로 이루어진 수열 A1, A2, ..., AN N(2 ≤ N ≤ 11), (1 ≤ Ai ≤ 100) 입력 값중 셋째 줄에 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 나눗셈은 정수 나눗셈으로 몫만 취한다. 또한 음수를 나눌 때에는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾸어야 한다. 백트래킹, DFS 알고리즘 유형의 문제 🖥 소스 코드 from sys impo..