알고리즘 관련 단어

BFS, DFS는 반드시 알아놔야 한다.

하드코딩으로 문제를 해결할 수 있다 하더라도 시간복잡도에서 걸러지기 마련이다.

 

DFS (Depth-First Search)

• 한 가지 경우를 검증하고 아니면 돌아가는 방식이다.
• 스택, 재귀함수 이용 / 그래프 구조, 미로 찾기 유용
• visited 리스트를 만들어서 방문한 노드를 저장한다
• DFS를 최단거리에서 사용하지 않는 이유
  • 목적지와 반대방향이더라도 끝까지 탐색하기 때문에

 

 

 

BFS (Breadth-First Search)

• visited 리스트를 만들어서 방문한 노드를 저장한다
• 큐 이용 / 최단 경로 찾기 유용
• 가중치가 없는 간선, 최단거리 문제에 이용
• 가중치가 있는 간선에서 BFS를 쓰지 않는 이유
  • BFS가 Greedy한 알고리즘이 아니기 때문이다

 

다익스트라(Dijkstra) 알고리즘

•  

 

인접행렬       

 

 

인행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식이다. 인접 행렬을 adj[][]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의할 수 있다.

 

adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

 

cf) 만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현할 수 있다.

 

2) 예시

간단한 예시를 통해 이해해보도록 하겠습니다. 다음과 같은 그래프가 있는 경우, 이 그래프의 연결 관계를 인접 행렬로 나타낸다면 인접 행렬은 다음과 같다.

 

 

 

모든 노드들 사이의 관계를 1(이어져있다), 0(안 이어져있다)로 표시한다. 그러기 때문에 정점의 개수가 n이라면 n*n의 크기이다.

장점 

• 두 정점을 연결하는 간선을 조회할 때 O(1) 시간복잡도로 가능하다.

단점:

• 메모리 공간이 낭비된다. n²
• 그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n²)의 시간이 소요된다.

 

인접리스트      

인접 리스트는 그래프의 연결 관계를 연결리스트(Linked List) , vector의 배열(vector<int> adj[])로 나타내는 방식입니다. 이 때, vector<int>에는 노드의 번호가 직접 저장됩니다. 인접 리스트는 adj[i](vector의 배열이기 때문에, adj[i]는 vector가 되겠죠?)를 다음과 같이 정의할 수 있습니다.

예시

 

장점: 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 보다 효율적이다

단점: 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간이 필요하다.

사진 출처: https://suyeon96.tistory.com/32

 

가중치 그래프 (weighted Graph)

연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다. 간선 자체가 정보가 생겼다는 의미입니다.

ex. 서울-부산으로 가는 거리 

 

비가중치 그래프 (unweighted Graph):

연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.

ex) 사람관계도

 

이분탐색

정렬되어 있는 배열에서 원하는 조건(해당 값보다 작은 수의 개수)을 찾는 것은 이분탐색 이용하기 

 

이분탐색 코드

            int total = 0;

    		int a = 36;
             int left = 0;
             int right = ints.size();
				
                while (left + 1 < right) {
                    int mid = (left + right) / 2;

                    if (a > ints.get(mid)) {
                        left = mid;
                    } else {
                        right = mid;
                    }
                
				}
                total += left;

https://school.programmers.co.kr/questions/66170?referer=collection-of-questions

 

백트래킹

DFS의 한종류이다. 자식노드의 탐색이 끝나면 인접 자식노드들을 탐색하기 위해 부모노드로 돌아간다고 해서 백트래킹이라고 부른다.