LOEWEN LOEWEN

문제 링크 이거, 수학적으로 풀기 쉽지 않다. 문제를 보다보면 이건 마치 확률 및 통계 기법으로 풀릴 것처럼 보인다. 물론 솔직히 푸는 방법이 없을 것 같지는 않은데, 그거 수학적 풀이 생각하고 있느니 그냥 탐색하는 게 더 좋다. 그리고 해보면 알겠지만 수학적 풀이 구현이 더 어려움,,, 왜냐하면 문제 조건에서,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 자료구조를 이용하는 것이었다.위와 같이 ..

문제 링크누적합 기법뭐 아래와 같이 행렬 일부에 같은 값을 더하거나 빼서 업데이트해야 할 일이 있다고 해보자. 직관적이긴 하지만 이러면 좀 비효율적이다. 이럴 때는이러는 편이 조금 더 낫다. 왼쪽부터 누적합을 하면 같은 결과가 나오게 되기 때문이다.이를 누적합 기법이라고 한다. 누적합 기법을 사용하지 않은 코드는 굉장히 간단하다. 그냥 빡구현도 아니고 그냥 단순 구현 문제일 뿐이다.def solution(board, skill): for heal_or_deal, r1, c1, r2, c2, degree in skill : #1 to -1; 2 to 1 heal_or_deal = 2 * heal_or_deal - 3 for r in range(r1, r2..

문제 링크 정답코드하라는 대로 하면 되는 간단한 문제def solution(n, times): shortest_time = 1 logest_time = n * max(times) while shortest_time = n : logest_time = assumed_time else : shortest_time = assumed_time+1 return shortest_time

TypeError: ' not supported between instances of 'int' and 'NoneType' 1. heapq는 O(log N)의 시간복잡도로 리스트 내 최솟값을 구할 수 있게 해주는 고마운 친구이다.혹시 이 원리를 모르겠다면, 그리고 sort()랑 뭐가 다른지 모르겠다면,min heap 자료구조를 공부하면 된다. 코드 외우지만 말고 반드시 공부하자.import heapqa = [3, 2, 1, 5, 9, 4, 7]heapq.heapify(a)heapq.heappop(a) #1단, 처음부터 heappush()로 구축한 게 아닌 이상 heapify()로 반드시 초기화 진행해야 함. 2. 심지어 원소가 int가 아니라 tuple, list여도 된다.그래서 BFS에서 매우매우매우 ..