[SWEA] 배열 최소 합 (python)

SWEA Learning Club 7차시 배열 최소 합 문제

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIc7KqfQDFAWg 

SW Expert Academy

배열 최소 합 문제

문제 요구사항은 순열로도 풀 수 있지만 백트래킹을 활용하여 푼 문제

100% 내 생각으로 풀었는가?
→ △

개념을 참고하면서 풀었고, 무엇보다 과제로는 통과했지만, 실제 처음 실행시간이 7초가 나와버려서 효율이 별로였고, 이를 해결하기 위해 다른 분께 아이디어를 얻었음

 

내가 푼 정답코드

T = int(input())
def back(n,min_n):
    global m
    if min_n > m : # 기존값보다 크다면
        return # 끝내버리기
    if n == N: # 전부 True일때의
        if min_n < m :
            m = min_n #최소값
        return
    for i in range(N): #한정조건 (같은 열 선택 불가 조건)
        if check[i] == False:
            check[i] = True
            back(n+1,min_n+x[n][i])
            check[i] = False
    return

for case in range(1,T+1):
    N = int(input())
    m = 10 * N
    x = [0]*N
    check = [False]*N
    for w in range(N):
        x[w] = list(map(int, input().split()))
    back(0,0)
    print(f'#{case} {m}')

내가 직접 푼건 아니지만 순열을 활용한 코드
(코드 몇개 추가안해서 실행시간이 오래걸림)

def f(i, k):
    global minV
    if i == k : # 순열 완성
        s = 0
        for j in range(N):
            s += arr[j][p[j]]  # j 행에서 고른 열 p[j]
        if minV > s:
            minV = s
        return
    else :
        for j in range(i, N) : #p[i]의 숫자를 자신부터 오른쪽과 교환
            p[i], p[j] = p[j], p[i]
            f(i+1, k)
            p[i], p[j] = p[j], p[i]
    return
T = int(input())
for case in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    p = [i for i in range(N)] # p[i] i행에서 선택한 열
    minV = 10*N # 자연수
    f(0,N)
    print(f'#{case} {minV}')

백트래킹을 활용하여 풀었고(정확히는 DFS가 맞을지도?) 생각보다 쉽게 접근할 수 있던 문제 다만 원래 과제로의 요구 사항은 순열을 이용하는 쪽을 원한거같지만 백트래킹 쪽을 조금은 더 알고 있어서 백트래킹을 활용하여 해결하였다.

---

느낀점

백트래킹 기법의 경우 유망할 경우의 조건을 따지는 과정에서 코드 짜는게 생각보다 쉽지 않아서 초반에 많이 애먹었다. 특히 다른 백트레킹 문제를 해결한 코드들을 참고하면 대부분 함수 2개로 나눠서 처리했기에 함수 2개로 나눠야하나 생각했으나 꼭 2개로 나누지 않아도 충분히 유망한지 판정할 수 있었다.

확실히 점점 과제가 어려워지는게 느껴져서 요즘 부족하다는 걸 굉장히 많이 느끼고 있다. 특히 stack 초반에는 쉽다고 느껴졌는데 2일정도 지나자마자 난이도가 한 5배는 어려워진 느낌이었고, 확실하게 사용할줄 알면 도움이 많이 되니 시간 날때 깊게 다시 공부해야겠다 😥