소피it블로그

자료 출처: 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/add-two-numbers/ Add Two Numbers - 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 아주 간단한 링크드 리스트 문제인데, 나는 링크드 리스트에 대한 개념 정도만 있지 실제로 구현해서 문제풀이에 사용해본 경험은 거의 없었기 때문에 이 문제로도 꽤나 많은 오류를 거쳤다. 애초에 문제 자체는 연결 리스트를 숫자로 바꿔서 더한 후 다시 연결 리스트로 바꾸라는 의도는 아니었던 것 같으나, 나는..

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..

https://leetcode.com/problems/evaluate-reverse-polish-notation/ Evaluate Reverse Polish Notation - 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 스택에 관한 기본적인 문제로, 크게 어렵지는 않았으나 음수를 고려 못하고 .isnumeric()을 써댄 탓에 꽤 헤맸다. 다른 답안 찾아다 놓고 일일이 한줄씩 고쳐가면서 간신히 오류를 파악함. 또한, 흥미롭게도 stack.append(toke..