전체 글
Dijkstra Algorithm
Dijkstra {{}} 특정 시작점에서 다른 모든 정점으로 가는 최단 거리를 각각 구해주는 알고리즘 {{}} A도시에서 D도시로 가는 최단 비용(거리, 시간, 돈)을 구하는 문제에 적합한 알고리즘. ⚠️ 음수 가중치 간선이 있는 그래프에서는 쓸 수 없다. 시간복잡도 우선순위 큐⭕️ O(ElogV) 우선순위 큐❌ O(V^2) 구현 import heapq INF = int(1e9) def dijkstra(start): queue = [] heapq.heappush(queue, (0, start)) distance[start] = 0 while queue: dist, node = heapq.heappop(queue) for v, c in graph[node]: cost = dist + c if cost < ..
Kruskal Algorithm
MST Spanning Tree: 최소한 간선을 사용하여 그래프 내 모든 정점을 이은 트리(트리는 사이클이 없다는거 주의) n개의 정점에 n-1개의 간선이 존재하는 그래프는 트리 가중치가 있는 그래프에서 최소 비용을 사용하면 Minimum Spanning Tree Union-Find 특정 원소들을 합칠때 이들이 같은 집합에 포함되어 있는지 확인하거나 두 집합을 합칠때 사용한다. Kruskal Algorithm 최소비용 간선을 선택해나간다. 이때 사이클이 발생하지 않도록 하는데 그 과정에서 Union-Find를 사용하면 사이클이 발생하는지 체크할 수 있다. 간선의 가중치가 작은 것부터 순서대로 보면서 해당 간선 양 끝에 있는 두 노드 x, y에 대해 find(x), find(y)값을 비교하여 일치하지 않는..
Prim Algorithm
Prim Algorithm 크루스칼이 최소비용 간선을 선택해 나간다면, 프림 알고리즘은 최소비용 간선이 있는 정점을 선택해 나간다. 시간복잡도 우선순위 큐 O(ElogV) 인접행렬 O(V^2) 구현 import heapq INF = int(1e9) def prime(start): queue = [] heapq.heappush(queue, (0, start)) distance[start] = 0 while queue: dist, u = heapq.heappop(queue) for v, c in graph[u]: if c < distance[v]: distance[v] = c n, m = map(int, input().split()) # 노드, 간선 개수 start = int(input()) # 출발 노드 ..
Tree
트리 🌲 정점끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프 ⬆️위와 같은 가계도 모양을 생각하면 노드는 가문의 각 구성원이며 왜 상위 노드를 부모 노드, 하위 노드가 자식 노드라고 불리는지 쉽게 이해할 수 있다. 이 예시로 트리 용어들을 일상적으로 비유해 본다면 루트 노드는 가문의 선조, 차수는 각 구성원에서 뻗어나간 가지 수로 몇 명의 자식이 있는지, 깊이는 현재 구성원이 선조로부터 몇 세대 내려왔는지, 높이는 마지막 후손의 깊이이다. 이진 트리 🌲 자식 수가 최대 2개인 트리 이진트리 탐색 전위 탐색: 부모 - 좌 - 우 중위 탐색: 좌 - 부모 - 우 후위 탐색: 좌 - 우 - 부모 이진탐색트리 왼쪽 방향에 있는 노드들은 전부 부모 보다 값이 작아야 함 우측 방향에 있는 노드들은 전부 ..
Git 기본 활용
공식문서 누구나 쉽게 이해할 수 있는 Git 입문 git 개념 버전 관리? 파일의 변화를 시간에 따라 기록했다가 필요한 경우 특정 시점의 버전을 다시 꺼내올 수 있는 시스템 중앙집중식 버전 관리(CVCS) 중앙 서버에 문제가 생기면 협업 불가 분산 버전 관리 시스템(DVCS) 로컬 저장소가 원격 저장소의 파일, 히스토리 모두 복제 -> 백업 유리 git 기본 Repository: local - remote 원격 저장소 연결 git clone :원격 저장소 받아오기 git remote add origin 원격저장소주소 upstream 저장소 설정 git remote add upstream 저장소 : 포크한 저장소의 원본 저장소 연결 git remote set-url **upstream** 원격 저장소 확인..
Linked List
연결 리스트 연결된 데이터를 저장할때 사용합니다. 연결리스트를 구성하는 노드의 구조는 다음과 같습니다. node data link(next) 장점단점 삭제와 삽입 O(1) 길이가 정해지지 않은 데이터를 다룰때 유용 메모리 요구량이 더 크다 원하는 위치 검색할 때 처음부터 다 확인해야한다 배열과 비교 배열연결리스트 삽입/삭제 O(n) O(1) 저장공간 연속한 위치 임의의 위치 탐색 O(1) O(n) 단순 연결 리스트 구현 노드 class Node: def __init__(self, item): self.data = item self.next = None 연결 리스트 class LinkedList: def __init__(self): self.nodeCount = 0 # 노드의 개수 self.head = N..
리모트에 올린 커밋 취소 or 되돌리기
요즘 번역 오픈소스 프로젝트를 하다보니 커밋하고 나서 보이는 오타들이 있었다. 하지만 글자 하나 때문에 새로 커밋 올리는 것은 깔끔하지 않다고 생각되고 어떤 오픈소스 프로젝트에서는 불필요한 커밋은 합쳐서 올리기를 요청하기도 한다고 했다(기본인가..?)🤔 이럴땐 커밋 취소, 되돌리기, 덮어쓰기를 상황에 맞게 사용하자. git log --oneline 현재 커밋 로그를 조회해서 어느 지점 커밋으로 되돌리고 싶은지 확인한다. 8d9111b (HEAD -> ddp_pipeline, origin/ddp_pipeline) 커밋4 cedfd58 커밋3 f0780f0 커밋2 b908557 커밋1 ✅ 이미 올라간 커밋을 바꾸고 싶다! 어떻게? 방법1 커밋 취소하기:git reset --soft HEAD^ 로컬 저장소 상..