트리

이진 트리와 그 배열 표현이 주어지면 인덱스 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

• 현재 노드를 부모 노드로 생각했을 때 왼쪽자식-> 오른쪽 자식 -> 부모

• 트리 삭제에 유용!

---

그래프

인접 행렬 표현

• int[노드수][노드수]

인접 리스트 표현

1. 노드의 개수만큼 배열 준비
2. 배열의 인덱스는 각 시작 노드를 의미하며 값에는 ArrayList 연결
3. ArrayList 에는 [정점,가중치] 넣기

노드

• 정점,가중치 묶어.

그래프 탐색

DFS

• 스택구조
• '다음에' 방문할 인접 노드를 push
• 탐색 후 되돌아옴

용도

• 가능한 모든 해를 찾는 백트래킹
• 사이클 감지
• 대부분의 탐색

준비물

• 방문 여부를 저장할 boolean 배열
• 재귀로 풀면 stack 구현 필요없어

BFS

• 큐
• '지금' 방문할 노드를 add
• 가중치X 그래프에서 최단경로 보장

용도

• 최단경로(미로)
• 네트워크 분석
• 여러답 중 가장 가까운 답 찾기

최단경로

다익스트라

• 음의 가중치에서는 불가.

준비물

• 최소 비용 저장 공간
• 직전 노드 저장 공간
• 우선순위 큐

로직

• 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()불가능.