소피it블로그

자료 출처: https://youtu.be/acqm9mM1P6o 동빈북을 사두고 생각보다 어려워서 많이 못 봤는데, 이 강의 시리즈를 보다보니 이해가 쉽게 가고 재밌어서 대강 쭉 봤다. 요즘 블로그에 정리하는 내용들도 강의 요약본이나 마찬가지인데, 어려운 알고리즘들은 계속 읽어보며 완전히 이해가 될 때까지 못 넘기겠어서 하나하나 코멘트를 다는 중. 투머치이긴 하지만 내가 이해하기 위한 것이기 때문에 그냥 적으려 한다. 1. 최단 경로 알고리즘 개요 한 지점에서 다른 한 지점까지 한 지점에서 다른 모든 지점까지: 다익스트라 알고리즘 모든 지점에서 다른 모든 지점까지: 플로이드 워셜 알고리즘 이 때 각 지점은 노드로, 지점 간을 연결하는 도로는 간선으로 표현한다. 2. 다익스트라 최단 경로 알고리즘 특정 노..

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

자료 출처: https://youtu.be/i5yHkP1jQmo 1. 트리 계층적인 구조를 표현할 때 사용할 수 있는 자료구조로, 다음과 같은 요소를 갖는다. 트리의 크기가 n일 때 전체 간선의 수는 n-1 개이다. 루트 노드 (root node) 단말 노드 (leaf node) 크기 (size): 트리에 포함된 모든 노드의 개수 깊이 (depth): 루트 노드부터의 거리 높이 (height): 깊이 중 최댓값 차수 (degree): 각 노드의 자식방향의 간선의 개수 2. 이진 탐색 트리 (Binary Search Tree) 이진 탐색을 쉽게 할 수 있게 해주는 트리로, 다음을 만족한다. 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 데이터의 조회 과정은 다음과 같다. 루트 노드부터 방문하여 탐색을..

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