티스토리

초부득3
검색하기

블로그 홈

초부득3

bdbest.tistory.com/m

/*re*/ zero 부터 시작하는 코딩 생활

구독자
2
방명록 방문하기
공지 Copyrights / illustr⋯ 모두보기

주요 글 목록

  • [스택] 백준 10799번 쇠막대기 with Python3 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 내 풀이 import sys from collections import deque #입력 input = sys.stdin.readline str = input().rstrip() #자료형 stack = deque([]) result = list() #인덱스 대체제 count = 0 #들어갔다 나갔다하는 stack 활용 for i in str: if i == ")": top = stack.pop() if.. 공감수 0 댓글수 0 2021. 8. 19.
  • [우선순위 큐, 힙] 백준 1658번 가운데를 말해요 with Python3 ★ https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 정답 풀이 import heapq import sys # 중앙값 기준으로 작은 값 = left, 큰 값 = right left, right = [], [] n = int(sys.stdin.readline()) for _ in range(n): num = int(sys.stdin.readline()) # 최소 힙과 최대 힙에 원소를 번갈아가며 push/ left부터이긴함 if .. 공감수 0 댓글수 0 2021. 8. 17.
  • [우선순위큐]백준 13334번 철로 with Python3 ★ https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 문제 정답 풀이 import sys import heapq n = int(sys.stdin.readline()) road_info = [] for _ in range(n): road = list(map(int, sys.stdin.readline().split())) road_info.append(road) d = int(sys.stdin.read.. 공감수 0 댓글수 0 2021. 8. 17.
  • [이분탐색] 백준 8983번 사냥꾼 with Python3 ★ https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 문제 내 풀이 import sys input = sys.stdin.readline m, n, l = map(int, input().split()) shootpos = list(map(int, input().split())) shootpos.sort() # 동물을 기준으로 자신을 죽일 수 있는 사대가 있는지를 이분 탐색했다. # 있을 경우 c.. 공감수 0 댓글수 0 2021. 8. 17.
  • [스택] 백준 2812번 크게 만들기 with Python3 더보기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 내 풀이 -실패 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) str = list(input().rstrip()) stack = list() print(str) for i in range(n-1, 0, -1): if len(stack) == n-m: if int(str[i]) > int(stack[0]): stack.popleft.. 공감수 0 댓글수 0 2021. 8. 16.
  • [스택] 백준 2504번 괄호의 값 with Python3 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 문제 정답 풀이 import sys str = sys.stdin.readline().rstrip() stack = list() for i in str: if i == ")": temp = 0 while stack: # stack에 element가 있다면 top = stack.pop() if top == "(": if temp == 0: stack.append(2) else: stack.appen.. 공감수 0 댓글수 0 2021. 8. 16.
  • [분할정복] 백준 10830번 행렬 제곱 with Python3 ★★ https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 내 풀이 n, b = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(n)] print(matrix) answer = [] for i in range(n): answer.append([1] * n) print(answer) sum = 0 for _ in range(b): for i in range(n): f.. 공감수 0 댓글수 0 2021. 8. 16.
  • [이분탐색] 백준 11053번 가장 긴 증가하는 부분 수열 with Python3 ★ https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 내 풀이 import bisect # 입력 n = int(input()) # 순열의 길이 numlist = list(map(int, input().split())) # 첫 순열 answer = [] for i in range(len(numlist)): # 주어진 순열을 처음부터 끝까지 탐색해가며 print(f'여기.. 공감수 0 댓글수 0 2021. 8. 16.
  • [우선순위 큐, 힙] 백준 1715번 카드 정렬하기 with Python3 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 내 풀이 import sys import heapq n = int(sys.stdin.readline()) heap = [] for i in range(n): heapq.heappush(heap, int(sys.stdin.readline())) if len(heap) == 1: # 1개일 경우 비교하지 않아도 됌 print(0) else: answer = 0 while len(h.. 공감수 0 댓글수 0 2021. 8. 16.
  • [큐, 시뮬레이션] 백준 3190번 뱀 with Python3 ★ https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 정답 풀이 from collections import deque def change(d, c): # d는 현재 direction 값, c는 현재 시간에 맞는 방향전환 지시 # 상(0) 우(1) 하(2) 좌(3) # 동쪽 회전: 상(0) -> 우(1) -> 하(2) -> 좌(3) -> 상(0) : +1 방향 # 왼쪽 회전: 상(0) -> 좌(3) -> 하(2) -> 우(1) -> 상(0) : -1 방.. 공감수 0 댓글수 0 2021. 8. 16.
  • [분할정복, 스택] 백준 6549번 히스토그램에서 가장 큰 직사각형 with Python3 ★★★ https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 각 정답자의 포스트에 잘 설명되어있다. 하지만 정말 답안이 어질어질하다... 정답 풀이 -분할정복- import sys # l = 직사각형 리스트의 제일 왼쪽, R= 제일 오른쪽 def max_square(l, r): # 리스트 h 길이가 1일 경우 그 길이를 바로 리턴 if l == r: return h[l] else: mid = (.. 공감수 0 댓글수 0 2021. 8. 14.
  • [분할정복] 백준 1629번 곱셈 with Python3 ★★ https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 정답 풀이 a, b, c = map(int, input().split()) ## a^b%c를 반환하는 함수 def solution(a, b): # 어떤 수든 재귀를 타면 b==1이 되게 된다. if b==1: return a%c ans = solution(a, b // 2) # 지수승 절반값의 %c한 값 호출 if b%2==0: # 짝수 return ans*ans%c else: # 홀수 return ans*ans*(a%c)%c # 공식상으로는 ans*ans*(a.. 공감수 0 댓글수 0 2021. 8. 14.
  • [스택] 백준 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: 원의 왼쪽 좌표.. 공감수 0 댓글수 0 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 _.. 공감수 0 댓글수 0 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.. 공감수 0 댓글수 0 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] #결국 .. 공감수 0 댓글수 0 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 # 공유기간의 가능한 최대 거리 = 가장 높은 거리와 .. 공감수 0 댓글수 0 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값에 더해주는 과정 #벌목 높이를 이분.. 공감수 0 댓글수 0 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.. 공감수 0 댓글수 0 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.. 공감수 0 댓글수 0 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).. 공감수 0 댓글수 0 2021. 8. 13.
  • [큐] 백준 2164번 카드2 with Python3 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 내 풀이 from collections import deque n = int(input()) Q = deque(range(1, n+1)) if len(Q) == 1: print(Q[0]) else: for i in range(len(Q)): Q.popleft() Q.append(Q.popleft()) if len(Q) == 1: break print(Q[0]) 해설 찬양하라 deque 단순히.. 공감수 0 댓글수 0 2021. 8. 13.
  • [큐] 백준18258번 큐 2 with Python3 https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 내 풀이 import sys n = int(sys.stdin.readline()) Q = [] for i in range(n): cmd = [] cmd = list(sys.stdin.readline().split()) if len(cmd) > 1: order = cmd[0] num = cmd[1] else: order = cmd[0] if order == 'push'.. 공감수 0 댓글수 0 2021. 8. 13.
  • [스택] 백준 17608번 막대기 with Python3 https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 문제 내 풀이 import sys n = int(sys.stdin.readline()) stack = [] #막대기들을 순서대로 담을 스택/리스트 for _ in range(n): stack.append(int(sys.stdin.readline())) rightstart = int(stack[-1]) #제일 앞에 바라보이는 막대기의 높이 top = int(max(stack)) #가장 긴 막대기. 이 뒤.. 공감수 0 댓글수 0 2021. 8. 13.
  • [스택] 백준 10773번 제로 with Python3 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 내 풀이 import sys input = sys.stdin.readline n = int(input()) stack = [] for _ in range(n): call = int(input()) if call != 0: stack.append(call) else: stack.pop() print(sum(stack)) 해설 기본적인 파이썬 리스트 기능으로 s.. 공감수 0 댓글수 0 2021. 8. 13.
  • [스택] 백준 10828번 스택 with Python3 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 내 풀이 import sys n = int(sys.stdin.readline()) stack = [] for i in range(n): cmd = [] cmd = list(sys.stdin.readline().split()) if len(cmd) > 1: order = cmd[0] num = cmd[1] else: order = cmd[0] if order == 'push'.. 공감수 1 댓글수 0 2021. 8. 13.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.