본문 바로가기
WIL

11/06 WIL

by 달리는 꿈나무 2022. 11. 6.

1.  알고리즘 관련 공부

이번 주는 공부했던 알고리즘 지식을 정리하려 한다.

 

DFS

  • 그래프 탐색의 일종으로 재귀함수 알고리즘의 형태를 띄고 있다.
  • 전위 순회, 중위 순회, 후위 순회의 형태의 트리 순회가 존재한다. 주로 사용하는 것은 전위 순회이다.
  • 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다. 명심하자!
  • 구현 방법은 재귀 함수 혹은 명시적 스택을 사용하는 것이다.
  • 인접 리스트의 경우 O(N+E)(노드, 엣지), 인접 행렬의 경우  O(n^2)의 시간 복잡도를 갖는다.

 

예제) 합이 같은 부분 집합(DFS)

 

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때
두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.


둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.


예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.

두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.


▣ 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.


▣ 입력예제 1
6
1 3 5 6 7 10


▣ 출력예제 1
YES

 

해설)

부분 집합의 문제는 DFS로 푼다는 것을 명심하자. DFS로 이진 트리의 형식으로 서칭을 하는 것이 해결 방법이다. 이 문제의 경우 정지 코드는 결국 YES가 나오는 조건으로 걸어주고 그것이 아니면 죄다 NO가 나오게 해야한다. DFS는 기본적으로 재귀함수의 형상을 띄는데 여기서 이 노드를 부분집합에 넣을 것인가로 두 가지 갈래가 갈라진다. 넣는 경우의 함수를 위에(이진 트리의 왼쪽 자식 노드라 생각하자), 넣지 않을 경우를 아래 쪽에 (이진 트리의 오른쪽 자식 노드라 생각하자) 배치를 하면 재귀함수는 완성이 되고 여기서 중요한 점은 인자의 L을 이진 트리의 레벨(뎁스)라 생각해서 리스트의 인덱스 번호를 넘기는 것이다.그래서 만약 인덱스 번호가 n까지 즉 리스트의 끝까지 간다면 DFS 이진 트리의 마지막 레벨로 갔다는 것이기에 부분 집합의 형성이 끝이 난다. 이를 정지 조건으로 걸고 여기서 부분집합의 합을 토탈에서 뺀 값이 나머지 값과 같다면 YES, 그 이외는 sys.exit(0) 후 NO가 출력되야 한다.

 

 

import sys
sys.stdin=open("input.txt","r")


# 1을 포함한다, 포함하지 않는다.
# 3을 포함한다, 포함하지 않는다.
# .. .. .. .. .
# 부분 집합의 모든 원소의 합을 sum에 저장하자

# 전체 원소의 합을 total이라고 하고
# 부분집합의 합 sum을 total에서 빼주면
# 그것이 나머지 부분집합의 합이다.
# 이게 맞으면 YES

# 부분 집합의 합을 누적하는 변수 = sum
def DFS(L,sum):
    # L은 a라는 리스트를 참조하는 인덱스 번호다.
    # 이진트리 사용으로 Level을 쓰는데 있어 L이란 변수로 지칭할 것이다.
    # 이진트리의 왼쪽 노드는 부모 노드의 원소를 사용할 때 sum에 더해주고
    # 오른쪽 노드는 안 사용할 때 sum에 더해주지 않는다.
    if L == n:
        # Total의 값이 홀수여서 //2를 쓰면 문제가 생긴다.
        if (total - sum) == sum:
            print("YES")
            # 프로그램 종료 코드
            # 아예 메인을 강제 정지 시켜버린다.
            # NO를 도출하는 건 DFS가 끝난 후에 YES가 나오지 않을 때 출력하자
            sys.exit(0)
    # else 코드 안 넣으면 이상해진다.
    else:
        # 핵심 알고리즘
        # 두 갈래로 나누기
        
        # 왼쪽 노드
        DFS(L+1,sum + a[L])
        #오른쪽 노드
        DFS(L+1,sum)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    # 총합
    total = sum(a)

    DFS(0,0)
    print("NO")

 

 

'WIL' 카테고리의 다른 글

11/27 WIL  (0) 2022.11.27
11/12 WIL  (0) 2022.11.12
10/30 WIL  (1) 2022.10.30
10/23 WIL  (1) 2022.10.23
10/16 WIL  (0) 2022.10.23