jyuseo

LeetCode의 238번인 "Product of Array Except Self" 문제를 풀어봤다 문제를 간략히 살펴보자.정수로 이루어진 배열이 주어지는데, 이때 해당 인덱스에 자신을 제외한 다른 모든 값을 곱한 값으로 대체하라는 것이다.위의 예제 1번에서 보는 것처럼 첫번째 index에 첫번째 index에 해당하는 값 1을 제외한 나머지 값들 (2, 3, 4)을 모두 곱한 값을 업데이트 하라는것이다.이 문제는 어렵진 않지만 몇 가지 제한조건이 있다.우선 배열의 길이는 2 ~ 105 사이여야 하며, 배열 안 정수는 -30 ~ 30 사이여야 한다.특히 가장 중요한 제한조건은 O (n)의 time complexity를 가져야 한다는 것이다.또한 나누는 연산 또한 할 수 없다.이제 문제를 풀어보자. 정답 코..

LeetCode의 380번인 " Insert Delete GetRandom O(1)" 문제를 풀어봤다 이문제에서는 스켈레톤 코드로 크게 4가지의 메서드를 주었고, 그거에 대해 채워야한다. 문제해결은 시간복잡도 O(1)만 삽입,삭제,random으로 return하는 것을 구현하는 문제이다. 1. “리스트 + 해시맵을 같이 써서” 3개 연산을 평균 O(1)로 만들기__init__ : 초기화import randomclass RandomizedSet: def __init__(self): self.numMap = {} # 정수를 인덱스와 매핑하는 딕셔너리 self.numList = [] # 정수 값을 저장하는 리스트numMap은 특정 정수를 리스트 내의 인덱스와 매핑하여 저장하는 딕셔너리 이다...

LeetCode의 274번 문제인 "H-Index" 문제이다.이문제는 두가지 방법으로 풀어봤다. 문제 핵심 : H-index = h편 이상의 논문이 각각 최소 h번 이상 인용된 최대 h. 1. 카운팅(버킷) 풀이정답 풀이(Python)class Solution: def hIndex(self, citations: List[int]) -> int: n = len(citations) paper_counts = [0] * (n+1) for c in citations: paper_counts[min(n, c)] += 1 h = n papers = paper_counts[n] while papers 아이디어h-index는 최대가 n(논문 수)을 넘을수 없고, 인용..

BFS(Breath-First Search), 너비우선 탐색 방식 1. BFS란? 너비 우선 탐색(Breadth-first search, BFS)는 맹목적 탐색 방법 중 하나로 시작 정점(vertex)을 방문한 후 인접한 모든 정점들을 우선으로 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때 까지 방문하지 않은 정점들에 대해서도 너비 우선 탐색을 적용하고, 일반적으로 queue 자료 구조를 이용해서 순차적으로 접근이 가능하도록 구현이 가능하다. Tree상에서 BFS로 탐색을 진행하는 경우에는 cycle이 생기는 경우가 없지만, graph에 BFS를 적용하는 경우에는 cycle이 있을 수 있기 때문에 무한 루프에 빠지는 것을 방지하기 위해서 방문 표시를 하면서 탐색을 진행해야 한다. 2. BFS..

LeetCode의 45번 문제인 "Jump Game II" 문제이다.한번 점프할때 도달 가능한 구간을 레벨 단위로 넓혀가는 방식으로 이문제의 알고리즘인 BFS 방식을 이용해서 풀어봤다. 문제아이디어nums[i]는 i에서 최대 점프 거리.0번에서 시작해서 마지막 인덱스 까지 가는 최소 점프 횟수를 구하는 문제. l , r "현재 점프 횟수(res)"로 도달 가능한 인덱스 범위를 의미함.어떤칸에서 점프하든, 다음 점프에서 도달 가능한 가장 먼곳을 계산해서 구간을 확장함레벨(res)에서 방문 가능한 노드 범위가 [l,r]일때 다음레벨 (res+1)에서 방문 가능한 최대 범위가 farthest 정답코드 (Python)class Solution: def jump(self, nums: List[int]) -..

LeetCode의 55번 문제인 "Jump Game" 문제이다. 이문제는 Dynamic Programming 알고리즘을 활용해서 풀어봤다.https://jyu-seo.tistory.com/98 09 - Dynamic ProgrammingDynamic Programming(동적계획법)이란큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말이다. 동적 계획법이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요가 없다. 바jyu-seo.tistory.com 각 칸에서 점프해서 마지막 칸까지 도달할수 있는지 체크하는 문제이다. DP[i]를 i번째 칸에서 최대로 점프 할 수 있는 칸 수라고 할때 DP[i] = max(DP[i-1] - 1, nums[i])로 구할 수 있다. 즉, 이전 칸에서 ..

Dynamic Programming(동적계획법)이란큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말이다. 동적 계획법이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요가 없다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 한다. Divide and Conquer(분할정복)과 비슷해보이는 알고리즘이지만, 결정적인 차이점이 있다 바로 "작은 문제가 중복이 일어나는지 안일어나는지" 이다. 분할정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법이다.특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 동적프로그래밍은 작은 부분들이 반복되는것(답이 바뀌지 않음)을 이용해 풀어나가는 방법이다. Dynamic Programming..

LeetCode의 122번 문제인 "Best Time to Buy and Sell Stock II" 문제이다 이 문제도 이전 121번문제와 비슷하게 그리디 알고리즘을 통해서 푸는 방식이다.알고리즘을 풀면서 가장 중요한게 " 가격이 오르는 구간의 이익을 전부 더하면, 여러번 사고 팔아 얻을수 있는 최대 이익과 같아진다" 라는 개념을 알고있어야 한다. 정답 코드(Python)class Solution: def maxProfit(self, prices: List[int]) -> int: profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i - 1]: profit += (prices[i] - pr..

객체 참조 복사Python에서 함수에 값을 복사할 때 실제로 개체 자체의 복사본이 아니라 개체에 대한 참조를 복사한다. 이 개념을 "객체 참조 복사" 또는 "참조 값 복사" 라고 한다. 함수에서 값 복사 동작은 객체가 변경 가능한지 또는 변경 불가능한지에 따라 다르다. 1. 불변 객체(lmmutable Objects)숫자, 문자열 및 튜플과 같은 불변 객체의 경우 함수 내 객체에 대한 모든 변경 사항은 새 객체를 생성한다. 원래 개체는 변경되지 않은 상태로 유지되므로 개체의 복사본이 함수에 복사된것처럼 보인다.def modify_value(x): x = x + 1 print(f"inside the function: {x}")number = 5modify_value(number)print(f"Outs..

힙(heap)힙은 힙 속성을 충족하는 특수 트리 기반 데이터 구조이고 완전한 이진 트리다 즉, 왼쪽에서 오른쪽으로 채워지는 마지막 수준을 제외하고 트리의 각 수준이 완전히 채워진다. 힙에서 각 노드의 키는 자식 키보다 크거나 같거나(max-heap) 작거나 같다(min-heap). 힙에는 두가지 유형이 있다.최대 힙(Max-heap)최대 힙에서 부모 노드는 자식 키보다 크거나 같은 키를 가진다. 가장 큰 키는 루트 노드에 있다.최소 힙(Min-heap)최소 힙에서 부모 노드는 자식 키보다 작거나 같은 키를 가진다. 가장 작은 키는 루트 노드에 있다.힙은 일반적으로 우선 순위 큐를 구현하는데 사용되며 우선 순위가 가장 높거나 낮은 요소에 효율적으로 엑세스 할 수 있다. 힙의 가장 일반적인 응용 프로그램은 ..