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

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

[이분탐색] 백준 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.
[큐] 백준 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 단순히.. 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'.. 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)) #가장 긴 막대기. 이 뒤.. 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.. 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'.. 2021. 8. 13.

티스토리툴바