10971_외판원 순회2 (Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 10971번: 외판원 순회2

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

'''
1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

예제 입력 1
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력 1
35

(3) 코드

n = int(input())
nums = [list(map(int, input().split())) for _ in range(n)]

depth = 0
answer = 99999999
visited = []

def recursive_dfs(city, depth, sum_cost, start):
    global answer

    # 순회를 마친 경우
    if depth == n:
        answer = min(answer, sum_cost)
        return

    for target in range(0, n):
        # 시작 지점으로 중간에 가지않으며 
        # target 이 city 가 되는 경우를 제외하고 
        # target 이 방문하지 않은 곳인 경우이고
        # city 에서 target 으로 갈때 0인 경우를 제외
        if target != start and target != city and target not in visited and nums[city][target] != 0:
            visited.append(target)
            sum_cost += nums[city][target]
            recursive_dfs(target, depth+1, sum_cost, start)
            sum_cost -= nums[city][target]
            visited.pop()

        # 마지막으로 시작지점으로 되돌아가기만 하면 되는 경우
        # city 에서 start 으로 갈때 0인 경우를 제외
        elif depth == n-1 and target == start and nums[city][start] != 0:
            visited.append(start)
            sum_cost += nums[city][start]
            recursive_dfs(city, depth + 1, sum_cost, start)
            sum_cost -= nums[city][start]
            visited.pop()

for city in range(n):
    sum_cost = 0
    target = 0
    start = city
    recursive_dfs(city, depth, sum_cost, start)

print(answer)

(4) 정리

코드를 어떻게 쉽게 작성해야 하나 고민중..
변수명만 적절하게 작성해도 어떻게 동작하는지 쉽게 그려져서 변수명에 신경을 잘 써야겠다.

(5) 참고

참고 풀이
질문 답변

[Python] 파이썬의 []와 list() 의 차이

0. []와 list()란?

1. 예시

(예시1)

(예시2)

(예시3)

2. 참고

참고 자료

1182_부분수열의 합 (Python)

0. 출처

• 유형 : 백트래킹, 브루트포스 (silver 2)
• 링크 : 1182번: 부분수열의 합

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 부분 수열을 구한다.
>> 부분 수열의 합을 구하고 만족하는 부분수열을 카운트한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
5 0
-7 -3 -2 5 8

- 예제 출력 1 -
1

(3) 코드

n, s = map(int, input().split())
nums = list(map(int, input().split()))

result = []

def iterative_dfs(index, path):
    # 매번 결과 추가
    result.append(path)

    for i in range(index, len(nums)):
        path = path+[nums[i]]
        iterative_dfs(i+1, path)

iterative_dfs(0, [])

cnt = 0

for answer in result:
    if answer != [] and sum(answer) == s:
        # print(answer)
        cnt += 1

print(cnt)

(4) 정리

(5) 참고

알고리즘 인터뷰 Q37. 부분집합 문제를 참고하면 좋습니다.

15666_N과 M(12)(Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15666번: N과 M(12)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수에 '중복된 숫자가 있을 때' 중복조합을 구하는 문제
>> set 이용 중복된 수를 제거하고 중복조합을 구한다.

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 1
1 7
1 9
7 7
7 9
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums = set(nums)
nums = list(nums)
nums = sorted(nums)

stack = []

def iterative_dfs(start):
    if len(stack) == m:
        print(*stack)
        return

    for i in range(start, len(nums)):
        stack.append(nums[i])
        iterative_dfs(i)
        stack.pop()

iterative_dfs(0)

(4) 정리

(5) 참고

15665_N과 M(11) (Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15665번: N과 M(11)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수 중에 중복된 숫자가 있을 때 중복순열을 구하는 문제
>> 주어진 수에서 중복된 숫자를 제거하고(set 이용) 그냥 중복순열을 구한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 1
1 7
1 9
7 1
7 7
7 9
9 1
9 7
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))

set_nums = set(nums)
list_nums = list(set_nums)
nums = sorted(list_nums)

stack = []

def iterative_bfs():
    if len(stack) == m:
        print(*stack)
        return

    for i in range(0, len(nums)):
        stack.append(nums[i])
        iterative_bfs()
        stack.pop()

iterative_bfs()

(4) 정리

(5) 참고

15664_N과 M(10) (Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15664번: N과 M(10)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수 중에서 중복된 수가 있을 때 조합을 구하는 문제

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 7
1 9
7 9
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums = sorted(nums)

visited = [False] * n
stack = []

def iterative_dfs(start):
    if len(stack) == m:
        print(*stack)
        return

    overlap_check = 0
    for i in range(start, n):
        if not visited[i] and overlap_check != nums[i]:
            visited[i] = True
            overlap_check = nums[i]
            stack.append(nums[i])
            iterative_dfs(i)
            stack.pop()
            visited[i] = False

iterative_dfs(0)

(4) 정리

(5) 참고

참고 풀이

# 아래와 같이 bool타입이 들어있는 리스트에
visited = [False] * n

vistied = False 와 같이 잘못작성해서 발생한 에러입니다.

visited[i] = True
visited[i] = False 등으로 작성해줘야 합니다.

15663_N과 M(9) (Python)

0. 출처

• 유형 : 백트래킹 (sliver 2)
• 링크 : 15663번: N과 M(9)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수 중에서 '중복된 숫자가 있을 때' 순열을 만드는 문제

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 7
1 9
7 1
7 9
9 1
9 7
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))

nums.sort()
visited = [False] * n
stack = []

def solve(depth, n, m):
    if depth == m:
        print(' '.join(map(str, stack)))
        return
    overlap = 0
    for i in range(n):
        if not visited[i] and overlap != nums[i]:
            visited[i] = True
            stack.append(nums[i])
            overlap = nums[i]
            solve(depth+1, n, m)
            visited[i] = False
            stack.pop()

solve(0, n, m)

(4) 정리

기존 n과 m 문제를 푼 방식에서 조금 다양한 장치를 더 추가해야 된다.
visited 로 방문해야 될 숫자를 구별하고
overlap 변수로 중복된 수열을 출력하는 것을 방지한다.

# overlap 변수가 없는 경우

# 입력
4 2
9 7 9 1

# 출력
1 7
1 9
1 9
7 1
7 9
7 9
9 1
9 7
9 9
9 1
9 7
9 9

중복된 숫자 9를 구별하지 못한다.

(5) 참고

참고 풀이1
참고 풀이2

15657_N과 M(8) (Python)

0. 출처

• 유형 : 백트래킹 (silver 3)
• 링크 : 15657번: N과 M(8)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수로 중복 조합만들기

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 5 2

- 예제 출력 1 -
2
4
5

- 예제 입력 2 -
4 2
9 8 7 1

- 예제 출력 2 -
1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9

(3) 코드

n, m = map(int, input().split())

nums = list(map(int, input().split()))
nums = sorted(nums)

stack = []

def iterative_bfs(start):
    if len(stack) == m:
        print(' '.join(map(str, stack)))
        return

    for i in range(start, len(nums)):
        stack.append(nums[i])
        iterative_bfs(i)
        stack.pop()

iterative_bfs(0)

(4) 정리

(5) 참고

파이썬의 pprint

0. 파이썬의 pprint란?

pprint 모듈은 임의의 파이썬 데이터 구조를 인터프리터의 입력으로 사용할 수 있는 형태로 '예쁘게 인쇄'할 수 있는 기능을 제공합니다.
글을 작성하는 이유는 특정 데이터 구조의 길이가 pprint의 기준 이상이 되지 않으면 출력이 print() 와 동일하게 됩니다.
이 경우 마치 pprint가 동작하지 않는 것 처럼 보여 왜 동작하지 않나 하여 직접 디버깅을 해보며 기준을 찾아보았고
또한 pprint는 코딩테스트에서 이차원배열이 사용되는경우가 많아 디버깅시 많이 이용하는 모듈이라 이번 기회에 찾아보게 되었습니다.

1. 예시

(예시1)

# 입력
arr1 = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

#출력
[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]

이쁘게 출력 안해주는 모습

(예시2)

# 입력
arr2 = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16], [17,18,19,20]]

#출력
[[1, 2, 3, 4],
 [5, 6, 7, 8],
 [9, 10, 11, 12],
 [13, 14, 15, 16],
 [17, 18, 19, 20]]

이쁘게 출력 해주는 모습

(예시3)

# 입력
arr3 = [[1,2,3,4,5,6,7,8,9,10],[11,12,13,14,15,16,17,18,19,20]]

# 출력
[[1,2,3,4,5,6,7,8,9,10],[11,12,13,14,15,16,17,18,19,20]]

이쁘게 출력 안해주는 모습

(예시4)

# 입력
arr4 = [[1,2,3,4,5,6,7,8,9,10],[11,12,13,14,15,16,17,18,19,20],[21,22,23,24,25,26,27,28,29,30]]

# 출력
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 [11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
 [21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

이쁘게 출력 해주는 모습

위와 같이 '특정 기준'을 넘어야 이쁘게 출력해줌을 알 수 있습니다.
option으로 해당 기준을 변경할 수 있는 것인지 찾아봤지만 아직찾지못했습니다.
정확한 default 기준이 무엇인지는 찾아봐야 알 것 같습니다.

2. 참고

공식 문서
참고 자료