알고리즘
1.[알고리즘] 트리, 최소 스패닝 트리, 크루스칼 알고리즘(백준 1197)
노드와 에지로 연결된 그래프의 특수한 형태순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.트리의 부분 트리 역시 트리의 모든 특징을 따른다.트리에서 임의의 두 노드를 이어주는 경로는 유일하다.그래프로
2.[알고리즘] 다익스트라(백준 1916)
시작점에서 종점까지의 최단 경로를 찾는 알고리즘 시작점, 종점이 확실하게 정해져 있어야 함 현재까지 가중치 + 추가 가중치 합산이 목적지의 가중치 합산 값보다 작을 때만 갱신한다. 간선의 가중치가 음이 아닌 경우에만 사용 가능하다 음의 가중치 : 벨만-포드 알고
3.[알고리즘] 완전이진트리 / 힙 자료구조
완전이진트리 왼쪽부터 차례로 빈 곳 없이 채워진 이진트리 인덱스 표시 가능 | index | 1 | 2 | 3 | 4 | 5 | 6 | |-------|---|---|---|---|---|---| | - | 3 | 2 | 4 | 5 | 0 | 1 | 규칙
4.[알고리즘] 그리디(백준 1715)
탐욕법현재 상태에서 계속 BEST를 선택 ➡️전체 선택 중 BEST라고 가정하는 알고리즘⚠️ 항상 최적의 해를 보장하지는 않는다.그리디로 풀어도 되는지 안되는지 판단하는 것이 중요하다.최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 한다.ex) 거스름 돈 문제해
5.[알고리즘] 이진 탐색
순차 탐색 : 앞에서부터 데이터를 하나씩 확인이진 탐색 : 탐색 범위를 절반씩 좁혀가며 탐색정렬된 상태에서 시작O(logN)입력이 말도 안되게 큰 편예: 업다운 게임bisect_left(a, x) : 정렬 순서 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환b