자료구조
-
[백준] 9372 상근이의 여행 with PythonPS 2022. 2. 22. 20:17
📌 BOJ 9372 상근이의 여행 💡 조건 N개국을 여행할 상근이에게 가장 적은 비행기를 타고 여행할 수 있게 도와주자. 테스트 케이스의 수 T(T ≤ 100) 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다. 이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b) 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다. 그래프이론, 유니온-파인드 유형의 문제 🖥 소스 코드 from sys import stdin def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, paren..
-
[백준] 2628 종이 자르기 with PythonPS 2022. 2. 22. 20:01
📌 BOJ 2628 종이 자르기 💡 조건 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램 정렬 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin..
-
[백준] 2168 터널 위의 대각선 with PythonPS 2022. 2. 21. 17:23
📌 BOJ 2168 터널 위의 대각선 💡 조건 한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다. x와 y는 정수이다. 직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다. x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 문제. x와 y는 1,000,000,000 이하의 자연수 수학, 정수론, 유클리드 호제법유형의 문제 🖥 소스 코드 from sys import stdin from math import gcd x, y = map(int, stdin.readline().split()) print(x + y - gcd(x, y))🔖 예제 및 실행결과 예제 ..
-
[백준] 2075 N번째 큰 수 with PythonPS 2022. 2. 21. 17:05
📌 BOJ 2075 N번째 큰 수 💡 조건 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 표에 채워진 수는 모두 다르다. N(1 ≤ N ≤ 1,500) 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. 자료구조 응용, 우선순위 큐 활용, 정렬 유형의 문제 🖥 소스 코드 from sys import stdin import heapq n = int(stdin.readline()) q = [] cnt = 0 for _ in range(n): data = list(map(int, stdin.readline().split())) for j in data: if cnt != n: heapq.heap..
-
[백준] 15970 화살표 그리기 with PythonPS 2022. 2. 20. 23:01
📌 BOJ 15970 화살표 그리기 💡 조건 부분 점수가 있는 문제. 점들의 개수를 나타내는 정수 N N개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x와 y가 주어진다. 모든 점에서 시작하는 화살표들의 길이 합을 출력하는 문제. 각 점은 N개의 색깔 중 하나를 가진다. 각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다. 여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다. 브루트포스유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) arr = [] for _ in range(n): x, y = m..
-
[백준] 13565 침투 with PythonPS 2022. 2. 19. 18:10
📌 BOJ 13565 침투 💡 조건 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다. 맨 윗줄에서 받은 전기가 맨 밑 줄까지 갈 수 있다면 True, 아니면 False BFS 유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque n, m = map(int, stdin.readline().split()) board = [] visited = set() for _ in range(n): board.append(list(map(int, list(stdin.readl..
-
[백준] 11048 이동하기 with PythonPS 2022. 2. 19. 17:59
📌 BOJ 11048 이동하기 💡 조건 N×M 크기의 미로 (1 ≤ N, M ≤ 1,000) (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동가능. 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하는 문제 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다. 다이나믹프로그래밍 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) arr = [] candy = [[0] * m for _ in range(n)] res = 0 for _ in ..
-
[백준] 2477 참외밭 with PythonPS 2022. 2. 14. 18:20
📌 BOJ 2477 참외밭 💡 조건 m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20) 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이 (1 이상 500 이하의 정수) 변의 방향에서 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 구현 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) nums = [] x, y = [], [] for _ in range(6): direction, length = map(int, stdin.rea..
-
[백준] 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 with PythonPS 2022. 2. 13. 23:35
📌 BOJ 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 💡 조건 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 정수 N과 M이 주어진다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000) N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 같은 조합은 두 번 이상 나오지 않는다. 브루트포스 알고리즘, 그래프 이론유형의 문제 🖥 소스 코드 from sys import stdin from itertools import combinations n, m = map(int, stdin.readline().split()) ice_cream = set(x for x..