[PGS] 프로그래머스 두 개 뽑아서 더하기, 완전탐색, 백트래킹 최적화 #99클럽8일차 #TIL

---

#99클럽 #99일지 #코딩테스트 #개발자스터디 #항해 #TIL #프로그래머스
 

✅ 두 개 뽑아서 더하기 설명

✅ 해결 방법

✅ 발생한 문제와 방안

✅ 최종적인 해결 방법

✅ 최적화 방안

 
 

그래서 오늘의 TIL(Today I Learned) 학습 키워드 
 

✨ 전수 조사

✨ 백트래킹

---

 

✅ 두 개 뽑아서 더하기 설명

 

99클럽 미들러 난이도 두 개 뽑아서 더하기로 ✨전수 조사, 백트래킹✨ 하는 방법을 알아보겠습니다.
 
코딩테스트 연습 - 두 개 뽑아서 더하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

---

 
 

✅ 문제설명

 

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

 

numbers의 길이는 2 이상 100 이하입니다.
numbers의 모든 수는 0 이상 100 이하입니다.

 

 

---

 

✅ 해결 방법

 

서로 다른 인덱스에 있는 두 수를 뽑아 더해서 "만들 수 있는 모든 수"를 구하는 것이 목표로, 전수조사, 완전탐색에 해당합니다. 전수조사는 DFS, BFS로도 가능하지만 DFS 구현이 더 간단하기 때문에 DFS를 사용하기로 했습니다.

 

백트래킹은 이미 갔던 곳을 다시 나와서, 다른 방향을 탐색하는 방법으로 스택을 사용합니다. 백트래킹을 사용하지 않으면 한 방향으로만 조사하지만, 백트래킹을 사용하면 모든 방향을 조사할 수 있습니다.

 

이를 응용하면 조합, 순열도 가능합니다. 조합은 N개의 수 중에서 M개로 가능한 모든 경우의 수를 찾을 수 있는 방법입니다. iterools 라이브러리를 사용해도 되지만 코딩테스트에선 불가한 경우가 많기 때문에 조합을 직접 만들어 적용해보겠습니다. 여기서는 N개의 수에서 2개만 고르면 되겠네요. 배열의 넓이, 깊이는 2입니다.

 

항상 dfs를 구현할 때, 헷갈렸던 것은 dfs는 재귀함수라는 점이 구현하기가 복잡했습니다. 언제 return을 해야할 지도, 어디 부분에서 백트래킹을 해야 최적화로 구현해야할지도 조금 헷갈렸습니다.

 

def dfs(i):
    if len(ary) == 2:
        return
    
    for i in range(numbers):
        if not visited[i]:
            visited[i] = True
            dfs(i)
            visted[i] = False
        return

def solution(numbers):
    answer = []
    visited = [False] * len(numbers)+1
    
    #DFS 백트래킹
    for i in range(len(numbers)):
        if not visited[i]:
            visited[i] = True
            dfs(i)
            visited = False
            
            
    return answer

 

예를 들면 윗 코드에서 def dfs에서 visited를 관리해야할지, 아래의 메인함수에서 dfs에서 관리해야할지, 어느 곳에서 반복문을 동작해야하는 지 기준점이 필요했습니다.

 

def back():
    if len(ans) == 2:
        return ans[0] + ans[1]
    
    for i in range(1, len(numbers)+1):
        if i not in ans:
            ans.append(i)
            back(i)
            ans.pop()

def solution(numbers):
    answer = []
    visited = [False] * len(numbers)+1
    
    #DFS 백트래킹
    answer.append(back())
            
    return answer

 

재귀함수에서 for 문을 작동해야, 외부에서도 추가 작성하지 않습니다. 어차피 재귀함수내에 for문이 필요하기 때문이죠. 윗코드를 참고하여 작성해보겠습니다.

 

 

---

✅ 발생한 문제와 방안

 

해당 back() 함수는 if not in ans:로 작동합니다. 따라서 같은 숫자가 있으면 중복처리를 하지 않기 때문에 1+1 = 2 에서 오류가 발생가능합니다. visited 처리를 위해 글로벌 변수를 사용하겠습니다.

 

ans = []
def back(numbers):
    global visited
    if len(ans) == 2:
        print(2, ans[0], ans[1])
        return (ans[0] + ans[1])
    
    for i in range(0, len(numbers)):
        if not visited[i]:
            visited[i] = True
            ans.append(numbers[i])
            back(numbers)
            visited[i] = False
            ans.pop()

def solution(numbers):
    answer = []
    global visited
    visited = [False] * (len(numbers)+1)
    
    #DFS 백트래킹
    answer.append(back(numbers))
            
    return answer

 

분할된 재귀함수가 모든 값을 찾아주지만 return에서 [None]만 돌아오고 있습니다. 이유는 스택 함수가, return을 했더라도 그 이전의 재귀함수로 값이 넘어갈뿐 저장을 하지 않고 덮여졌기 때문이죠. 

 

 

수정하고, None값이 아닐때만 값을 저장한 후 배열에서 중복값을 없애야합니다. set을 사용하면 될거같습니다.

 

---

✅ 최종적인 해결 방법

 

ans = []
answer = []

def back(numbers):
    global visited
    if len(ans) == 2:
        print(2, ans[0], ans[1])
        return ans[0] + ans[1]

    for i in range(0, len(numbers)):
        if not visited[i]:
            visited[i] = True
            ans.append(numbers[i])
            result = back(numbers)
            if result is not None:
                answer.append(result)
            visited[i] = False
            ans.pop()


def solution(numbers):
    global visited
    visited = [False] * (len(numbers) + 1)

    # DFS 백트래킹
    back(numbers)
    final_answer = list(set(answer))
    
    return sorted(final_answer)

 

 

---

✅ 최적화 방안

 

전역 변수를 제거하고, 중복 제거를 백트래킹 내부 함수에서 집합으로 처리해서 최적화 할 수 있습니다. |= 는 합집합 연산입니다.

def back(numbers, ans, idx):
    if len(ans) == 2:
        return ans[0] + ans[1]

    result = set()
    for i in range(idx, len(numbers)):
        ans.append(numbers[i])
        result.add(back(numbers, ans, i + 1))
        ans.pop()

    return result

def solution(numbers):
    final_answer = set()
    for i in range(len(numbers)):
        final_answer |= back(numbers, [numbers[i]], i + 1)

    return sorted(final_answer)

좌: 최적화 전 / 우 : 최적화 후

참고자료

---

https://veggie-garden.tistory.com/24