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

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

[큐, 시뮬레이션] 백준 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 방.. 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 = (.. 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.. 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: 원의 왼쪽 좌표.. 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.

티스토리툴바