one Book a Day

KMP에서 실패함수를 만드는 느낌. 중복 매칭 알고리즘을 짠다. import sys input = sys.stdin.readline L = int(input()) # 광고판 길이 string = input().rstrip() # 광고판 문자열 string_length = len(string) # 실패함수 ( KMP 패턴 부분 일치 테이블 만들기) pattern_table = [0 for _ in range(string_length)] count = 0 for idx in range(1, string_length): while count > 0 and string[idx]!=string[count]: count = pattern_table[count-1] if string[idx]==string[count..

문제 이름만 봐도 바킹독님이 만드신 문제.. 구현문제로 자주나오는 유형. 삼성 기출의 연구소 같은 느낌으로 막아놓을 벽을 몇개 정하고 BFS로 막힌 영역을 세는 느낌. 연구소 시리즈를 풀며 연습할 필요성을 느꼈다. 벽을 고르는 조합도 comb를 쓰지않고 함수를 구현하는 방법도 고려할 수 있다. import sys input = sys.stdin.readline from collections import deque from itertools import combinations def BFS(x,y,visited): queue = deque() visited[x][y] = True queue.append([x,y]) kill_ai_stone = 1 flag = 0 while queue: x,y = queue..

평범한 이분탐색을 이용한 LIS import sys input = sys.stdin.readline from bisect import bisect_left N = int(input()) cards = list(map(int, input().split())) LIS = [0] for card in cards: if card > LIS[-1]: LIS.append(card) else: LIS[bisect_left(LIS,card)] = card print(len(LIS)-1)

겹치는 구간이 몇개냐 세주면 된다. def count_bus(n): bus_stops = [0 for _ in range(5000)] for _ in range(n): start, end = map(int,input().split()) for i in range(start-1,end): bus_stops[i] += 1 P = int(input()) qa_set = [] for i in range(P): qa_set.append(bus_stops[int(input())-1]) return qa_set for test in range(1, int(input())+1): N = int(input()) answer = count_bus(N) print(f'#{test}', end=' ') print(*answer)

문자열이 다 빌때까지 제거하며 더해줬다. def read_vertical(s): answer = '' cnt = 0 while cnt

예전 강의실 배정문제처럼 풀었다. round가 반올림이 아니라 사사오입이라는걸 깨달은 아주 소중한문제.. 내 한시간.. from heapq import heappop,heappush from math import ceil def find_time_units(n): students = [] for _ in range(n): start, end = map(int,input().split()) if start > end: start, end = end, start start = ceil(start/2) end = ceil(end/2) students.append([start,end]) students.sort() time_units = [] heappush(time_units,students[0][1]) fo..

배열회전 너무 잘써먹는듯.. 대신 사고가 좀 갇히는것 같기도 하다. 다른 방법도 많은데 import sys input = sys.stdin.readline def rotate_clock(n, matrix): rot90 = [k[::-1] for k in zip(*matrix)] rot180 = [k[::-1] for k in zip(*rot90)] rot270 = [k[::-1] for k in zip(*rot180)] merge_matrix = [[] for _ in range(n)] for matrix in rot90,rot180,rot270: for i in range(n): merge_matrix[i].append(''.join(map(str,matrix[i]))) return merge_matr..

뒤에서부터 작은걸 만나면 그 차이만큼 결과에 더해줍니다. for test in range(1,int(input())+1): N = int(input()) prices = list(map(int, input().split())) answer = 0 max_price = 0 for j in range(N-1,-1,-1): if max_price > prices[j]: answer += max_price - prices[j] else: max_price = prices[j] print(f'#{test} {answer}')

널리 알려진대로 dp이용해서 풀이. import sys input = sys.stdin.readline def stick_paper(n): length = n//10 dp = [0] * (length+1) dp[0],dp[1] = 1,1 for i in range(2,length+1): dp[i] = dp[i-2]*2 + dp[i-1] return dp[length] for test in range(1,int(input())+1): print(f'#{test} {stick_paper(int(input()))}')

stack을 이용해 같은게 옆에있으면 같이 빼버린다. def repeat_str(s): init = len(s) stack = [] cnt = 0 while s: pre = s.pop() if stack: if pre == stack[-1]: stack.pop() cnt += 1 else: stack.append(pre) else: stack.append(pre) return init - 2*cnt for test in range(1,int(input())+1): s = list(input()) print(f'#{test} {repeat_str(s)}')