junhwa100 님의 블로그

1. 문제 이해prices라는 배열이 주어진다.배열의 i번째 요소는 i번째 날의 주식 가격이다.각각의 날에 주식을 사거나 팔 수 있다.(같은 날에 사고 팔 수 있다.)여러 번의 거래로 얻을 수 있는 최대 이익을 구한다.  2. 풀이 과정오르기 전에 주식을 산다.떨어지기 전에 주식을 판다.그리디 알고리즘으로 풀이한다. 배열을 순회한다. i+1번째 날의 가격이 i번째 날의 가격보다 크면 가격 차를 결과에 더한다.for i in range(len(prices) - 1): if prices[i+1] > prices[i]: result += prices[i+1] - prices[i]  3. 전체 코드class Solution: def maxProfit(self, prices: List[in..

1. 문제 이해m x n matrix가 있다.row는 왼쪽에서 오른쪽으로 오름차순으로 정렬되어 있다.column은 위에서 아래로 오름차순으로 정렬되어 있다.matrix에서 target 값이 존재하면 true를 리턴하는 알고리즘을 구현한다.  2. 풀이 과정row와 column 모두 정렬된 배열이다.첫 행의 맨 뒤 요소를 택한 다음, target이 이보다 작으면 왼쪽으로, 이보다 크면 아래로 이동한다.첫 행의 맨 뒤 요소로 row와 column을 초기화한다.row = 0col = len(matrix[0]) - 1 row와 column이 유효한 동안 반복한다.while row = 0: if target == matrix[row][col]: return True elif target ..

1. 문제 이해하나의 정렬된 배열이 주어진다.배열에서 합쳐서 target을 만드는 두 수의 인덱스를 구한다.(배열의 인덱스는 1부터 시작한다.)두 인덱스를 하나의 배열로 리턴한다.  2. 풀이 과정배열이 정렬되어 있으므로 투 포인터를 사용한다.start, end를 처음과 끝 인덱스로 초기화한다.두 수의 합이 target보다 크다면 end를 1만큼 감소시킨다. target보다 작다면 start를 1만큼 증가시킨다.두 수의 합이 target과 같다면 start+1, end+1을 리턴한다.start, end = 0, len(numbers)-1while start target: end -= 1 elif numbers[start] + numbers[end]  다른 풀이로 Binary Searc..

1. 문제 이해두 배열이 주어진다.두 배열의 교집합을 구한다.  2. 풀이 과정한쪽 배열은 순서대로 탐색하고 다른 한쪽 배열은 정렬해서 Binary Search로 값을 찾는다.첫 번째 방법은 Binary Search를 직접 구현하는 것이다.704번 문제와 거의 동일하게 구현한다. target 매개변수만 추가한다.def binary_search(a:int, b:int, target) -> int: if a > b: return -1 mid = (a+b)//2 if target == l1[mid]: return mid if target > l1[mid]: return binary_search(mid+1, b, target) elif target..

1. 문제 이해F(0) = 0, F(1) = 1이다.n이 주어진다. 피보나치 수열 F(n)의 값을 구한다.  2. 풀이 과정첫 번째 방법은 재귀를 이용해 풀이하는 것이다.class Solution: def fib(self, n: int) -> int: if n  실행 시간이 매우 길다.실행 시간을 줄일 방법은 없을까?두 번째 방법은 Dynamic Programming의 하향식 풀이인 Memoization을 이용하는 것이다.계산한 값을 저장하기 위해 딕셔너리 형태의 dp 그래프를 만든다.dp = collections.defaultdict(int) 계산하기 전에 dp[n]의 존재를 확인하고 존재한다면 dp[n]을 리턴한다.if self.dp[n]: return self.dp[n] Me..

1. 문제 이해오름차순으로 정렬된 정수들의 배열이 주어진다.target 정수의 배열 인덱스를 구한다.시간복잡도 O(logn)으로 풀어야 한다.  2. 풀이 과정시간복잡도 O(logn)이라는 조건이 있다.Binary Search로 접근한다. 시작 인덱스, 끝 인덱스를 매개변수로 하는 재귀함수를 구현한다.  3. 전체 코드class Solution: def search(self, nums: List[int], target: int) -> int: #a는 시작 인덱스, b는 끝 인덱스 def binary_search(a: int, b: int) -> int: if a > b: return -1 mid = (a+b)..

1. 문제 이해문자열 s와 t가 주어진다.t가 s의 Anagram이면 true를 리턴한다. 2. 풀이 과정두 문자열을 모두 정렬하고 같은지 비교한다. -> 이 방법은 O(nlogn)이다.def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == sorted(t) (25.12.8)Counter 객체를 각각 만들어 비교한다.(Counter은 해시맵을 사용하므로 O(n)이다.)Counter 객체의 비교 연산은 객체가 가지고 있는 모든 키와 밸류들이 일치하는지 확인한다. 3. 전체 코드class Solution: def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == ..

1. 문제 이해음이 아닌 정수들의 배열이 주어진다.이 정수들을 arrange하여 만들 수 있는 가장 큰 수를 리턴한다.(string형으로)  2. 풀이 과정첫 번째 풀이는 Insertion Sort를 이용한다. xy와 yx의 크기를 비교하는 함수를 구현한다.def compare(n1: int, n2:int) -> bool: return str(n1) + str(n2)    Insertion Sort의 Pseudocode를 참고하여 구현한다.def largestNumber(self, nums: List[int]) -> str: i = 1 while i 0 and self.compare(nums[j-1], nums[j]): nums[j-1], nums[j] = nums[..

1. 문제 이해Linked List를 Insertion Sort를 사용해서 정렬한다.  2. 풀이 과정 Insertion Sort는 정렬을 해야 할 대상과 정렬을 끝낸 대상, 두 그룹으로 나눠 진행한다.cur은 정렬을 끝낸 대상, head는 정렬을 해야 할 대상이다.parent는 cur의 시작 지점을 기억하는 역할을 한다.cur = parent = ListNode(None) 모든 과정은 정렬을 해야 할 대상인 head가 존재하는 경우에 진행한다.정렬을 끝낸 cur는 head와 비교하면서 더 작다면 cur.next로 이동한다.삽입할 위치를 찾는 것이다.(cur 바로 다음)while cur.next and cur.next.val  삽입한다.Python의 Multiple Assignment를 활용한다.오른쪽 ..

1. 문제 이해interval들의 배열이 주어진다.겹치는 interval들을 merge해서 겹치지 않은 interval들의 배열로 만든다.  2. 풀이 과정결과를 담을 빈 배열을 만든다.merged = [] interval의 시작값을 기준으로 오름차순으로 interval들을 정렬한다.정렬된 interval들을 순회한다.merged에 값이 존재하고 i[0] 아니라면 merged에 그대로 추가한다.for i in sorted(intervals, key = lambda x: x[0]): if merged and i[0]   3. 전체 코드class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: merg..