본문 바로가기

Algorithm

(6)

백준 (BOJ) - 17219 비밀번호 찾기 [Python] 백준을 안 푼지 너무 오래 됐다 다시 깃헙에 잔디 심기 Start 대충 풀 바엔 그냥 풀지말고 그 날은 쉬자 파이팅 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net # 20231230 다시 풀기 import sys input = sys.stdin.readline Arr1 = [] Arr2 = [] N, M = map(int, input().split()) for i in range(N): Arr1.append(li..

백준 (BOJ) - 1260 DFS와 BFS [Python] https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 오늘부터 BFS랑 DFS만 뒤지게 풀어볼 예정이라 본격적으로 들어가기 전 개념정리 느낌으로 가장 기본 문제를 풀이 해보았다. 우선 DFS는 깊이 우선 탐색이고 stack을 사용하는 알고리즘이며, BFS는 너비 우선 탐색이고 queue (보통 O(n)의 시간 복잡도를 갖는 deque)를 사용한다. 우선 input으로 정점 개수, 간선 개수, 시작 노드를 받아주고..

백준 (BOJ) - 1764 듣보잡 [Python] https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 실버4의 매우 간단한 문제지만 List 두 개를 만들어서 for i in List1: if i in List2: newList.append(i) 이런 방식으로 시간 복잡도를 개 무시한(?) 코드를 짜버린 나머지 시간 초과가 떴다. 푸는 방법은 정말 간단하다. 문제가 원하는 답안이 A집합과 B, 두 집합의 교집합임으로 그 것만 구해주면 된다. import sys N, M = map(int, sys..

백준 (BOJ) - 1541 잃어버린 괄호 [Python] https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이 문제의 핵심은 1. -를 기준으로 식을 모두 나눈 뒤 55-50+40을 나누면 "50" 과 "55+40" 나눠짐. 2. 나머지 덧셈으로 이루어진 문자열을 계산하고 50 95 3. - 계산을 모두 해주면 됨 50 - 95 = -35 이런식으로 계산하면 55 - (50+40)과 같은 계산 결과가 나옴 코드 진행에서 살짝 헷갈리는 부분은 바로 string으로 들어오는 input에서 사칙연산 부..

백준 (BOJ) - 2110 공유기 설치 [Python] https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이 문제의 중요한 포인트는 역시 공유기 설치하는 거리를 start와 end로 놓는 것이다. 공유기를 설치하는 후보 집과 집 사이의 최소 거리를 start라고 놓고 (최소 길이는 바로 옆에 있는 경우니까 10 최대 거리를 end라고 놓는다 (최대 길이는 첫번째 집 to 마지막집 거리) 처음에 start를 arr[0], end를 arr[-1]이런 식..

백준 (BOJ) - 1931 회의실 배정 [Python] https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이번 문제의 핵심은 어떻게 해야 가장 많은 개수의 회의를 넣을 수 있는지 아는 것이다. 나는 1. 일찍 끝나는 회의부터, 2. 종료 시간이 같다면 나중에 시작하는 회의 순으로 정렬시켰다. 코드 n = int(input()) s = [] for i in range(n): first, second = map(int, input().split()) s.append([first, second]) s = sorted(s, key=lambda a: a[0]) s = sorted(s, key=lambda a: a[1]) la..

이전 1 다음

티스토리툴바