썸네일 [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에 수열에 들어갈 수 있는 최댓값인 ..
썸네일 [BOJ] #18405 경쟁적 전염 (Python) 🌱 문제 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 🌱 풀이 0. 입력 받기 n, k = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input().split()))) s, x, y = map(int, input().split()) 첫째줄에 시험관의 크기(n)와 바이러스의 종류의 개수(k)를 입력받습니다. 다음 n개에 줄에 시험관의 정보를 입력받습니다. 마지막 줄에 시간(s..
썸네일 [BOJ] #2230 수 고르기 (Python) 🌱 문제 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 🌱 풀이 투 포인터 알고리즘을 이용해서 푸는 문제입니다. 핵심 아이디어는 두 포인터가 가리키는 값이 m이상일 때, result를 업데이트해 나가는 것입니다. 그리고 업데이트와 동시에 왼쪽 포인터를 하나 증가시킵니다. 차이가 더 줄여질 수 있는지 확인하기 위해서입니다. 두 포인터가 가리키는 값이 m미만이라면 오른쪽 포인터를 하나 증가시켜, 차이를 키워줍니다. 🌱 코드 # !/usr/bin/env python # -*- coding: u..
썸네일 [BOJ] #9935 문자열 폭발 (Python) 🌱 문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🌱 풀이 1. 입력 받기 str = deque(list((input().strip()))) bomb = list(input().strip()) 전체 문자열과 폭발 문자열을 입력으로 받습니다. 빠른 pop연산을 위해서 전체 문자열은 queue로 바꿔줍니다. 2. 변수 초기화 stack = [] stack은 결과값을 저장할 변수입니다. 3. 스택과 큐 사용 while str: ch = str.popleft() stack.append(ch) i..
라이브러리 브랜드 그룹 | hellomygreenworld

티스토리툴바