TIL (2022.04.02)

1. 그래프

정점 (Vertex) = 노드
간선 (Edge) = 정점과 정점을 잇는 선

간선에 값이 적혀 있는 경우도 있고, 없는 경우도 있음
-> 값이 있을 경우 = 간선의 가중치

특정 정점과 연결된 정점의 수 = 차수 (Degree)

인접 행렬의 경우 )
a정점과 b정점이 연결되어 있는 가? = O(1)
특정 정점과 연결되어 있는 모든 정점 = O(|V|)

인접 리스트의 경우)
a정점과 b정점이 연결되어 있는 가? = O(min(degree(a),degree(b))
특정 정점과 연결되어 있는 모든 정점 = O(degree(a))

2. DFS & BFS

Depth First Search = 깊이 우선 탐색
깊게 탐색하고 나서 이전과정으로 돌아간다.
스택으로 구현

Breadth First Search = 너비 우선 탐색
해당 노드 먼저 방문 후 그 다음에 이웃한 노드 방문.
큐로 구현
가장 짧은 방법의 길이 구하기에 사용 가능

이론 상으로 성능은 별 차이 나지 않음.

3. 선택 정렬

1. 전체 값에서 가장 작은 값 찾기
2. 그 값을 첫번째에 배치
3. 첫번째 값을 제외하고 가장 작은 값 찾기
4. 그 값을 두번째에 배치
   이런 과정을 반복해서 정렬하는 것

선택 정렬의 경우에는 O(n^2)의 시간 복잡도를 가짐
첫 회전 : 1~n-1
두번째 회전 : 2~n-1

(n-1)+(n-2)+...+2+1 => n(n-1)/2 = O(n^2)

#include <iostream>
using namespace std;

int main(){
    int n;
    cin>>n;

    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    for(int i=0;i<n-1;i++){
        int minVal=i;
        for(int k=i+1;k<n;k++){
            if(arr[minVal]>arr[k]){
                minVal=k;
            }
        }

        int temp=arr[i];
        arr[i]=arr[minVal];
        arr[minVal]=temp;
    }

    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}