BOJ
-
[백준] 3184 양 with PythonPS 2021. 10. 19. 22:21
📌 BOJ 3184 양 💡 조건 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다. 한 칸에서 수평, 수직만으로 이동할수 있다. 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대가 많으면 양은 사라진다. 넓이 우선 탐색(BFS) 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque n, m = map(int, stdin.re..
-
[백준] 2343 기타 레슨 with PythonPS 2021. 10. 19. 21:52
📌 BOJ 2343 기타 레슨 💡 조건 강의의 수 N (1 ≤ N ≤ 100,000) 블루레이의 수 M (1 ≤ M ≤ N) 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 각 강의의 길이가 분 단위(자연수)로 주어진다. 가능한 블루레이의 크기 중 최소를 구하는 문제. 이분탐색 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) arr = list(map(int, stdin.readline().split())) def get_cnt(): count = 0 temp = 0 for i in range(n): if temp + arr[i] > mid: count += 1 temp = 0 temp += ar..
-
[백준] 1743 음식물 피하기 with PythonPS 2021. 10. 18. 20:41
📌 BOJ 1743 음식물 피하기 💡 조건 통로의 세로 길이 N(1 ≤ N ≤ 100) 통로의 가로 길이 M(1 ≤ M ≤ 100) 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M) K개의 줄에 음식물이 떨어진 좌표 (r, c) DFS 유형의 문제(깊이우선탐색) 🖥 소스 코드 from sys import stdin, setrecursionlimit setrecursionlimit(10 ** 9) n, m, k = map(int, stdin.readline().split()) arr = [[0] * (m + 1) for _ in range(n + 1)] food_t = [] for _ in range(k): x, y = map(int, stdin.readline().split()) arr[x][y] = 1 ..
-
[백준] 1713 후보 추천하기 with PythonPS 2021. 10. 18. 20:30
📌 BOJ 1713 후보 추천하기 💡 조건 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정 구현 & 시뮬레이션 유형의 문제 🖥 소스 코드 from sys import stdin import heapq def solution(n): student = {} data = list(map(int, stdin.readline().split())) for s in data: if s not in student: if len(student) >= n: # dict를 heapq 모듈을 사용해 최솟값을 뽑아냄 a = heapq.n..
-
[백준] 1244 스위치 켜고 끄기 with PythonPS 2021. 10. 17. 21:38
📌 BOJ 1244 스위치 켜고 끄기 💡 조건 및 풀이 첫째 줄은 스위치 개수. 스위치 개수는 100 이하인 양의 정수. 둘째 줄은 각 스위치의 상태. 켜져 있으면 1, 꺼져있으면 0이라고 표시 셋째 줄에는 학생 수. 학생수는 100 이하인 양의 정수 넷째 줄부터 마지막 줄까지 한 줄에 한 학생의 성별, 학생이 받은 수. 남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다. 즉, 스위치가 켜져 있으면 끄고, 꺼져 있으면 켠다. 여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다. 이때 구간에 속한 스위치 개수는 항상 홀수가 된다. 구현 & 시뮬레이션 유형의 문제..
-
[백준] 10775 공항 with PythonPS 2021. 10. 13. 23:23
📌 BOJ 10775 공항 💡 조건 및 풀이 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정. i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. Union - Find 알고리즘 유형의 문제 비행기를 최대 몇 대 도킹시킬 수 있는지 구하는 문제. 게이트의 수 G (1 ≤ G ≤ 105) 비행기의 수 P (1 ≤ P ≤ 105) P개의 줄에 gi (1 ≤ gi ≤ G) 🖥 소스 코드 from sys import stdin def find_parent(parent, x): if parent[x] !..
-
[백준] 2143 두 배열의 합 with PythonPS 2021. 10. 12. 00:00
📌 BOJ 2143 두 배열의 합 💡 조건 및 풀이 (-1,000,000,000 ≤ T ≤ 1,000,000,000) (1 ≤ n ≤ 1,000) (1 ≤ m ≤ 1,000) 누적합 유형의 문제 두 배열의 부분배열을 사용하여 합을 구해 T를 만들 수 있는 개수를 구한다. 🖥 소스 코드 from sys import stdin, setrecursionlimit setrecursionlimit(int(1e9)) t = int(stdin.readline()) n = int(stdin.readline()) A = list(map(int, stdin.readline().split())) m = int(stdin.readline()) B = list(map(int, stdin.readline().split())) A..
-
[백준] 1967 트리의 지름 with PythonPS 2021. 10. 11. 23:34
📌 BOJ 1967 트리의 지름 💡 조건 및 풀이 노드의 개수 (1 ≤ n ≤ 10,000) 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호 두 번째 정수는 자식 노드 세 번째 정수는 간선의 가중치 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. BFS 유형의 문제 루트 노드의 번호는 항상 1 간선의 가중치는 100보다 크지 않은 양의 정수 트리에 존재하는 모든 경로들 중, 가장 긴 경로를 출력하는 문제이다. 🖥 소스 코드 from sys import stdin from collections import deque n = int(stdin.readline()) tree = [[] for _ in range(n + 1)]..
-
[백준] 1799 비숍 with PythonPS 2021. 10. 11. 21:44
📌 BOJ 1799 비숍 💡 조건 및 풀이 체스판의 크기는 10 이하의 자연수 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0 대각선 방향으로 움직이는 비숍이 이동할 수 있는 경로에 비숍을 놓을 수 없다. 백트래킹 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) chess_map = [] black = [] white = [] color = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): color[i][j] = (i % 2 == 0 and j % 2 == 0) or (i % 2 != 0 and j % 2 != 0) for i in range(n): ch..
-
[백준] 6987 월드컵 with PythonPS 2021. 9. 22. 23:14
📌 BOJ 6987 월드컵 💡 조건 및 풀이 6개의 국가가 있고, 총 18번의 경기를 한다. 승, 무, 패의 결과가 있으며, 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0 백트래킹 유형의 문제 입력은 네 줄로 들어오며, 각 줄에 대해 가능한 결과 1, 불가능한 결과 0 을출력하는 문제이다 🖥 소스 코드 from sys import stdin from itertools import combinations as cb def solution(round): global ans if round == 15: ans = 1 for sub in res: if sub.count(0) != 3: ans = 0 break return t1, t2 = game[round] for x, y in ((0, 2), (1..