완전탐색(Brute-force Search) + 백준 1018 체스판 다시 칠하기 + 백준 1182 부분집합의 합

쉽게 말하면 가능한 경우를 일일히 다 탐색하는 것, 틀릴일이 없지만 시간이 최대로 들어간다.
일단 맨 처음에 정말 거의 모든 경우에 성립하지 않지만, 완전 탐색이 먹히는지 고려하고 넘어가는 것도 좋다.
정말 아무 방법이 없어보이는 답이 없는 문제가 의외로 문제 크기가 작아서 진짜 일일히 다 시도해보는 것이 가능할 떄가 있다.

• 1018 체스판 다시 칠하기

  → 돌고 돌아옴. 이런 미로 문제나 체스판 문제의 경우는, 하나씩 세주는 것이 옳다.

  내가 B 라면, 내가 W 라면 이런식

  → 솔직히 힘들었다. 그냥 구현을 하는 것에서도 버벅거리는 것을 느낀다.

  → 절대적인 문제 풀이량이 늘어야한다.

    # 100ms, 메모리: 29380kb
    garo, sero   = map(int, input().split(" "))
    boards=[]
    for _ in range(garo):
        boards.append(input())
  
    board_want=[]
    for g in range(garo-7):
        #print(g)
        for s in range(sero-7):
            board = boards[g:g+8]
            board_tmp=[]
            for b in board:
                board_tmp.append(b[s:s+8])
            board_want.append(board_tmp)
    ans_list=65
    for b in board_want:
        #print(b)
        ans=0
        reverse=True # 줄별로 체크 무늬 바뀐다.
        for garo in range(8):
            if reverse:
                reverse=False # 줄별로 체크 무늬 바뀐다.
                rowrow="WBWBWBWB"
            else:
                reverse=True
                rowrow="BWBWBWBW"
            for sero in range(8):
                #print("board:",b[sero][garo])
                #print(rowrow[sero])
                if b[sero][garo]==rowrow[sero]:
                    ans+=0
                else:
  
                    ans+=1
        if ans > 32:
            ans = 64-ans
        if ans_list> ans:
            ans_list = ans
  
        ans=0
  
    print(ans_list)

• 1182 부분집합의 합

  → dfs 는 가능한데 완전 탐색으로는 죽었다 깨어나도 못풀겟음.

  → 부분집합은 고로 조합이다.

  → 부분집합은 자고로 combination이라고 생각해야하네.

  → 조합을 조합으로 받아들이는 것도 굉장히 중요한 스킬이다.

  → list 의 합은 꼭 sum 을 쓰는게 가장 시간을 절약한다.

    # 668ms
    # 백준 1018 체스판 다시 칠하기
    import itertools
  
    N, S = map(int, input().split(" "))
    ns = list(map(int, input().split(" ")))
    ans = 0
  
    for g in range(1,N+1):
        nCr = list(itertools.combinations(ns,g))
        for param  in nCr:
            if sum(param) == int(S):
                ans+=1
  
    print(ans)

• python 순열과 조합, list 사용하고 조합해야할 때 항상 볼것 : combinations, permutations

  파이썬 iterable 의 원소로 순열과 조합을 구한다.

  • permutation

    순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 의미한다. 즉, 서로 다른 n 개 중에 r 개를 골러 순서있게 나열하는 가짓수 이다.

    순열은 순서를 고려한다.

    예)

    • 1,2,3 의 숫자가 적힌 카드가 있을 때, 이 중 두 장을 꺼내는 경우의 수 → 12, 13, 21, 23, 31, 32

    • 'A','B','C' 로 만들 수 있는 경우의 수 → 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'

      itertools.permutation 을 이용하면 for 문을 사용하지 않고 순열을 구할 수 있다.

      import itertools 
      
      pool =['A','B','C']
      print(list(map(''.join, itertools.permutations(pool)))) # 3 개의 원소로 수열 만들기
      print(list(map(''.join, itertools.permutations(pool,2)))) #  2 개의 원소로 수열 만들기
      
      arr = ['A','B','C']
      
      nPr   = itertools.permutations(arr,2)
      print(list(nPr))
      #결과 : [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
      

  • combination

    조합이라는 것은 순서를 고려하지 않고 서로다른 n 개 중에 r 개를 취해 조를 만들떄, 하나하나의 조를 n개 중에서 r개를 취한 조합이라고 생각하자.

    조합은 순서를 고려하지 않기 때문에 [A, B, C]의 리스트에서 2개의 원소를 골라 나열하면

    [(A, B), (A, C), (B, C)] 가 나오게 된다. 조합은 (A, B)와 (B, A)는 같은 것으로 취급한다.

      import itertools
    
      arr = ['A','B','C']
    
      nCr = itertools.combinations(arr,2)
      print(list(nCr))
      결과 : [('A', 'B'), ('A', 'C'), ('B', 'C')]

참고링크