Choo의 머릿속
Choo의 머릿속/
2️⃣
완전탐색(DFS/BFS) VS 백트래킹+순열과 조합(백준N과 M)
2️⃣

완전탐색(DFS/BFS) VS 백트래킹+순열과 조합(백준N과 M)

작성일자
May 4, 2023
태그
PS
프로젝트
책
책 종류
 

1. 완전 탐색

1) 정의

  • 비유) 파일찾기 → 존재하는 모든 폴더에 들어가서 찾음
  • 정의) 모든 경우의 수를 찾아서 답을 찾는 방법
  • 특징)
    • 가장 확실한 방법
    • 가장 시간이 오래 걸리는 방법
    • 입력(N) 제한이 작다면 완전탐색 의심해 볼만함
  • 예시) 백준 2309 일곱 난쟁이
    • 9명 키 합에서 2명 키 뺐을 때 100이 되는 경우 모두 찾기 → 9C2

2) 종류

[1] 브루트포스

  • 정의) 반복문, 조건문을 이용해 모두 테스트하는 방법
    • 단순히 for문과 if문으로 모든 경우들을 만들어 답 구함
  • 예시)
    • 난쟁이 문제
    • 1부터 100까지 3의 배수 다 더하기 → for (i=1; i<100; i++) {if(i%3==0) sum+=i;}

[2] 비트마스크

  • 정의) 2진수 표현 기법을 이용하는 방법
    • 모든 경우의 수가 1 또는 0으로 구성되는 경우
  • 예시) 원소가 5개인 집합의 모든 부분집합 구하기
    • 0 0 0 0 0 / 0 0 0 0 1 / 0 0 1 0 1 … → 5자리 2진수로 표현 가능 (쓸지 안 쓸지)

[3] 재귀

  • 정의) 자기 자신을 호출하여 작업을 반복 수행하는 방법
    • 재귀함수 : 자기 자신을 호출하는 함수
  • 예시) 백준 17478 재귀함수가 뭔가요? (간략히 작성함)
    • 예시) 원소가 5개인 집합의 모든 부분집합 구하기
        • 출력결과

    [4] 순열 nPr

    • 정의) n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
      • 순열에 원소를 하나씩 채워가는 방식
      • 중첩 for문이나 재귀함수로 구현 가능
    • 특징) 시간복잡도 O(N!) → N 정말 작을 때만 사용 가능
    • 예시) 5C3
        • 출력 결과

    [5] DFS, BFS

    • 정의) 그래프에서 모든 정점을 탐색하는 방법
      • 모든 곳을 다 방문한다는 점에서 완전탐색으로 분류 가능
    • 종류)
      • DFS : 깊이 우선 탐색
      • BFS : 너비 우선 탐색
        • notion image
    • 예시) 백준 1260번 DFS와 BFS 프로그램

      2. 백트래킹

      1) 정의

      • 비유) 미로찾기 → 길의 끝이 보이면 분기점으로 돌아감
      • 정의) 완전 탐색처럼 전부 탐색하지 않고, 가지치기(Pruning)로 가능한 경우의 수를 줄인 것
        • 한정된 조건을 가진 문제를 풀려는 전략
        • 시간이 오래 걸린다는 완전탐색의 단점 보안 (제한 조건 많을수록 시간 단축됨)
      • 특징) 주로 재귀함수로 구현
      • 예시) 백준 9663 N-Queen
        • 퀸의 특성
          • 상하좌우로 움직일 수 있음
            • 같은 행/열에 없어야 함
              • N*N 체스판에 퀸 N개이므로 각 행/열마다 퀸 한 개씩
          • 대각순으로 움직일 수 있음
            • 동일 대각선상에 없어야 함
              • 기울기가 1이거나 -1이면 안됨
        • 경우의 수 구하는 코드
            • 각 경우 구하는 코드

        2) 백준 N과 M문제 시리즈 정리(순열과 조합)

        N과 M문제들은 백트래킹을 연습해보기 좋은 문제들이다.
        문제집: N과 M (시리즈)
        문제집: N과 M (시리즈)
        https://www.acmicpc.net/workbook/view/2052
        문제집: N과 M (시리즈)

        백트래킹 기본 구조

        💡
        nCr, nPr 등의 경우
        1. 종료 조건 : r개의 수를 골랐을 때
        1. 반복문 : 총 n개의 자연수
        1. 제한 조건 : 이미 사용한 수는 사용 X
        1. 상태 변화 : 사용한 수는 표시
        1. 다음 단계 : 한 개의 수 더 고름
        1. 원상 복구 : 사용했다고 표시한 거 복구
        백트래킹 기본 틀
        백트래킹 응용 틀

        순열과 조합 → {1,2,3,4} n=4, r=2

        • 순열 nPr : 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 다르면 다르게 봄. 인정함)
            • {1,2} {1,3} {1,4} 🌿 {2,1} {2,3} {2,4} 🌿 {3,1} {3,2} {3,4} 🌿 {4,1} {4,2} {4,3}
            N과 M(1), N과 M(5)
        • 조합 nCr : 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 달라도 하나로 봄. 인정 안함)
            • {1,2} {1,3} {1,4} 🌿 {2,3} {2,4} 🌿 {3,4}
            N과 M(2), N과 M(6)
        • 중복순열 nπr : 중복 가능한 n개 중에 r개를 선택하는 경우의 수 (순서 다르면 다르게 봄)
            • {1,1} {1,2} {1,3} {1,4} 🌿 {2,1} {2,2} {2,3} {2,4} 🌿 {3,1} {3,2} {3,3} {3,4} 🌿 {4,1} {4,2} {4,3} {4,4}
            N과 M(3), N과 M(7) (특이사항: 출력할 때 시간 단축해줌)
        • 중복조합 nHr : 중복 가능한 n개 중에 r개를 선택하는 경우의 수 (순서 달라도 하나로 봄)
            • {1,1} {1,2} {1,3} {1,4} 🌿 {2,2} {2,3} {2,4} 🌿 {3,3} {3,4} 🌿 {4,4}
            N과 M(4), N과 M(8)

        같은 것이 있는 순열과 조합 → {1,1,1,2} n=4, r=4

        • 순열 (순서 다르면 다르게 봄)
            • {1,1,1,2} {1,1,2,1} {1,2,1,1} {2,1,1,1}
            N과 M(9)
        • 조합 (순서 달라도 하나로 봄)
            • {1,1,1,2}
            N과 M(10)
        • 중복순열 (순서 다르면 다르게 봄)
            • {1,1,1,1} {1,1,1,2} {1,1,2,1} {1,1,2,2} {1,2,1,1} {1,2,1,2} {1,2,2,1} {1,2,2,2} {2,1,1,1} {2,1,1,2} {2,1,2,1} {2,1,2,2} {2,2,1,1} {2,2,1,2} {2,2,2,1} {2,2,2,2}
          • 1 네 개 2 네 개 있는데, 8P4하는 느낌
            • N과 M(11)
        • 중복조합 (순서 달라도 하나로 봄)
            • {1,1,1,1} {1,1,1,2} {1,1,2,2} {1,2,2,2} {2,2,2,2}
          • 1 네 개 2 네 개 있는데, 8C4하는 느낌
            • N과 M(12)

        3. 완전탐색 vs 백트래킹 → 문제 풀이 Tip

        • 일단 완전탐색으로 풀었을 때의 시간 복잡도를 계산한 후
          • 가능할 거 같다면 한 번 풀어보고,
          • 시간초과가 날 거 같다면 백트래킹을 시도하기