Home 시간복잡도 알고리즘 DFS/BFS에 대해서
Post
Cancel

시간복잡도 알고리즘 DFS/BFS에 대해서

Posted Aug 19, 2023
By lgm1995
7 min read

시간복잡도와 DFS/BFS에 대해서

오늘은 시간 복잡도 알고리즘에 대해서 공부한 내용을 정리해보려 한다.

시간복잡도란?

시간복잡도

입력값에 변화에 따른 연산 횟수에 비해 걸리는 시간

시간 복잡도에 대해서 표기하는 방식은 주로 빅-오 표기법을 사용하는데 이는 최악, 최선, 평균치의 경우에 대해 시간 복잡도를 나타내는 방법이다.

관련하여 좋은 기술 블로그 들이 많으니 참고하기 바란다.

다만 주의할 점은 시간 복잡도는 로직의 반복횟수를 중점으로 둔다.

그 이유는 어떠한 로직이 수행되는 하드웨어는 성능에 따라 걸리는 시간이 다를 수 있기 때문이다.

내가 참고한 블로그 </br> https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/ —

그래프 탐색

알쏭 달쏭 프로그래밍 세상은 너무 어려운 말들이 가득하다.

이따 설명하게 될 DFS / BFS 는 그래프 탐색이라고 불린다.

그래프 탐색이란 쉽게 말해 그래프에 있는 특정 개체를 찾기 위해 모든 방법을 탐색하는 알고리즘을 말한다.

깊이 우선 탐색은 루트노드에서 부터 다음 분기점을 거치기 전에 모든 분기를 완벽하게 탐색하는 기법이다…

쉽게 말하면 결과가 나올때 까지 한놈만 팬다…

한놈만패

그렇기 때문에 재귀함수를 호출하여 하나의 조건에 대한 모든 결과를 만든 후에 다음 조건에 부합하는 탐색을 시작한다.

예를 들어 더하거나 빼서 값을 찾아야 하는 경우에는 모든 경우를 더한 경우의 수부터 시작하여 모든 경우를 뺀 결과까지 진행되는 알고리즘이다.

그렇기 때문에 결과를 찾는 속도가 편차가 클 수 있다.

프로그래머스의 코딩테스트 연습 문제 타겟 넘버를 DFS로 풀이한 코드이다.

문제는 n개의 정수 배열이 들어왔을 때 각각의 배열의 인자를 더하거나 빼서 원하는 target의 값을 몇번 도출할 수 있는지 리턴하는 문제이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
  int answer;
  int target;
  int[] numbers;

  void dsf(int index, int sum) {
    if (index == numbers.length) {
      if(sum == target) answer++;
      return;
    }
    dsf(index+1 , sum + numbers[index]);
    dsf(index+1 , sum - numbers[index]);
  }
  public int solution(int[] numbers, int target) {
    answer = 0;
    this.numbers = numbers;
    this.target = target;
    dsf(0,0);
    return answer;
  }
}

코드의 내용을 설명하면 dsf라는 재귀함수를 만들고 배열의 인덱스를 돌며 더하는 경우와 빼는 경우를 재귀함수로 반복호출하여 결과를 도출하는 방법이다.

이 코드는 더하는걸 우선으로 재귀함수를 호출하기 때문에 모든 수를 더하는 방법부터 시작하여 마지막엔 모든 수를 다 빼보는 방법으로 연산이 마무리 된다.

넓이 우선 탐색은 루트 노드부터 시작해서 모든 인접한 노드를 먼저 탐색하는 방법이다.

쉽게 말하면 한번씩 때린다…

가까운 노드 부터 탐색을 하기에 순서가 보장되어야 한다.

큐를 이용한 넓이 우선 탐색 알고리즘의 순서는 이렇다.

  1. 루트 노드부터 시작점을 정한다.

  2. 루트노드와 인접하며 방문하지 않은 노드를 큐에 저장한다.

  3. 큐에서 루트노드와 인접하고 방문된적 없고, 큐에 저장되지 않은 노드를 Queue에 넣는다. Queue에서 dequeue하여 가장 먼저 큐에 저장한 노드를 방문한다 내가 참고한 블로그 </br> https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

프로그래머스 코딩테스트 문제인 게임 맵 최단 거리에 대한 풀이이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import java.util.*;

class Solution {

    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};

    public int solution(int[][] maps) {
        int answer = 0;

        int[][] visited = new int[maps.length][maps[0].length];

        bfs(maps, visited);
        answer = visited[maps.length-1][maps[0].length-1];

        if(answer == 0){
            answer = -1;
        }

        return answer;
    }

    public void bfs(int[][] maps, int[][] visited){
        int x = 0;
        int y = 0;
        visited[x][y] = 1;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});

        while(!queue.isEmpty()){
            int[] current = queue.remove();
            int cX = current[0];
            int cY = current[1];

            for(int i = 0; i < 4; i++){
                int nX = cX + dx[i];
                int nY = cY + dy[i];

                if(nX < 0 || nX > maps.length-1 || nY < 0 || nY > maps[0].length-1)
                    continue;

                if(visited[nX][nY] == 0 && maps[nX][nY] == 1){
                    visited[nX][nY] = visited[cX][cY] + 1;
                    queue.add(new int[]{nX, nY});
                }
            }

        }


    }
}

문제를 보면 시작점을 기준으로 큐에 담고 방문했던 배열과 이동할 수 있는 곳을 체크하면서 새로운 지점을 계속 큐에 담는다.

최종지의 값은 방문했던 곳의 증가치이므로 마지막에 결과값이 리턴된다.

마무리

아직은 많은 반복이 필요해 보인다. 이론은 알겠으나 코드로 적용시키는 연습이 필요하다.

개인적인 이해를 바탕으로 작성한 글 입니다. 피드백 언제든 환영합니다!

Learn, Programming, Algorithm
Algorithm DFS BFS
Recently Updated
Contents