wooomr2 / coding-test Goto Github PK

1.visited 리스트 생성
2.연결 상태 리스트 생성
3.시작 노드를 리스트에 담기
4.노드를 꺼내고 연결 노드를 담기
5.이 때 노드를 어떻게 꺼내냐에 따라 DFS/BFS가 나뉨
(DFS : Stack 사용 // BFS : Queue 사용)

1. 정렬된 데이터가 있다. (정렬된 데이터를 잘 고르는 게 중요) -> 시간
2. 정렬된 데이터와 상관관계가 있는 상태(값)이 존재한다. -> 그 정렬된 데이터로부터 방향성을 가진 상태를 찾을 수 있어야 함
3. 정렬된 데이터의 적정값을 찾거나 최대/최소값을 구해야 한다. -> 조건을 만족하는 처리 인원 수를 만드는 적정 시간

선형 구조 -> 순차탐색:  반복문 사용
비선형 구조 -> 그래프 (DFS, BFS)

[
    [0,1,0],
    [1,0,1],
    [0,1,0]
]

- 각 노드마다 대응되는 배열이 있으며 모든 노드에 대한 연결 상태를 표현
- 두 노드가 연결되어 있는지 확인하는 것이 빠름
- 특정 노드와 연결된 모든 노드를 찾는 건 느림 (간선이 많을수록 유리)
- 많은 메모리 사용 (고정된 n^2 만큼의 메모리 필요)

[
    [1],
    [0,2],
    [1]
]

- 각 노드마다 대응되는 리스트가 있으며 연결된 노드만 표현
- 두 노드가 연결되어 있는지 확인하는 것이 느림
- 특정 노드와 연결된 모든 노드를 찾는 건 빠름 (간선이 적을수록 유리)
- 필요한 메모리 사용

[
    [0,1],
    [1,2]
]

- 엣지만 표현
- 간선 위주로 문제를 풀어가는 크루스칼 알고리즘에서 사용

1. 임의의 정점 선택
2. 인접 정점 중 최소 비용의 간선을 가지는 정점 선택
3. 여기서 인접 정점은 신장 트리와 연결된 모든 정점이 대상
4. 2를 반복

1. 가중치에 따라 간선을 오름차순 정렬
2. 가중치가 낮은 간선부터 추가
3. 만약 사이클이 만들어지는 간선이면 Pass (상호 배타 집합 활용)
4. 2를 반복

# 상호배타집합
def make_set(x):
    p[x] = x

def find_set(x):
    if p[x] != x:
        p[x] = find_set(p[x])
    return p[x]

def union(x, y):
    p[find_set(y)] = find_set(x)

1. 중점으로 거리를 모두 최대값으로 초기화
2. (아직 선택되지 않은 정점 중) 중점으로부터 거리가 최소인 정점을 선택
3. 선택한 가장 가까운 정점을 방문해서 다른 정점으로 가는 경우의 수를 비교해서 최단 거리 갱신
4. 2, 3 반복