LOEWEN LOEWEN

문제 링크 생각보다 섬세함이 필요한 BFSBFS 그거 그냥 queue 만들어서 while queue 하면 끝 아님? 싶을 수 있겠지만... BFS에 익숙해진 나머지, 근의 공식 사용하듯이 그렇게 아무 생각 없이 풀면 안 된다는 것을 깨달았다. 일단 이 문제는, MST(최소 스패닝 트리) 방식으로도 충분히 잘 풀 수 있다. 그것도 물론 좋은 방법이지만, 나는 BFS 풀이로 풀었다. 오답 풀이import heapqdef solution(land, height): N = len(land) queue = [(0, 0, 0)] seen = [[False] * N for _ in range(N)] dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] ..

1. deque()에서는 rotate()가 가능하다.from collections import deque A = deque([1,2,3,4,5])A.rotate(-1)A #deque([5, 1, 2, 3, 4]) 2. deque()를 deepcopy()해도 rotate()가 가능하다.from collections import deque from copy import deepcopyA = deque([1,2,3,4,5])A.rotate(1)B = deepcopy(A)B #deque([5, 1, 2, 3, 4]) 3. dict()의 value가 deque()여도 rotate()가 가능하다.A = {0 : deque([1,2,3,4,5]), 1 : deque([1,2,3,4,5]), 2 : de..

문제 링크 Simple is the best 쫄지 말자. 구간합 문제는 누적리스트로 풀릴 때가 많다.def solution(cookie): n = len(cookie) S = [0] * (n+1) for i in range(1, n+1) : S[i] = S[i - 1] + cookie[i - 1] #S[i]는 A[i-1]까지의 합 max_sum = 0 for m in range(n-1) : l = 0 r = n-1 while l right : l += 1 else : ..

문제 링크 정답 코드하라는 대로 하기만 하면 되는 간단한 문제.def solution(lines): times = [] for line in lines: date, time, duration = line.split() hh = int(time[:2]) mm = int(time[3:5]) ss = int(time[6:8]) ms = int(time[9:]) duration = int(float(duration[:-1]) * 1000) end_time = (hh * 3600 + mm * 60 + ss) * 1000 + ms start_time = end_time ..

문제 링크 반환형식생각보다는 까다로운 반환 형식... "09:41" → 581"10:11" → 611 뭐 이런 식으로 시간 string을 60*hh + mm 해서 int로 바꾸는 건 쉬운데, 사실 그 역과정이 꽤나 복잡하다. "9:41"이 아니라 "09:41"을 반환해야 하기 때문이다. 이럴 때 파이썬 포맷팅을 쓰면 쉽다.f"{5:02d}" # 결과: "05" 정답코드이 문제를 어렵게 생각할 필요는 없다. 결국 이 문제는 어느 게으른 직원이 "가장 마지막 셔틀"의 "가장 마지막 좌석"에 타고 싶어 하는 것이기 때문이다. 탐색조차도 불요하다.from collections import dequedef solution(n, t, m, timetable): # 셔틀 운행 횟수 n, 셔틀 운행 간격 t, ..

문제 링크 이렇게 여러 개의 직사각형이 형성하는 영역의 외곽을 따라 이동하여 빨간 점에서 파란 점까지의 최소 거리를 찾으면 되는 문제. 이거 걍 BFS 아님?정확하다. 이런 문제는 그냥 이렇게 격자를 나누어서 우리가 갈 수 있는 "도형의 외곽"을 1로 채우고, 도형의 내부는 2로 채워서 BFS 탐색하면 끝!라고 생각하기 쉽다. 그런데 치명적인 문제점이 있다.   바로 저 보라색 부분이 문제된다. 원래는 아래와 같이 삥 돌아가야 하는 경로인데, 위와 같은 형태의 map이라면 바로 위로 뚫고 가버리니 말이다.그러므로, 더 촘촘하게 격자를 나누어야 한다. (두배로) 자 이제 안심이다. 이제는 붙어있는 변과 한칸 띄어져 있는 변이 정확히 구분된다. 정답코드from collections import dequede..

문제 링크 여기서 Floyd-Warshall이?갑자기 웬 플로이드-워셜인가 싶을 것이지만, 이 문제를 찬찬히 살펴보면 알게 될 것이다. Floyd-Warshall 알고리즘의 본질은, i-j의 관계를 모르더라도 i-k, k-j 사이의 관계를 알면 결국 i-j 사이의 관계를 알게 된다는 것이다. 그러므로 이 알고리즘은 비단 "거리"나 "cost"에 한정된 아이디어가 아니다. 예를들어 이는 부등호 관계에서도 성립되는 아이디어이다. i > k, k > j 를 알고 있다면, i > j 또한 알 수 있게 되기 때문이다. 정답 코드def solution(n, results): graph = [[0] * n for _ in range(n)] for A, B in results : ..

문제 링크 최소 스패닝 트리문제를 읽자마자 대놓고 "최소 스패닝 트리로 풀어!" 라고 말하고 있다.최소 스패닝 트리(MST) 문제는 Prim 알고리즘과 Kruskal 알고리즘으로 풀 수 있다.Prim 알고리즘 : 임의의 정점에서 시작해서 가장 가까운 이웃 정점을 고르고, 다시 그 정점에서 가장 가까운 정점을 고르기를 반복하는 것Kruskal 알고리즘 : 간선 중 짧은 것부터 고르는 것. 다만, Cycle이 형성되면 안 됨.Cycle이 형성되면 안 된다는 문제점 때문에 (이게 생각보다 코드 구현이 빡세서), 보통은 Prim 알고리즘이 선호된다. 여기에서도 Prim 방법을 쓸 것이다.비슷한 백준 문제를 Kruskal 알고리즘으로 푼 포스트는 다음 링크에 있다:https://loewen.tistory.com ..