python14 [LEET CODE 150] - 238 Product of Array Except Self LeetCode의 238번인 "Product of Array Except Self" 문제를 풀어봤다 문제를 간략히 살펴보자.정수로 이루어진 배열이 주어지는데, 이때 해당 인덱스에 자신을 제외한 다른 모든 값을 곱한 값으로 대체하라는 것이다.위의 예제 1번에서 보는 것처럼 첫번째 index에 첫번째 index에 해당하는 값 1을 제외한 나머지 값들 (2, 3, 4)을 모두 곱한 값을 업데이트 하라는것이다.이 문제는 어렵진 않지만 몇 가지 제한조건이 있다.우선 배열의 길이는 2 ~ 105 사이여야 하며, 배열 안 정수는 -30 ~ 30 사이여야 한다.특히 가장 중요한 제한조건은 O (n)의 time complexity를 가져야 한다는 것이다.또한 나누는 연산 또한 할 수 없다.이제 문제를 풀어보자. 정답 코.. 2026. 1. 26. [LEETCODE 150] - 380 Insert Delete GetRandom O(1) 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은 특정 정수를 리스트 내의 인덱스와 매핑하여 저장하는 딕셔너리 이다... 2026. 1. 25. [LEETCODE 150] - 274 H-Index 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(논문 수)을 넘을수 없고, 인용.. 2026. 1. 22. 10 - BFS BFS(Breath-First Search), 너비우선 탐색 방식 1. BFS란? 너비 우선 탐색(Breadth-first search, BFS)는 맹목적 탐색 방법 중 하나로 시작 정점(vertex)을 방문한 후 인접한 모든 정점들을 우선으로 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때 까지 방문하지 않은 정점들에 대해서도 너비 우선 탐색을 적용하고, 일반적으로 queue 자료 구조를 이용해서 순차적으로 접근이 가능하도록 구현이 가능하다. Tree상에서 BFS로 탐색을 진행하는 경우에는 cycle이 생기는 경우가 없지만, graph에 BFS를 적용하는 경우에는 cycle이 있을 수 있기 때문에 무한 루프에 빠지는 것을 방지하기 위해서 방문 표시를 하면서 탐색을 진행해야 한다. 2. BFS.. 2026. 1. 22. [LEETCODE 150] - 45 Jump Game II 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]) -.. 2026. 1. 21. [LEETCODE 150] - 55 Jump Game 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])로 구할 수 있다. 즉, 이전 칸에서 .. 2026. 1. 21. 이전 1 2 3 다음
