[코드트리/Python] 조삼모사 & 연산자 배치하기

 

 

1. 조삼모사 

https://www.codetree.ai/training-field/frequent-problems/problems/three-at-dawn-and-four-at-dusk/description?page=1&pageSize=20&order=tier 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

 

풀이

 

CODE

import sys

input = sys.stdin.readline
num_of_works = int(input())
works = []
for _ in range(num_of_works):
    works.append(list(map(int, input().split())))

array = [i for i in range(num_of_works)]
k = num_of_works // 2
used = [False for _ in range(num_of_works)]

# 아침, 저녁 분류된 배열을 바탕으로 점수 차 구하기
def get_scores(morning_arr):
    morning = 0
    night = 0
    night_arr = []
    for i in range(num_of_works):
        if i not in morning_arr:
            night_arr.append(i)

    for i in morning_arr:
        idx = 0
        while idx < k:
            if morning_arr[idx] != i:
            # 자기 자신이 아닐 경우 함께하는 다른 조합과의 상성 점수 더해주기
                morning += works[i][morning_arr[idx]]
            idx += 1

    for i in night_arr:
        idx = 0
        while idx < k:
            if night_arr[idx] != i:
            # 자기 자신이 아닐 경우 함께하는 다른 조합과의 상성 점수 더해주기
                night += works[i][night_arr[idx]]
            idx += 1

    return abs(morning - night)  # 절댓값으로 반환


# 조합 구하는 백트래킹
def backtrack_comb(idx, arr, mornings):
    if len(arr) == k:
        mornings.append(arr)
        return arr

    for i in range(idx + 1, len(array)):
        if used[i] == False:
            used[i] = True
            backtrack_comb(i, arr + [array[i]], mornings)
            used[i] = False

    return mornings


combs = backtrack_comb(-1, [], [])
answer = 1e9
for c in combs:
    each = get_scores(c)
    if answer > each:
        answer = each

print(answer)

• 삼성 코테는 itertools를 사용하지 못한다고 해서 itetools를 쓰지 않고 조합 구하는 방법을 찾아봤다.
• 따라서 bactrack_comb는 구글링의 도움을 조금 받았다!
  앞으로 코드를 복습하면서 itertools없이 조합과 순열을 구하는 법에 익숙해져놔야겠다.

 

---

 

2. 연산자 배치하기 

https://www.codetree.ai/training-field/frequent-problems/problems/arrange-operator/description?page=1&pageSize=20&order=tier 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

 

풀이

 

CODE

import sys

input = sys.stdin.readline

# 입력
n = int(input())
numbers = list(map(int, input().split()))
carc = list(map(int, input().split()))

# 계산 순서에 대한 백트래킹 진행
def bactracking(idx, ans, total):
    if idx == n-1:
        total.append(ans)

    for i in range(3):
        if carc[i] > 0:
            carc[i] -= 1

            if i == 0:
                bactracking(idx + 1, ans + numbers[idx + 1], total)
            elif i == 1:
                bactracking(idx + 1, ans - numbers[idx + 1], total)
            elif i == 2:
                bactracking(idx + 1, ans * numbers[idx + 1], total)

            carc[i] += 1

    return total


result = bactracking(0, numbers[0], [])
print(int(min(result)), int(max(result)))

• 이렇게 오래 걸릴 일이 아닌데 어렵게 생각했는지 너무 오래걸렸다. 아직 확실히 백트래킹에 취약한가보다.
• '덧셈, 뺄셈, 곱셈 순서의 모든 경우를 고려해야하는가'를 고민하다가 처음엔 순열로 접근했으나 시간초과와 메모리초과가 발생했다. 백트래킹에서 '방문처리'와 '되돌리기' 방법을 고민하면서 이렇게 된 것 같다. 이렇게 숫자를 줄이는 방식으로 진행하면 되는 걸 ..!!! 그래도 백트래킹에 대해 좀 더 알게 되는 문제였다. 백트래킹 문제는 함수 자체를 최대한 간결하게 탈출조건 위주로 구현하고, 인자를 활용해서 조절해나가는 것 같다는 느낌을 받았다.

 

- 끝! -