one Book a Day

제목부터 힙큐 두개쓰라고 나와서 두개썼다. 근데 사실 큐를 두개쓰기때문에 한쪽에서 사라진걸 다른쪽에서 어떻게 없앨꺼냐? 에 대한 아이디어를 보는 문제였다. 결론은 삽입시 입력했던 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탈출. -> 다익스트라. # 경찰이 도로를 막았을때 지연시킬 수 있는 최대시간을 정수로 출력. # 지연효과없으..

예전엔 어려웠지만.. 이젠 위상정렬.. 쉬운걸? 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))

처음에 조합으로짰다가 최대한 줄여도 메모리 시간초과나서 고생하다 결국 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..

뭔가 줄일수 있을 것 같긴한데 일단 통과. 3차원 배열은 뭔가 3차원값들에 대해 늘 초기화해줘야 한다는게 좀 짜증난다. 얕은복사라 그런가 자꾸 초깃값을 가져와서 새로 덮어씌우는 바람에 아직 설계가 손에 익지 않는다. 오늘 좀 더 설계에 대해 연습해 볼 것. 3차원 배열 내 값의 수정과 반복문에 대해서. import sys input = sys.stdin.readline # 세로 M 가로 M M,N = map(int,input().split()) K = int(input()) maps = [list(input().rstrip()) for _ in range(M)] dp = [[[0,0,0] for _ in range(N)] for _ in range(M)] # 정글 J 바다 O 얼음 I for i in r..

다른 스터디원들 보면 뭔가 짧게 풀었던데 일단 나는 0,0기준 고쳐야하는것 체크하고 그 값 범위마다 따로sum구해서 비교했다. import sys input = sys.stdin.readline N,M = map(int,input().split()) chess = [list(input().rstrip()) for _ in range(N)] dp = [[0]*M for _ in range(N)] for i in range(N): for j in range(M): if i%2 == j%2: if chess[0][0] != chess[i][j]: dp[i][j]=1 else: if chess[0][0] == chess[i][j]: dp[i][j]=1 min_change = float('inf') for i i..

Tree 탐색등등 종종 나오는 경우의수를 따지는 DFS문제이다. idx 값을 1개 늘리냐 2개 늘리냐의 분기로 재귀를 실시. 실질적인 4방탐색이나 숨바꼭질 같은 문제와 다를게 없다. 재귀로 값을 누적시키며 달릴것이냐 큐나 스택을 이용할 것이냐의 차이. 선택의 문제. 경우의 수. 종료조건은 max값이 수열 길이와 같은 것. 왜 못풀었을까 생각해보자. import sys from collections import deque def DFS(idx): # idx 1부터 시작 kriii의 검사가 모두 끝나면 수열의 가장 큰 값을 찾는다. if idx == len(kriii): high = 0 for i in range(len(sequence)): high = max(high,int(sequence[i])) # 가..