08-1 그래프의 표현

에지 리스트

에지 리스트는 에지를 중심으로 그래프를 표현.

가중치 없는 그래프 표현하기

배열의 행 2개면 충분

만약 방향이 없으면 2차원 만들고 시작노드로 두지 않고 1,2 / 2,1 양쪽으로 다룰 수 있음

가중치 있는 그래프 포현하기

행을 3개로 S, E, V로 하면 됨

대부분 그래프 input은 시작, 종료, 가중치로 표현한다.

에지 리스트는 에지를 중심으로 표현해서 노드 관련 되어 있는 에지 탐색은 쉽지 않다. - 벨만포드

인접행렬

2차원배열 료구조 사용해서 그래프 표현 N = [n][n]

가중치 없는 그래프 표현하기

행과 열이 만나는 곳에 1로 표현

가중치 있는 그래프 표현하기

굉장히 간단하지만 풀수있는걸 잘 판단해야함. 시간복잡도가 좋지 않음. 에지리스트보다는 낫지만 ㅂㄹ . 공간 효율성도 떨어짐. 노드가 작을 때 써야함. 행과 열 만나는 곳에 가중치 표현

인접 리스트 ★★★

인접리스트 adjacency list는 Arraylist 로 그래프를 표현 노드 개수만큼 Arraylist를 선언.

가중치 없는 그래프 표현하기

ArrayList<Integer>[5] 어레이리스트 “배열”로 선언!!! 가중치 ㄴㄴ

Arraylist 리스트 자료형은 배열과 다르게 가변적이다.

A[3]이렇게 배열의 장점이 나온다. 인덱스를 통해 직접 접근이 가능!!! A[3].add(4)

가중치 있는 그래프 표현하기★★★

실제 코테에서 가중치 없는거 거의 ㄴㄴ

ArrayList<Node>[N] ⇒ class Node S 넣어주는 것다

class Node{int E, int v}

A[3] 시작노드 써주고 .add(객체생성해서 넣어줌 new Node(4, 13))

복잡한게 굳이 왜 쓸가?

구현은 복잡 그러나 노드와 연결된 에지를 탐색하는 시간이 매우 뛰어남 → 시작노드를 배열의 형태로 선언

인접행렬은 쓸데없이 빈공간을 탐색 but 인접리스트는 빈공간없이 꽉차다. 시간복잡도 뛰어나고 빈공간도 없어서 메모리 초과도 발생하지 않음

2. 오늘의 문제 : Shuttle the arry

https://leetcode.com/problems/shuffle-the-array/

15분만에 풀라고해서 완전 허겁지겁 풀었어요

3. 풀이

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] arr = new int[2*n];
        for(int i = 0; i < n; i++){
            arr[2*i] = nums[i];
            arr[2*i+1] = nums[i+n];
        }
        return arr;
    }
}

3. 회고

코딩테스트 시험 대비에 맞추어 시험장 테스트를 해보았는데 문제 3개를 풀었습니다. 시간이 부족했지만 마지막에 이진탐색을 이용해 풀면되겠다는 생각이 들었어요! 이런 상황 너무 뿌듯하다.. 내가 공부한 것이 생각나서 그걸 응용하는 과정이 너무 좋았습니다. 지금까지 매일 문제를 풀었지만 온전히 스스로 푼 문제는 몇 문제 되지 않았거든요.. 혼자 골머리 앓다가 남의 코드 보고 풀었었는데 그래도 실전에서 기억이 나 풀 수 있으니 너무 뿌듯했고 앞으로 더 열심히 공부할 동기를 얻은 것 같습니다.