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

sw사관학교 정글 2기/02 이분탐색, 분할정복, 스택, 큐, 우선순위 큐26

[스택] 백준 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.. 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 .. 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.. 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.. 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.. 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.. 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.. 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'여기.. 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.. 2021. 8. 16.

티스토리툴바