본문 바로가기
  • 초부득3 - 어제보다 나은 내일을 위해
  • 꿈이 현실이 되는 날까지

전체 글195

[스택] 백준 10000번 원 영역 with Python3 ★★ https://www.acmicpc.net/problem/10000 10000번: 원 영역 x축 위에 원이 N개 있다. 원은 서로 교차하지 않는다. 하지만, 접할 수는 있다. 원으로 만들어지는 영역이 몇 개인지 구하는 프로그램을 작성하시오. 영역은 점의 집합으로 모든 두 점은 원을 교 www.acmicpc.net 문제 정답 풀이 import sys N = int(sys.stdin.readline()) points = [] for _ in range(N): x, r = list(map(int, sys.stdin.readline().split())) # x 원의 중심 좌표, r: 원의 반지름 points.append(["{", x-r, 0, 0]) # 1: 원의 왼쪽을 표시하는 괄호 # 2: 원의 왼쪽 좌표.. 2021. 8. 14.
[스택] 백준 2493번 탑 with Python3 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 내 풀이 -시간 초과- import sys from collections import deque n = int(sys.stdin.readline()) stack = deque([]) ans = [] stack = deque(map(int, sys.stdin.readline().split())) for i in range(1, n+1): teststack = deque(stack) for _.. 2021. 8. 14.
[스택] 백준 9012번 괄호 with Python3 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 내 풀이 import sys from collections import deque input = sys.stdin.readline #뒤에서부터 탐색해서, )는 +1, (는 -1을 통해 검사하는 함수 def countthat(a): global check if check < 0: print("NO") return if not a and check == 0: pri.. 2021. 8. 13.
[이분탐색] 백준 2470번 두 용액 with Python3 ★★ https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 정답 풀이 import sys input = sys.stdin.readline N = int(input()) liquid = [int(x) for x in input().split()] liquid.sort() #이분 탐색을 위해 정렬해준다. left = 0 right = N - 1 answer = liquid[left] + liquid[right] #결국 .. 2021. 8. 13.
[이분탐색] 백준 2110번 공유기 설치 with Python3 ★★ 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 문제 정답 풀이 import sys n,c = map(int,input().split()) house = [] for _ in range(n): x = int(sys.stdin.readline()) house.append(x) house.sort() # 공유기 거리의 최소값 start = 1 # 공유기간의 가능한 최대 거리 = 가장 높은 거리와 .. 2021. 8. 13.
[이분탐색] 백준 2805번 나무 자르기 with Python3 ★★ https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 정답 풀이 N, M = map(int, input().split()) tree = list(map(int, input().split())) start, end = 1, max(tree) #이분탐색 검색 범위 설정 while start = mid: log += i - mid #i높이 이상의 나무들을 모두 잘라서 log값에 더해주는 과정 #벌목 높이를 이분.. 2021. 8. 13.
[이분탐색] 백준 1920번 수 찾기 with Python3 ★ https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 내 풀이 from typing import Any, Sequence def bin_search(a: Sequence, key: Any) -> int: pl = 0 pr = len(a) - 1 while True: pc = (pl + pr)//2 if a[pc] == key: return 1 elif a[pc] < key: pl = pc+1 el.. 2021. 8. 13.
[분할 정복] 백준 2630번 색종이 만들기 with Python3 ★★ https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 정답 풀이 #쿼드 트리 함수 정의 def quad_tree(x, y, n): global matrix, blue, white #주어진 배열과 색 카운트 끌어오기 color = matrix[y][x] #첫 색깔과 나머지 색이 같아야함 double_break = False #for문 탈출용 double_break for i in range(x, x+n): if doub.. 2021. 8. 13.
[큐] 백준 11866번 요세푸스 문제0 with Python3 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 내 풀이 -index 값 이동 n, step = map(int, input().split()) indexstep = step - 1 inistep = step numlist = list(range(1, n+1)) ans = [] while True: #인덱스 자체가 같은 간격으로 이동하게 구현했다. #번외로, step 번 째에 해당하지 않는 것들은 popleft, 후 맨뒤에 append하는 #deque 활용을 했더라면 더욱 깔끔한 코드였을것 같다. if len(numlist).. 2021. 8. 13.

티스토리툴바