썸네일 [BOJ] #2531 회전초밥 (Python, Sliding window, 시간초과 해결) 🌱 문제https://www.acmicpc.net/problem/2531 🌱 풀이0. 입력받기input = sys.stdin.readlinen, d, k, c = map(int, input().split())belt = []for _ in range(n): belt.append(int(input())) *처음 생각했던 방법 (시간 초과 발생)최대 접시 수는 30,000개이니까 브루트 포스로 충분히 가능하다고 생각했습니다. 리스트를 돌면서 초밥의 종류만 세주면 되네!하고 아래와 같이 코드를 짰는데 시간초과가 발생하였습니다.answer = 0for i in range(n): belt.append(belt.popleft()) answer = max(len(set(list(belt)[:k] ..
썸네일 [BOJ] #10830 행렬 제곱 (Python, 분할정복) 🌱 문제  🌱 풀이이 문제의 관건은 100,000,000,000까지 가질 수 있는 매우 큰 지수를 효율적으로 처리하는 것입니다. 행렬을 반복적으로 곱하는 대신, 행렬의 거듭제곱을 분할 정복(Divide and Conquer) 기법으로 계산합니다. 1) 입력 받기N, B = map(int, input().split())matrix = []for _ in range(N): matrix.append(list(map(int, input().split()))) 2) 행렬 제곱을 구하는 함수(Divide and Conquer)def pow_matrix(matrix, B): """ 행렬 matrix를 B 제곱하는 함수 """ if B == 1: return [[element..
썸네일 [BOJ] #5430 AC (Python, Deque, 시간 초과 해결) 🌱 문제https://www.acmicpc.net/problem/5430 🌱 풀이1. 입력 받기T = int(input())for _ in range(T): p = input() p.replace("RR", "") p = list(p) n = int(input()) array = deque(eval(input()))테스트 케이스 개수인 T를 int로 받아서 해당 개수만큼 반복문을 들어갑니다.수행해야할 함수 p는 우선 string으로 받습니다. 이때, RR은 뒤집고 바로 뒤집기 때문에 배열에 아무런 변화를 주지 않으므로 replace()함수로 바로 지웠습니다. 그리고나서 string을 list로 바꾸어 이후에 반복문을 수행하며 함수 하나하나를 탐색할 수 있도록 하였습니다. 가..
썸네일 [BOJ] #2437 저울 (Python, Greedy) 🌱 문제 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 🌱 풀이 0. 접근하기 문제 예시에서 추가 1, 1, 2, 3, 6, 7, 30일 때, 정답이 21입니다. 이를 추의 배열이 [1, 1, 2, 3, 6, 7, 30]일 때 앞에서부터 차례대로 더한 값의 배열은 [1, 2, 4, 7, 13, 20, 50]입니다. 정답이 21임을 아는 상태에서는 1-20까지의 무게는 무조건 만들 수 있다고 판단할 수 있습니다. 이 때 1부터 20까지는 무조건 만들 수 있으므로 31부터 50까지도 무조건 만들 수 있음을 알 수 있습니다..
썸네일 [BOJ] #11000 강의실 배정 (Python, 우선순위 큐, 그리디) 🌱 문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 🌱 풀이 우선순위 큐 자료구조를 활용하여 푸는 그리디 문제입니다. 1. 시작 시간을 기준으로 정렬하기 class_times = [list(map(int, input().split())) for _ in range(n)] class_times.sort(key = lambda x: x[0]) 우선 순위 큐에 삽입 하기 이전에 우선, 입력 받은 강의 시간을 시작 시간을 기준으로 오름차순으로 정렬해야 합니다. 그 이유는 아래 예시를 통해서 설명하도록 하겠습니다. 아래에서 정렬 없이 큐에 삽입한 경우, 첫 번째..
썸네일 [BOJ] #16724 피리 부는 사나이 🌱 문제 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 🌱 풀이 0. 기본 로직 safe_zone = [] idx = 1 for i in range(n): for j in range(m): if visited[i][j] == False: dfs(board, i, j, visited) idx += 1 방문하지 않은 노드를 돌면서 dfs 탐색을 합니다. dfs 함수에서 무조건 하나의 사이클이 찾아지므로 dfs함수를 수행하고 나오면 idx 값을 증가시킵니다. 1. dfs 함수 d..
썸네일 [BOJ] #1027 고층 건물(Bruteforce, Python) 🌱 문제 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 🌱 풀이 1. 기울기 계산 def calc_gradient(x1, y1, x2, y2): if x1 == x2: return 0 gradient = (y2 - y1) / (x2 - x1) return gradient 건물이 보이는지 여부는 기울기에 따라 결정되므로 기울기를 계산하는 함수를 작성합니다. 1. 완전탐색 (Bruteforce) results = [] for idx in range(len(buildings)): cnt = 0 min_gradie..
썸네일 [BOJ] #1450 냅색문제 (이분 탐색, Python) 🌱 문제 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 🌱 풀이 1. 기존 Bruteforce로 풀 수 없는 이유 이 문제는 물건의 개수(n)가 최대 30개 주어집니다. 만약 이 문제를 완전 탐색으로 푼다면 물건 하나하나마다 넣을지 안넣을지 모든 경우를 세면 최대 $2^{30}$번의 연산을 하게 되는데, 이는 10억이 넘는 값으로 무조건 시간 초과가 발생합니다. 기존 Bruteforce로 푼다면 코드가 다음과 같을 것입니다. import sys from itertools import combinations ..
썸네일 [BOJ] #2110 공유기 설치 (이분탐색, Python) 🌱 문제 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 🌱 풀이 이 문제는 이분탐색 문제입니다. 이 문제에서는 집들 사이의 간격을 이분탐색하여 조정합니다. 아래에서 자세히 설명해보겠습니다. 0. 입력 받기 n, c = map(int, input().split()) position = [int(input()) for _ in range(n)] position.sort() 집의 개수 n과 공유기 개수 c를 입력 받습니다. 집의 위치를 리스트(position)에..
썸네일 [BOJ] #2252 줄 세우기 (Python) 🌱 문제 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 🌱 풀이 0. 입력 받기 n, m = map(int, input().split()) graph = [[] for _ in range(n + 1)] in_degree = defaultdict(int) for i in range(m): small, big = map(int, input().split()) graph[small].append(big) in_degree[big] += 1 학생수(n)과 키를 비교한 횟수..
썸네일 [BOJ] #1976 여행가자(Python) 🌱 문제 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 🌱 풀이 0. 입력 받기 및 변수 초기화 n = int(input()) m = int(input()) graph = [] parent = [i for i in range(n + 1)] for i in range(n): graph.append([idx + 1 for idx, i in enumerate(list(map(int, input().split()))) if i == 1]) plan = list(map(int, input().split())) 전체 ..
썸네일 [BOJ] #13144 List of Unique Numbers (Python) 🌱 문제 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 🌱 풀이 0. 입력 받기 n = int(input().rstrip()) num_list = list(map(int, input().split())) 수열의 길이와 수열의 원소 값들을 입력받습니다. 1. 변수 초기화 result = 0 start, end = 0, 0 seq = [False] * 1000001 투포인터를 이용해 풀기 위해 num_list의 인덱스를 가리킬 start와 end를 각각 0으로 초기화 해줍니다. seq에 수열에 들어갈 수 있는 최댓값인 ..
라이브러리 브랜드 그룹 | hellomygreenworld

티스토리툴바