LOEWEN LOEWEN

문제 링크 무식한 방법 (시간복잡도 초과)이 문제는 상당히 쉽지 않은데, 사실 첫눈에는 쉬워보인다. 그냥 하라는 대로 하는 건 어렵지 않기 때문이다. 문제는 시간복잡도이다.from collections import Counterdef solution(land, P, Q): sqz_land = [] for wall in land : sqz_land += wall min_h = min(sqz_land) max_h = max(sqz_land) sqz_land_counter = Counter(sqz_land) min_cost = float('inf') for flattened_h in range(min_h, max_h+1) : ..

문제 링크 하란다고 진짜로 하지 말기요즘 이런 식의 문제를 많이 풀어서 느껴지는 거지만, 문제에서 정의내리는 "부분수열"을 진짜로 만들어서 그것이 스타수열인지 체크하고... 하는 것은 불가능하다. 리스트에서 원소 하나 삭제하고 할 때마다 O(N)인데, 그걸 2^N 번을 반복해서 탐색한다?*왜 2^N번 반복이냐면 nC0 + nC1 + nC2 + ... + nCn = 2^n 이니까 O(N*2^N) 같은 건, N이 24 이하여야 가능하다.  그런데 N이 500,000까지 치솟을 수 있는 상황에서 저 복잡도는 그냥 말도 안 되는 소리이다. 언제나 본질을 기억하자. 부분수열을 만들어서 뭘 한다고 해서 "진짜로" 그걸 만들 필요는 없다. 정답 코드from collections import Counter, deque..

문제 링크 "실제로 구현할 필요 없음" 구현, 특히 빡구현 문제들을 많이 풀고, 또한 BFS 문제를 많이 접하다보면 으레 까먹는 중요한 사실이 있다. 문제가 자신만의 상상의 나래를 펼쳐 죠르디가 기둥과 보를 짓는 이러한 문제를 풀 때, 기둥과 보를 설치하거나 철거하란다고 진짜로 설치하거나 철거할 필요는 없다는 것이다. 그런데 사실 그 유혹에 넘어가는 게 생각보다 쉽다. 왜냐하면, n이 겨우 100 이하이기 때문에, 100 * 100 행렬을 만들어도 공간복잡도가 10,000 밖에 되지 않아서, 마치 이게 정답인 길 같아 보이기 때문이다.  그러나 지금 이 문제에서 중요한 것은, 설치/철거 명령어 시퀀스에서 feasible한 명령만을 취한 후, 이를 sort하여 반환하는 것 뿐이다. 실제 map에 이를 구현..

문제 링크 이거, 수학적으로 풀기 쉽지 않다. 문제를 보다보면 이건 마치 확률 및 통계 기법으로 풀릴 것처럼 보인다. 물론 솔직히 푸는 방법이 없을 것 같지는 않은데, 그거 수학적 풀이 생각하고 있느니 그냥 탐색하는 게 더 좋다. 그리고 해보면 알겠지만 수학적 풀이 구현이 더 어려움,,, 왜냐하면 문제 조건에서,N 어디 마음껏 탐색해보라고 속삭이고 있기 때문이다. 세상에 N  그럼에도 불구하고 시간복잡도 초과된 코드아래의 코드는 brute-force 탐색 코드 치고 상당히 최적화가 잘 된 코드이다. 그럼에도 불구하고 시간복잡도가 초관된다. 어디 마음껏 탐색해보래서 진짜로 탐색했더니, 복잡도가 초과되는 것이다.#시간복잡도가 초과된 정답코드from itertools import combinations, pr..

문제링크 문제 조건이 속삭이고 있다. 마음껏 Brute-force 탐색하라고. 즉, 이 문제는 DP 문제이다. 정답 코드def solution(N, number): dp = [set() for _ in range(9)] for i in range(1, 9) : dp[i].add(int(str(N) * i)) for i in range(1, 9) : for j in range(1, i) : for a in dp[j] : for b in dp[i-j] : dp[i].add(a+b) dp[i].add(a-b) ..

문제 링크 이걸 DP가? 그러므로, string의 i부터 j까지가 팰린드롬인지를 저장하는 dp matrix를 만들어서, dp를 해내가면 된다! 정답 코드def solution(s): n = len(s) dp = [[False] * n for _ in range(n)] for i in range(n) : dp[i][i] = True answer = 1 for i in range(n-1) : if s[i] == s[i+1] : dp[i][i+1] = True answer = 2 for length in range(3, n+1) : for i in ra..

문제 링크 정말정말 어려웠던 문제... class Node도 선언해보고 별거 다 해봤지만... 결론은 간단한 이진탐색, 혹은 인덱스가 저장된 heapq를 사용하는 것이었다. 윈도우 슬라이싱에 있어서 heapq 사용의 어려움만약 슬라이싱 윈도우를 list로 관리한다면(최악임) 시간복잡도는 아래와 같다. 여기서 K는 슬라이싱 윈도우의 크기이다.즉, O(K)로 최댓값을 찾고, 새로운 윈도우를 O(K)로 구하는 과정을 N번 반복해야 하기 때문에 (N은 전체 리스트 길이)전체 시간복잡도는 O(NK^2)이다! 이 경우 문제 조건에 의해 최대 8 * 10^15 의 복잡도를 가질 수 있다.(복잡도는 1억 넘기면 좀 힘들다고 생각하면 편함) → deque 쓰면 되잖아? 이 경우에도 복잡도는 O(NK)이기 때문에 10^1..

문제 링크 시간복잡도 초과된 코드 이 코드는 시퀀스에서 "110"을 찾아서 다른 데에 끼워넣을 수 있는 모든 경우의 수를 찾고, 그중 사전순 가장 빠른 시퀀스를 찾아서, 다시 그 시퀀스에서 "110"을 찾고...를 반복하는 코드이다. def solution(s): answer = [] for sequence in s : n = len(sequence) if n   Stack 자료구조를 이용해 새롭게 탄생될 "110"을 미리 감지하기관건은 뭐였냐면, "110"을 전부 찾아서 다른 데에 옮겼는데 그걸 옮김으로 인해서 그 전에 없었던 새로운 "110"이 생기면 그것을 어떻게 처리하는가였다. 답은 생각보다 간단했는데, stack 자료구조를 이용하는 것이었다.위와 같이 ..