친절한 도현씨 친절한 도현씨

★ 접근 모든 경우의 수를 살펴봐야하고, 엄청난 크기의 병사, 최대 백만인 라운드 수 이 요소들을 종합적으로 미루어 봤을 때 그리디 알고리즘을 떠올릴 수 있다. 근데 여기서 그리디만을 가지고는 풀 수 없다. 그리디인데도 불구하고 시간초과가 날 것이다. 우선순위 큐 알고리즘도 접목시켜야 풀 수 있다. ★ 풀이 매번 라운드 적군과 맞서 싸운다. 그러다가 아군 병사의 숫자가 적군의 병사의 숫자보다 부족할 경우 무적권을 써야한다. 이 때 무적권이 한 장도 남지 않았다면 게임을 종료시킨다. 무적권이 남아있다면 음수가 돼도 괜찮으니 현재 남은 아군 병사에 현 라운드 적군 병사의 숫자만큼 뺀다. 그리고 현재 적군 숫자를 우선순위 큐에 넣은다음 이제까지 치뤘던 전투 중 가장 적군이 많았던 숫자를 꺼낸 다음 현재 병사에..

※ 접근 sequence의 길이가 최대 백만이었기에 중첩 포문을 돌면 안되겠다는 생각이 제일 먼저 떠올랐다. 구간 합을 구하고 그 구간이 계속 변해가야하기에 left,right 투 포인터를 사용하기로 했다. ※ 풀이 1. 첫 시작과 나중을 구분했다. 그 이유는 처음에는 k를 같든 작든 크든 right가 오른쪽으로 이동해줘야 하기 때문이다. (right는 left보다 같거나 큰 idx에 위치해야 하기 때문이다. ) 2. temp == k라면 구간의 길이를 key로 하고 left, right를 사전형에 추가시켜준다. left와 right를 오른쪽으로 한 칸씩 이동시켜준다. 3. temp > k라면 left를 줄여준다. 4. temp < k라면 right를 한 칸 오른쪽으로 이동시켜준다. 5. 마지막에 가장 ..

※ 점근법 문제에서 시키는 것만 하면 되는 구현 문제이다. 근데 여기서 00:00 ~ 23:59 까지 시간을 흐르게 할지 여부를 정해야 하는데 그러면 오히려 반복 길이가 더 길어질 것 같아서 과제에 들어있는 것을 순차적으로 돌았다. ※ 풀이 1. 일단 멈춘 과제를 담아둘 리스트인 stop을 만들어 줍니다. 2. 마지막 과제인 경우 후에 처리해야 할 과제가 없기 때문에 무조건 끝내니 이 과제가 마지막인지 여부를 판단해줍니다. 3. 현재 과제의 끝날 시간과 다음 과제의 시작 시간을 계산해서 비교해줍니다. 4. 다음 과제 끝날 시간보다 같거나 작은 시간안에 현재 과제가 끝난다면 정답 리스트에 담아줍니다. 5. 그 후에 멈춰둔 과제가 있다면 진행해줍니다. 6. 여기서 다음 과제를 할 때까지 남은 시간을 계산해줍..

※ 접근법 문제를 봤을 때 어떤 곡괭이로 광물을 캐는지에 따라서 누적 피로도가 달라지니 바로 백트래킹인 것을 떠올렸다. 하지만 여기서 곡괭이가 최대 15개가 될 수 있는데 시간초과가 나지 않을까라는 생각이 들었다. 결국 여기서 시간초과가 발생했고 로직을 조금 수정했더니 문제가 해결됐다. ※ 풀이 1. 곡괭이 종류만큼 반복을 해 곡괭이가 남아있다면 곡괭이로 광물을 캔다. 2. 광물을 캐면서 누적 피로도를 계산해준다. 3. 다음 재귀로 넘어갈 때 누적피로도, 다음 광물 인덱스, 쓴 곡괭이 개수를 계산해서 넘겨준다. def dfs(picks,minerals,fatigue,m_idx,p_count,total): global count if m_idx >= len(minerals) or p_count == tot..

※ 접근법 두 큐 합을 같게 만들기 위한 방법은 여러가지가 있고 최소 횟수를 구해야하니 모든 경우의 수를 파악해야 한다고 생각했다. 하지만 제한사항에서 두 큐의 리스트의 길이가 최대 300,000인 것을 보고 완전탐색을 하면 안 된 다는 것을 느꼈다. ※ 풀이 1. 두 큐 리스트의 합을 비교해 큰 쪽에서 팝을 하고 작은 쪽에다가 append를 해준다. 2. 두 큐 값이 같아지거나, 한 쪽 큐가 비워지거나, 큐 하나 길이에 * 4만큼 반복을 했으면 무한루프를 끝내준다. 3. 2번 조건에 들어가기 전 까지 1번 조건을 반복해준다. def solution(queue1, queue2): count = 0 one_sum = sum(queue1) two_sum = sum(queue2) total = one_sum ..

※ 접근법 1. 그래프가 주어지고 최소의 경우의 수를 구해야 하니 탐색을 떠올렸다. 2. 보드의 크기가 최대 100, 100 총 만 칸이니 dfs로 탐색할 시 RecursionError가 발생할 것 같아 bfs로 풀기로 했다. ※ 풀이 1. 미로에서 상하좌우로 이동하는데 빙판길이라고 생각했다. 2. 장애물("D"), 벽("그래프 범위를 벗어나기 전 가장자리")을 만나기전 까지 계속 미끄러진다. 3. 목표지점을 만났다면 바로 리턴해서 함수를 종료해준다. (바로 리턴해줄 수 있는 이유는 밑에 나온다.) 4. 벽이나 장애물을 만났는데 count > 0이면서 전에 방문했을 때보다 더 작은 횟수로 방문했을 시 큐에 추가해주고 visited값을 갱신해준다. (이렇게 최소 횟수의 방법만 큐에 들어오니 목표지점 도착했..

import math def solution(fees, records): answer = [] time = dict() inout = dict() money = dict() for i in records: if i[6:10] not in time: time[i[6:10]] = int(i[0:2]) * 60 + int(i[3:5]) inout[i[6:10]] = str(i[0:5]) + "in" else: if "IN" == i[11:13]: time[i[6:10]] += int(i[0:2]) * 60 + int(i[3:5]) inout[i[6:10]] = str(i[0:5]) + "in" else: time[i[6:10]] = int(i[0:2]) * 60 + int(i[3:5]) - time[i[6:1..

def solution(k, ranges): answer = [] height = [] width = [] while k != 1: height.append(k) if k % 2 == 0: k //= 2 else: k = k * 3 + 1 height.append(1) width.append((height[0] + height[1]) / 2) for i in range(1,len(height)-1): width.append((height[i] + height[i+1]) / 2 + width[i-1]) for x,y in ranges: y = len(height)-1 + y if x > y: answer.append(-1.0) elif x == y: answer.append(0.0) else: if x =..