one Book a Day

이건 그냥 평범한 dp였다. 그전 조건이있는 칸부터 떨어진만큼 제곱을 더해서 기록해주는 방식. import sys input = sys.stdin.readline N = int(input()) BOJ_avenue = input().rstrip() # 스타트 i i+1부터N번까지 점프 가능 K만큼 점프하는 에너지 k*k # 가장 가까운 BOJ를 순서대로 밟기. # 누적 -> dp(전 상태에 따라 변화값이 존재하는 조건.) dp = [float('inf')]*N dp[0] = 0 for i in range(1,N): for j in range(i): if BOJ_avenue[j]=='B' and BOJ_avenue[i]=='O': dp[i] = min(dp[i],dp[j]+ pow(i-j,2)) elif B..

제목부터 힙큐 두개쓰라고 나와서 두개썼다. 근데 사실 큐를 두개쓰기때문에 한쪽에서 사라진걸 다른쪽에서 어떻게 없앨꺼냐? 에 대한 아이디어를 보는 문제였다. 결론은 삽입시 입력했던 i값이 같은 인자를 매번 D패턴마다 앞에서 while을 통해 삭제시켜주는 것. 겹쳤던걸 모두 거른 후 본 명령을 시행하는 방식이다. i값 삭제여부는 삽입시 true 삭제시 false로 공유되는 정보인 visited 배열을 통해 해결한다. => 연결되지 않는 두 자료구조 간에는 id값과 공통정보를 수용하는 자료구조를 두어 연계시킨다. import sys input = sys.stdin.readline from heapq import heappush,heappop # key값 관리를 통해 어떤 수를 삽입하면 True 삭제하면 그 키..

조건이 있는 다익스트라. 다익스트라까지는 구현이 쉬웠지만 검문소 하나하나 거는게 생각보다 빡빡했다. 결국 최소거리 path를 구해서 그 도로들만 조사하고 또 이거저거 필요없는 조건들 줄여서야 겨우 시간 통과. 다른분들 풀이보니 아예 최소 이동 도로만 조사하셨던데 그걸 의도한게 맞을듯. 여튼 나는 그냥 모든 지점에 대해 최소로 이동되는 도로들만 조사했다. import sys input = sys.stdin.readline from heapq import heappop,heappush # 가중치 있는 그래프. # 최소 시간. 양수. # 경찰 도로 검문(간선 가중치 무한대).(탈출 지연) # 1진입 N탈출. -> 다익스트라. # 경찰이 도로를 막았을때 지연시킬 수 있는 최대시간을 정수로 출력. # 지연효과없으..

얘도 예전에 풀었던 위상정렬문제. queue에 넣는 기준이 인접점이냐 레벨0이냐? 이거만 잘 정하면 쉽다. import sys from collections import defaultdict,deque input = sys.stdin.readline def topological_sorting(): queue = deque() for i in range(1, N+1): if level[i] == 0: queue.append(i) while queue: cur_order = queue.popleft() final_order.append(cur_order) for post_order in post_order_table[cur_order]: level[post_order] -= 1 if level[post_or..

예전엔 어려웠지만.. 이젠 위상정렬.. 쉬운걸? ez 원큐에 짜서 원큐에 통과. 기분좋다. import sys input = sys.stdin.readline from collections import deque def topological_sorting(): queue = deque() for i in range(1,N+1): if not level[i]: queue.append(i) dp_times[i] = times[i-1] while queue: cur_node = queue.popleft() if cur_node == W: return for next_node in graph[cur_node]: dp_times[next_node] = max(dp_times[cur_node]+times[next_..

계속 쌓이는 값들 중에서 도 뭔가 sort를 계속 해주며 중앙값을 읽어야만 할것같지만 sort를 하다가는 시간초과에 걸릴게 자명.. sort를 하는대신 최대힙과 최소힙 두개를 만들어 읽어야하는값을 그 사이에 계속 컨트롤 해주는 방식으로 힙을 운용한다. 한쪽 힙의 길이가 길어지지 않도록 같은 길이면 왼쪽에 길이가 다르면 오른쪽에 넣어 균형을 맞춰주고 읽어야하는 왼쪽 힙의 value를 기준으로 좌우 크기가 역전되면 팝, 푸시를 통해 정렬된 상태를 유지해준다. import sys import heapq n = int(sys.stdin.readline()) max_h, min_h = [], [] # max_h[0][1]값을 기준으로 큰 값은 min_h, 같거나 작은 값은 max_h에 삽입 for _ in ran..

포인터로 와리가리하면서 삽입, 출력해야하는문제 뭔가 insert를 써야할 것 같은 문제는 보통 stack을 2개쓰거나 heap을 두개쓰거나 하면 된다. import sys input = sys.stdin.readline T = int(input()) for test in range(T): L = input().rstrip() left,right = [],[] for chr in L: if chr=="": if right: left.append(right.pop()) elif chr=="-": if left: left.pop() else: left.append(chr) answer = left + right[::-1] print("".join(answer))

Component란? ​ 전체의 부분. ​ 하나의 덩어리라면? 높은 의존성을 가진다 재사용성이 낮다 규모가 큰 설계에 적용하기 어렵다. 프론트엔드에서 컴포넌트란? Ajax 이후로 사용자와 인터렉션 증가 -> 웹의 복잡도 증가 -> 복잡한 웹을 작게 나누기시작함. -> 웹을 효율적으로 설계할 수 있게 됨. 컴포넌트란? 엘리먼트 그룹을 반환하는 자바스크립트 함수 컴포넌트의 분리. Atomic Design 이란? 원자 : 유저 인터페이스를 구성하는 최소 단위의 블록. (ex. 버튼, 인풋, 폼같은 HTML태그들) 분자 : 원자가 모여 기능을 구현 유기체 : 원자, 분자, 유기체들의 조합(헤더영역) 하나 이상의 책임을 가짐. 템플릿 : 컴포넌트들을 배치하는 레이아웃. 단점 : 분리하는 기준이 모호. 원자 하나가..

처음에 조합으로짰다가 최대한 줄여도 메모리 시간초과나서 고생하다 결국 c++코드보고 이분탐색풀이로 다시 짰다. 이분탐색 안그래도 공부하려고 생각중이었는데 오늘 기본문제부터 조금씩 풀어봐야 할듯 싶다. 위는 조합풀이, 아래는 이분탐색 풀이. import sys input= sys.stdin.readline from itertools import combinations # N-1개의 사이에서 M-1개의 작대기를 뽑는 조합. # 각 max값중 최댓값과 slice한 작대기 위치 패킹해 저장. # 저장된 max값 정렬 후 맨앞에있는 배열 출력. N,M = map(int,input().split()) ball_lists = list(map(int,input().split())) maxes = float('inf')..

점에서 각 집까지 최소거리 = 대놓고 다익스트라. 처음엔 조건 못보고 dp그려야하나 고민하고 있었는데 다시보니 가까운 순서로 방문이라고 대놓고 써줘서 다익스트라 결과값 정렬때린다음 반복문 으로 쉽게 해결했다. import sys input = sys.stdin.readline from heapq import heappop,heappush # 1. 0번에서 각 집에 가는 최소거리. -> 다익스트라 def dijkstra(start): heap = [] dp_dists[start] = 0 heappush(heap,[dp_dists[start],start]) while heap: cur_dist,cur_node = heappop(heap) for next_node,next_dists in graph[cur_n..