코딩테스트 합격자되기 C++ - 1주차

개념 문제

1. DFS 구현하느 대표적인 두 가지 방법은 재귀 호출을 이용하는 것과 명시적인 스택(Stack) 자료구조를 사용하는것임. 각 구현의 방식과 장단점은?

•  
• 구현
  • 재귀

    void DFS(grap, node, visited)
    {
    	if(탈출 조건)
        {
        	return;
        }
        
    	visited(node) = 방문;
        cout<<node<<endl; // 방문 노드 출력
        for(auto a : grap[node])
        {
        	if(visited[a] == 방문X)
            {
            	DFS(grap, a, visited);
            }
        }
    }

  • 스택

    void DFS(graph, start)
    {
        unordered_set<int> visited;
        stack<int> s;
        
        // 시작 노드를 스택에 삽입
        s.push(start);
        
        while (s.empty() == false)
        {
            // 스택에서 하나의 노드를 꺼냄
            int node = s.top();
            s.pop();
            
            // 방문하지 않은 노드라면 방문 처리
            if (visited.find(node) == visited.end())
            {
                visited.insert(node);
                cout << node << " ";  // 방문한 노드 출력
                
                // 인접한 노드들을 스택에 넣음 (역순으로 넣어 재귀와 유사한 순서로 방문)
                for (int i = graph[node].size() - 1; i >= 0; i--)
                {
                    int neighbor = graph[node][i];
                    if (visited.find(neighbor) == visited.end())
                    {
                        s.push(neighbor);
                    }
                }
            }
        }
    }

	재귀	스택
장점	코드가 간결하고 이해하기 쉬워짐 알고리즘의 본질에 충실한 구현으로 직관적 방문 경로가 콜스택에 저장됨	스택 오버플러우의 위험이 없음 깊이 제한이 없어 큰 그래프도 탐색 가능 방문 순서를 더욱 세밀하게 제어 가능
단점	깊이가 깊은 그래프에선 스택 오버플러우가 발생할 수 있음 재귀 호출의 오버헤드가 발생 일부 언어에서 재귀 깊이가 제한이 있어 큰 그래프에선 문제가 될 수 있음	재귀 방식보다 복잡 명시적 스택 관리가 필요 백트래킹이 필요한 경우 추가로직이 필요
메모리 사용	시스템 콜 스택을 사용하므로 호출 깊이만큼 메모리 사용	명시적 스택을 사용하여 실제 필요한 노드 정보만 저장
성능	함수 호출 오버헤드로 인해 일반적으로 느림	스택 연산만 사용하므로 일반적으로 더 빠름
상태 관리	함수의 지역 변수로 상태 관리가 자연스러움	상태를 명시적으로 스택에 저장
사용 상황	트리나 그래프의 깊이가 제한적인 경우 코드 가독성이 중요한 경우	대규모 그래프 그래프가 깊은 경우 성능이 중요한 경우

 

2. 방향 그래프에서 사이클 존재 여부를 판별하기 위해 DFS를 어떻게 활용할 수 있는지 구체적인 알고리즘을 설명하시오

• 기본 아이디어
  • 모든 노드를빵문하지 않은 상태로 시작해, 각 노드에 대해 DFS를 실행하면서 방문 중인 상태(노드 탐색이 완전 끝나지 않은 상태)의 노드를다시 방문하면 사이클 존재한다

 

3. 재귀를 활용한 DFS에서 가장 최근 노드로 돌아가는 백트래킹 동작이 어떤 방식을 동작하는지 하나의 예를 들어 설명하시오

• 백트래킹은 함수 호출 스택을 통해 자연스럽게 이루어지는데, 백트래킹이란 더이상 탐색할노드가 없다면 이전 분기점으로 돌아가는 과정이다
• ex) 밑에 그래프에서 1-2-4까지 방문했다 했을 때 더이상 탐색할 노드가 없다면 2로 돌아가는 것이다 
     1
     / \
   2   3
   / \   \
  4  5   6
     / \
    7  8

---

문제 풀이

• 네트워크:https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스