트리
이진 트리와 그 배열 표현이 주어지면 인덱스 idx(루트의 인덱스 0에서 시작)에 있는 노드는 다음을 갖습니다.
인덱스 2idx + 1의 왼쪽 자식
인덱스 2idx + 2의 오른쪽 자식
1
/ \
2 3
/| |\
4 5 6 7
- 루트(1)은 인덱스 '0'에 있습니다.
- 1(2)의 왼쪽 자식은 2*0+1 = 1 인덱스에 있습니다.
- '1'(3)의 오른쪽 자식은 '2*0+2 = 2' 인덱스에 있습니다.
- 또한 '2'(4)의 왼쪽 자식은 '2*1+1 = 3' 인덱스에 있습니다.
전위순회 preorder
- 현재 노드를 부모 노드로 생각했을 때 부모-> 왼쪽 자식 -> 오른쪽 자식 (직관적)
중위순회 inorder
-
현재 노드를 부모 노드로 생각했을 때 왼쪽자식-> 부모 -> 오른쪽 자식
-
정렬된 순서대로 값을 가져올때 사용
후위순회 postorder
-
현재 노드를 부모 노드로 생각했을 때 왼쪽자식-> 오른쪽 자식 -> 부모
-
트리 삭제에 유용!
집합
유니온
private static void union(int x, int y){
int root1 = find(x);
int root2 = find(y);
parent[root2] = root1;
}파인드
private static int find(int x){
if(parent[x]==x)
return x;
return parent[x] = find(parent[x]);
}그래프
인접 행렬 표현
- int[노드수][노드수]
인접 리스트 표현
- 노드의 개수만큼 배열 준비
- 배열의 인덱스는 각 시작 노드를 의미하며 값에는 ArrayList 연결
- ArrayList 에는 [정점,가중치] 넣기
노드
- 정점,가중치 묶어.
그래프 탐색
가중치 있거나 x,y 좌표 있을때 노드 소환 + dist 로 가중치 저장!! || 가중치 필요없으면 방문여부만 visited로 관리
양방향일 경우 체크!
DFS
준비물
1. 방문 여부 저장배열 boolean[] visited
2. 재귀로 풀면 stack 구현 필요없어
- 스택구조
- '다음에' 방문할 인접 노드를 push
- 탐색 후 되돌아옴
용도
- 가능한 '모든' 해를 찾는 백트래킹
- 사이클 감지
- 대부분의 탐색
BFS
- 큐
- '지금' 방문할 노드를 add
- 가중치X 그래프에서 최단경로 보장
준비물
1.최단거리면 int[] dist || 방문여부 배열 boolean[] visited
2.queue
- 2차원이면 dist 도 2차원 + Node로
용도
- 최단경로(미로)
- 네트워크 분석
- 여러답 중 가장 가까운 답 찾기
최단경로
다익스트라
- 음의 가중치에서는 불가.
준비물
0. 노드 클래스 구현 Node(dest,cost)
1. 인접 리스트 저장배열 ArrayList< Node>[] adList
2. 방문 여부 저장배열 boolean[] visited
3. 우선순위 큐 PriorityQueue< Node> pq
로직
-
while(노드 개수 -1)
-
(아직 방문하지 않은 노드 중) 최소 비용 노드선택 후 다른 곳까지의 경로 비용 vs 현재까지 구한 최소 비용으로 다른곳까지의 경로 비용 하나하나 비교.
- 바뀐 거 있으면 직전 노드, 최소 비용 바꿔.
-
1차원 리스트. 노드의 개수+1 로 크기 정하기.
벨만-포드
-
매 단계마다 모든 간선 가중치 다시 확인 -> 음의 가중치도 가능!
-
음의 사이클을 감지할 수 있음.
-
다익스트라와 같지만,
로직
- while(노드 개수 -1)
- 시작노드에서 갈 수 있는 각 노드에 대해 전체 노드 각각을 거치는 비용보다 최소 비용이 있는지 검사
- 있다면 음의 순환
- Ex) A에서 A,B,C,D,E 를 각각 검사.... B에서 A,B,C,D,E 를 각각 검사
ArrayList 변환
String[] 으로 변환
public String[] solution(String[] record) {
ArrayList<String> result = new ArrayList<>();
...
return result.toArray(new String[0]);
}
int[] 로 변환
public int[] solution(String[] genres, int[] plays) {
ArrayList<Integer> answer = new ArrayList<>();
return answer.stream().mapToInt(Integer::intValue).toArray();
}- 이는 Java 컬렉션이 원시 유형을 직접 저장할 수 없기 때문. 그렇기 때문에 toArray()불가능.
백트래킹
준비물
2차원일경우
- 불가능 검사 함수를 여러개두기
- Node 를 사용하기
정렬
ArrayList 정렬
Collections.sort(adj);Array 정렬
Arrays.sort(array);