238. Product of Array Except Self - 파이썬 풀이 해당문제 링크목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 일단 해당 문제는 O(n) 시간 복잡도로 풀어야한다는 조건이 있고 나눗셈을 쓸 수 없다. 그렇다면 시간 초과가 나지 않기 위해서는 3N 이런식은 상관없는데 N^2가 되면 안된다. 그럼 각 인덱스에서 곱하기를 계산하고 있으면 안된다는 의미이다. 그래서 여기서 구간 합을 이용할 것이다. 구간합이란 a라는 인덱스에서 b란 인덱스 까지의 합을 의미한다. 부분합은 0에서 b란 인덱스까지의 합을 의미하는 것이다. 만약 내가 어떤 구간 합을 구하고 싶으면 보통 해당 인덱스부터 반복을 통해서 마지막 인덱스까지의 합을 구하는 것을 생각할 것이다. 하지만 이 방법은 모든 인덱스마다의 ..

해당문제 링크목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 해당 문제는 1=0: new[j-1] += dp[j] if j+1

해당문제 링크 목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 먼저 해당 문제는 가능한 많은 양의 포도주를 맛봐야하는 최적화 문제이다. 무작정 백트래킹과 같이 모든 경우의 수를 생각해볼수 있으나 잔의 개수가 최대 10,000개 이기 때문에 시간 초과 발생할 것으로 생각된다. 그렇다면 DP를 이용해서 풀어야겠다고 생각했다. DP의 최적문제는 이전 저장된 값들을 이용해서 이후의 최적의 값을 찾는 것이다. 그렇게 하기 위해서 바텀업을 하면서 반복하여 푸는 방식을 이용할 것인데 이 경우 작은 문제에서 큰 문제를 풀기 때문에 작은 경우를 생각해보는 것이 좋다고 생각한다. 해당 문제는 3개 연속으로 와인을 마시지 못한다. 이를 알아두고 작은 경우를 생각해보겠다...

3. Longest Substring Without Repeating Characters - 파이썬 풀이 해당 문제 링크 문제접근 아이디어 구현코드 문제접근 아이디어 일단 문자열의 길이가 50,000개 정도이기 때문에 순차적인 탐색을 해도 괜찮을 것 같다. 순차적으로 비교를 하다가 지금 가지고 있는 subString안에 같은 문자가 존재하면 해당 문자까지 빼주고 중복되지 않는 문자부터의 subString에 현재 문자를 더해서 다시 비교해준다. 같은 문자가 나오면 최대값과 비교해서 갱신한다. 구현코드 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if s == "": return 0 start = 0 maxLength =..

백준 2293번 동전 1 - 파이썬 풀이 문제풀이 아이디어 구현코드 문제풀이 아이디어 해당 문제는 이전의 수의 풀이 값을 이용하여 현재의 수에 대한 값을 구하기 때문에 DP 문제이다. 먼저 해당 문제를 굉장히 간단하게 1,2의 동전 종류로 4의 값을 만든다고 가정해보자.dp = [0]*(k+1) 동전 종류 1 2 3 4 1 2 위의 표를 이용해서 설명을 하면 동전 종류 1을 이용해서 1이란 수를 만들기 위한 경우의 수는 몇개일까? 1개일 것이다. -> [1] 그렇다면 동전 종류 1을 이용해서 2이란 수를 만들기 위한 경우의 수는 몇개일까? 1개일 것이다. -> [1,1] 그렇다면 동전 종류 1을 이용해서 3이란 수를 만들기 위한 경우의 수는 몇개일까? 역시 1개일 것이다. -> [1,1, 1..

542. K Closest Points to Origin - 파이썬 풀이 문제접근 아이디어 구현코드 문제접근 아이디어 해당 문제는 입력되는 point의 개수가 최대 10,000개이다. 그래서 그냥 반복문을 이용해서 해결할 수 있을 것이라 생각된다. 요구하는 것은 유클리드 거리가 짧은 순서대로 k만큼 반환하라는 것이다. 계산된 특정 값을 이용하여 정렬을 하는 것을 생각할 때 가장 편리하게 사용할 수 있는 것은 내 생각으론 우선순위 큐이다. 유클리드 값을 계산 해서 파이썬 라이브러리 heapq에 넣으면 정렬이 되어있다. 이 값을 음수로 바꿔서 넣으면 거리가 제일 긴 것이 pop을 하면 나올 것이다. 그리고 우선순위 큐에 요소의 수를 len()으로 세어서 내가 원하는 값보다 더 크면 pop을 해서..