하미의 기술 블로그

💡 '서로 다른 개체가 연결되어 있다' or '여러 개의 도시가 연결되어 있다' ⇒ 그래프 알고리즘 그래프와 트리 속성 그래프 트리 방향성 방향 그래프 or 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 X O 노드간 관계성 부모와 자식 관계 X 부모와 자식 관계 O 모델의 종류 네트워크 모델 계층 모델 서로소 집합 union: 하나의 집합으로 합치는 연산 find: 특정한 원소가 속한 집합을 알려주는 연산 서로소 집합 알고리즘 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b):..

다익스트라 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 음의 간선이 없을 때 ex) GPS 그리디 알고리즘 매번 '가장 비용이 적은 노드'를 선택하기 때문 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산 → 최단 거리 테이블 갱신 5. 위 과정에서 3,4번 반복 방법1: 간단한 다익스트라 시간복잡도: O(V^2) import sys input = sys.stdin.readline INF = int(1e9) # 10억 n, m = map(int, input().split()) # 노드 개수, 간선 개수 start = int(input()) # 시작..

DP 사용 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 탑다운(Top-Down) 방식 # 피보나치 수열 with 재귀 함수 d = [0] * 100 def pibo(x): if x == 1 or x == 2: return 1 if d[x] != 0: return d[x] d[x] = pibo(x-1) + pibo(x-2) return d[x] 보텀업(Bottom-Up) 방식 # 피보나치 수열 with 반복문 d = [0] * 100 d[1] = 1 d[2] = 1 for i in range(3, 99): d[i] = d[i-1] + d[i-2] 파이썬 재귀 제한 완화 import sys sys.setrecursionlimit(10**6)..

순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 시간복잡도:O(N) 이진 탐색 배열 내부 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하는 방법 시간복잡도:O(logN) 재귀 함수로 구현한 이진 탐색 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, start, mid - 1) els..

정렬이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬 매번 가장 작은 것을 선택하여 맨 앞과 교체하는 방법 시간 복잡도: O(N^2) for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] 삽입 정렬 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 방법 시간 복잡도: O(N^2), 데이터가 정렬되어 있는 경우 O(N) for i in range(1, len(array)): for j in range(i, 0, -1..

탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조 스택 (Stack) 선입후출 (First In Last Out) / 후입선출 (Last In First Out) 파이썬에서는 list 자료형을 스택으로 사용할 수 있다. stack = [] stack.append(5) stack.pop() 큐 (Queue) 선입선출 (First In First Out) 파이썬에서는 deque을 사용해 큐를 구현하는 것이 가장 빠른 방법이다. from collections import deque queue = deque() queue.append(5) queue.popleft() 재귀 함수란? 자기 자신을 다시 호출하는 함수 파이썬 인터프리터는 호출 횟..

내장 함수 sum result = sum([1,2,3,4,5])# 15 min result = min(7,3,5,2)# 2 max result = max(7,3,5,2)# 7 eval result = eval("(3+5) * 7")# 56 sorted result = sorted([9,1,8,5,4])# [1,4,5,8,9] result = sorted([9,1,8,5,4], reverse=True)# [9,8,5,4,1] result = sorted([('홍길동', 35), ('이순신', 75), ('아무개', 50)], key=lambda x: x[1], reverse=True)# [('이순신', 75), ('아무개', 50), ('홍길동', 35)] sort - 내부 값이 바로 변경됨 data = ..