Gaegul's devlog

1) 트리 (Tree) 란? 트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 2) 이진 탐색 트리 (Binary Search Tree) 란? 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종. 이진 탐색 트리의 특징 : 왼쪽 < 부모 < 오른쪽 부모 노드보다 왼쪽 자식 노드가 작습니다. 부모 노드보다 오른쪽 자식 노드가 큽니다. 3) 트리의 순회 (Tree Traversal) 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법. 트리 순회 방법 종류 전위 순회 (pre-order traverse) : root - left -right 중위 순회 (in-order traverse) : left - root - right 후위 순회 (po..

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미. 1. 다양한 문제 상황 1) 한 지점에서 다른 한 지점까지의 최단경로 2) 한 지점에서 다른 모든 지점까지의 최단경로 3) 모든 지점에서 다른 모든 지점까지의 최단경로 - 각 지점은 그래프에서 노드로 표현. - 지점 간 연결된 도로는 그래프에서 간선으로 표현. 2. 알고리즘 동작 과정 1. 출발 노드를 설정. 2. 최단거리 테이블을 초기화. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 (weight)를 선택. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다. But! 총 O(V)번에 걸쳐서 최단거리가 가장 짧은 노드를 매법 선형 탐색해야 한다. 따라서 전체 시간 복잡도는 O(V2) 이다...

탐색 알고리즘에는 크게 1. 이진 탐색 2. BFS 3. DFS가 있다. 이번 챕터에서는 이진 탐색에 관해 알아볼 것다. 이진 탐색 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 부터 차근히 확인하는 방법. 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법. 재귀문 구현 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 #찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid elif array[mid] > target: return binary_search(array, target,..

1. DFS (Depth-First-Search) 스택 자료 구조 이용하거나 재귀 함수를 이용. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 ㅇ낳은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 3. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복. #DFS 메소드 정의 def dfs(graph, v, visited): visited[v] = True print(v, end = '') #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) #각 노드가 연결된..

Greedy 알고리즘 ? 1. 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 2. 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 3. 정당성 분석이 중요. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토. 문제 . 1이 될때까지 n , k = map(int, input().split()) # N = 25, K = 3 res = 0 while True: #시간 복잡도 : O(log(n)) target = (n // k) * k res += (n - target) n = target if n < k : # 더이상 나눌 수 없으면 종료 break res += 1 # 횟수 count n //= k # 마지막으로 남은 수에 대해 1씩 빼기 res += (n..

DP(동적계획법)란? - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법. - 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 일반적으로, 구현 방식은 탑다운(Top-down)과 보텀업(Bottom-up) 방식으로 구성된다. 1. DP 를 사용할 수 있는 조건 1) 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2) 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 함. 2. DP 종류 1) 탑다운 방식 : 메모이제이션 (Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하..

연결 리스트는 가장 대표적인 선형 알고리즘. 효율적으로 풀기 위해서 첫번째 방법은 deque를 이용하여 최적화 시킬 수 있다. 동적 배열로 구성된 리스트는 맨 앞 아이템을 가져오기에 적합한 자료형이 아니다. 왜냐하면 첫번째 값을 꺼내오면 모든 값이 한 칸씩 shifting되며, 시간 복잡도도 O(n) 가 발생한다. 파이썬의 deque는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는 데 시간 복잡도 O(1)에서 실행된다. 두번째 방법은 런너를 이용하는 것이다. 순서에 따라 2개의 런너, 빠른 런너와 느린 런너를 각각 출발 시키면, 빠른 런너가 끝에 다다를 때 느린 런너는 중간 지점에 도달하게 된다. 그럼 느린 런너는 중간까지 이동하면서 역순으로 연결 리스트 rev를 만들어 나간다. 이제 중간에 도달한 ..

문제. 두수의 합 [2, 7, 11, 15] 가 input으로 들어갔을 때 sum = 9가 되는 두 숫자의 인덱스를 리턴하여라. 풀이 1. 브루트 포스로 계산 모든 경우의 수를 다 확인하는 방법. 매우 비효율적. for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + num[j] == target: return [i,j] 풀이 2. in을 이용한 탐색 모든 조합을 비교하지 않고 정답, 즉 타겟에서 첫 번째 값을 뺀 값 target - n이 존재하는지 탐색. for i, n in enumerate(nums): complement = target - n if complement in nums[i+1]: return [nums.index..