소피it블로그

자료 출처: https://youtu.be/5Lu34WIx2Us 이전까지는 다이나믹 프로그래밍이 뭔지 아예 모르고 이름만 많이 들어봤었는데, 이 강의 덕에 개념이 잡혔다. 문제를 아주 많이 풀어봐야 할 것 같다. 1. 다이나믹 프로그래밍 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법으로, 이미 계산된 결과는 별도의 메모리 영역에 저장한다. 조건 최적 부분 구조 (Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있는 경우. 즉, 작은 문제의 답을 모아 큰 문제를 해결할 수 있음 중복되는 부분 문제 (Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결해야 함 다이나믹 프로그..

자료 출처: https://youtu.be/AjFlp951nz0 1. 우선순위 큐 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 단순히 리스트를 이용하여 구현하는 방식: 삽입시 O(1), 삭제시 O(N)의 시간복잡도 힙(heap) 자료구조를 이용하여 구현하는 방식: 삽입, 삭제시 각각 O(logN)의 시간복잡도 2. 힙 (Heap) 완전 이진 트리의 일종인 자료구조로, 항상 루트 노드를 먼저 제거한다. 최소 힙 (Min Heap) 루트 노드가 가장 작은 값을 가짐 값이 작은 데이터가 우선적으로 제거됨 따라서 최소 힙에 넣었다 빼면 오름차순으로 정렬됨(작은 데이터부터 제거되므로) 최대 힙 (Max Heap) 루트 노드가 가장 큰 값을 가짐 값이 큰 데이터가 우선적으로 제거됨 따라서 최대 힙에 ..

자료 출처: https://youtu.be/94RC-DsGMLo 1. 이진탐색이란? 정렬되어 있는 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방식으로 동작하는 알고리즘 시작점, 끝점, 중간점을 이용한다. 시간 복잡도: O(logN) 재귀 또는 반복문을 이용하여 구현할 수 있다. 이하는 재귀를 이용하여 푸는 법. # 재귀 방식으로 구현 def binary_search(arr, target, start, end): if start > end: return None mid = (start + end) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search(arr, target, mid + 1, ..

https://leetcode.com/problems/flood-fill/ Flood Fill - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 분명 어려운 문제는 아닌데 아직도 bfs에 완전히 익숙해지지가 않아서 꽤 헤맸다. 특히, dx, dy로 리스트를 만들어놓고 다른 노드를 방문하는 방법이 아직 익숙하지 않아 우선은 중복되고 장황한 while문을 썼다. 또한, 처음에는 visited 리스트를 따로 만들려고 했으나, 풀다보니 굳이 그럴 필요 없이 방문한 곳의..

https://leetcode.com/problems/binary-tree-inorder-traversal/ Binary Tree Inorder Traversal - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 아직도 dfs-재귀 코드를, 개념적으로는 알겠는데 직접 구현해내는 것은 어렵다. 자꾸 삐걱거리고 이상한 살을 붙여버린다고 해야 할까. 재귀의 끝부분이 완전히 이해되지는 않는 느낌이다. 많이 풀다 보면 나아지려나. class Solution: def in..