LOEWEN LOEWEN

문제 링크 반환형식생각보다는 까다로운 반환 형식... "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 ..

문제 링크 생각보다는 어려웠던 문제.사실 이런 유사 문제는 DP 아니면 BFS일 때가 많고, 그중에서도 어지간하면 DP일 때가 많기는 하다.이 문제에 BFS가 안 통하는 이유는, 순서가 상관없는 조합 문제이기 때문이다. 아래의 그림은 2원과 3원으로 10원을 만드는 조합이다.2와 3으로는 2+2+2+2+2, 2+2+3+3와 같이 총 두 가지의 방법으로 10을 만들 수 있는데, 이는 아래의 그림과 같이 표현된다. 이를 코드로 표현하면 다음과 같다:def solution(n, money): dp = [1] + [0] * n for money_type in money : for i in range(money_type, n+1) : dp[i] += dp[i - ..

구간 최댓값과 세그먼트 트리잊을만하면 나오는 "구간 최댓값" 문제. 구간 최댓값, 구간합, 구간 최솟값 같은 문제는 세그먼트 트리 방식을 사용하는 것이 시간 복잡도 측면에서 유리할 때가 많다.  이를 트리 구조로 다시 봐보자. 세그먼트 트리이지만, 개인적으로는 트리가 아니라 리스트 방식으로 보는 것이 이해가 훨씬 더 수월했다. 보는 바와 같이 인덱스 1부터가 사실상 시작인데, 이는 트리 구조에서 인덱스 1을 root node로 놓으면, 2x하면 왼쪽 자식, 2x+1 하면 오른쪽 자식이 되어 계산이 편해지기 때문이다. 그럼 [1, 3, 5, 7, 9, 11] 중 index range(1, 4), 즉, [3, 5, 7] 의 최댓값을 찾아보자.1. 우선 우리가 구하고자 하는 구간 최대값 \(x = - \inf..

문제 링크 프로그래머스 PCCP 문제가 으레 그렇지만, 문제만 읽고는 도통 문제 해석이 쉽지 않다. (얘넨 항상 이런 식임). 이럴 때에는 문제에서 친절하게 제공해주는 예시를 철저히 분석해야 한다. 어차피 방정식이 아닌 이진탐색으로 문제를 풀 것이지만, 방정식으로 문제를 이해해보자.1번 문제의 답, 즉 숙련도를 \(x\)라고 해보자. 그러면 총 소요되는 시간은 다음과 같다:  i) \(3 \leq x  2번 퍼즐만 숙련도를 초과하므로 추가시간이 소요된다.즉 총 소요되는 시간은:\[2 + (4 + (5 - x) \times (2 + 4)) + 7 = 43 - 6x\]여기서 \(43 - 6x   ii) \(1 \leq x  2번과 3번 퍼즐이 숙련도를 초과한다.그러면 총 소요되는 시간은:\[2 + (4 + ..