[알고리즘 기초 2/2] 부르트 포스

3085번: 사탕 게임

예전부터 구현하기 겁나서 손도 못대던 문젠데.. 이번에야 말로 풀어봐야겠다는 결심이 섰다.

같은 행 or 열에서 다른 두개의 문자가 연속되어있을 때 교환.
교환 후에는 교환한 자리의 열과 행을 모두 체크해서 maxValue를 갱신해주는 방식이다.

n = int(input())

def check_row(row) :
    max_row = 0
    dp = [1] * n
    for i in range(1, n) :
        if arr[row][i - 1] == arr[row][i] :
            dp[i] += dp[i - 1]
    max_row = max(max_row, max(dp))
    return max_row

def check_col(col) :
    max_col = 0
    dp = [1] * n
    for i in range(1, n) :
        if arr[i][col] == arr[i - 1][col] :
            dp[i] += dp[i - 1]
    max_col = max(max_col, max(dp))
    return max_col

arr = []
for i in range(n) :
    arr.append(list(input()))

maxValue = 0
for col in range(n) :
    for i in range(1, n) :
        if arr[i][col] != arr[i - 1][col] :
            #change
            tmp = arr[i][col]
            arr[i][col] = arr[i - 1][col]
            arr[i - 1][col] = tmp
            #check
            maxValue = max([maxValue, check_col(col), check_row(i), check_row(i - 1)])
            #change again
            tmp = arr[i][col]
            arr[i][col] = arr[i - 1][col]
            arr[i - 1][col] = tmp
        else :
            maxValue = max([maxValue, check_col(col), check_row(i), check_row(i - 1)])

for row in range(n) :
    for i in range(1, n) :
        if arr[row][i] != arr[row][i - 1] :
            #change
            tmp = arr[row][i]
            arr[row][i] = arr[row][i - 1]
            arr[row][i - 1] = tmp
            #check
            maxValue = max([maxValue, check_col(i), check_col(i - 1), check_row(row)])
            #change again
            tmp = arr[row][i]
            arr[row][i] = arr[row][i - 1]
            arr[row][i - 1] = tmp
        else :
            #check
            maxValue = max([maxValue, check_col(i), check_col(i - 1), check_row(row)])
print(maxValue)

14500번: 테크로미노

와.. 진짜 !!! 너무 힘들었다.
이건 피지컬 문제다.
회전하는 걸 구현해보려고 했는데 그냥 노가다가 편하고 빠를 것 같아서 노가다로 했다.
정사각형과 길쭉하게 생긴건 따로 구현해줬고, 나머지 3개는 한번에 구현해줬다.
6개의 작은 사각형을 더해서 sum_tmp에 더한 뒤 2개의 비는 작은 사각형을 빼주는 방식으로 구현했다.

import sys

input = sys.stdin.readline

n, m = list(map(int, input().split()))
arr = []
for i in range(n) :
    arr.append(list(map(int, input().split())))

maxValue = 0

# ---- 모양 구현하기
for row_idx in range(n) :
    for col_idx in range(m) :
        if col_idx + 3 < m :
            maxValue = max(maxValue, sum(arr[row_idx][col_idx : col_idx + 4]))
        else :
            break
# | 모양 구현하기
for col_idx in range(m) :
    for row_idx in range(n) :
        if row_idx + 3 < n :
            tmp = arr[row_idx][col_idx] + arr[row_idx + 1][col_idx] + arr[row_idx + 2][col_idx] + arr[row_idx + 3][col_idx]
            maxValue = max(maxValue, tmp)
        else :
            break
# ㅁ 모양 구현하기
for row_idx in range(n) :
    for col_idx in range(m) :
        if row_idx + 1 < n and col_idx + 1 < m :
            tmp = arr[row_idx][col_idx] + arr[row_idx + 1][col_idx] + arr[row_idx][col_idx + 1] + arr[row_idx + 1][col_idx + 1]
            maxValue = max(maxValue, tmp)
        else :
            break

# (3, 2) 모양들 구현하기
for row_idx in range(n) :
    for col_idx in range(m) :
        if row_idx + 2 < n and col_idx + 1 < m :
            sum_list = []
            sum_tmp = arr[row_idx][col_idx] + arr[row_idx + 1][col_idx] + arr[row_idx][col_idx + 1] + arr[row_idx + 1][col_idx + 1] + arr[row_idx + 2][col_idx] + arr[row_idx + 2][col_idx + 1]
            sum_list.append(sum_tmp - arr[row_idx + 1][col_idx + 1] - arr[row_idx + 2][col_idx + 1])
            sum_list.append(sum_tmp - arr[row_idx + 1][col_idx] - arr[row_idx + 2][col_idx])
            sum_list.append(sum_tmp - arr[row_idx + 1][col_idx + 1] - arr[row_idx][col_idx + 1])
            sum_list.append(sum_tmp - arr[row_idx + 1][col_idx] - arr[row_idx][col_idx])
            sum_list.append(sum_tmp - arr[row_idx][col_idx + 1] - arr[row_idx + 2][col_idx])
            sum_list.append(sum_tmp - arr[row_idx][col_idx] - arr[row_idx + 2][col_idx + 1])
            sum_list.append(sum_tmp - arr[row_idx][col_idx + 1] - arr[row_idx + 2][col_idx + 1])
            sum_list.append(sum_tmp - arr[row_idx][col_idx] - arr[row_idx + 2][col_idx])
            maxValue = max(max(sum_list), maxValue)
        else :
            break

# (2, 3) 모양들 구현하기
for row_idx in range(n) :
    for col_idx in range(m) :
        if row_idx + 1 < n and col_idx + 2 < m :
            sum_list = []
            sum_tmp = sum(arr[row_idx][col_idx : col_idx + 3]) + sum(arr[row_idx + 1][col_idx : col_idx + 3])
            sum_list.append(sum_tmp - arr[row_idx][col_idx] - arr[row_idx + 1][col_idx + 2])
            sum_list.append(sum_tmp - arr[row_idx + 1][col_idx] - arr[row_idx][col_idx + 2])
            sum_list.append(sum_tmp - arr[row_idx + 1][col_idx] - arr[row_idx + 1][col_idx + 2])
            sum_list.append(sum_tmp - arr[row_idx][col_idx] - arr[row_idx][col_idx + 2])
            sum_list.append(sum_tmp - arr[row_idx + 1][col_idx + 1] - arr[row_idx + 1][col_idx + 2])
            sum_list.append(sum_tmp - arr[row_idx][col_idx + 1] - arr[row_idx][col_idx + 2])
            sum_list.append(sum_tmp - arr[row_idx + 1][col_idx] - arr[row_idx + 1][col_idx + 1])
            sum_list.append(sum_tmp - arr[row_idx][col_idx + 1] - arr[row_idx][col_idx])
            maxValue = max(max(sum_list), maxValue)
        else :
            break

print(maxValue)

10971번: 외판원 순회 2

분명 다 맞은 것 같은데.. 35퍼에서 자꾸 틀려서 질문게시판에도 올려보고 생 난리를 쳤다. 알고보니 맨 처음으로 돌아가는 걸 고려를 안했던 것..
고쳐주니까 해결 됐다.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(x for x in range(n))
map_list = []
for _ in range(n) :
    map_list.append(list(map(int, input().split())))

result = []
visited = [0] * n

def func(idx, num, current_num) :
    global min_num
    if min_num <= current_num :
        return
    elif num == n and map_list[result[-1]][result[0]] != 0 :
        current_num += map_list[result[-1]][result[0]]
        min_num = min(min_num, current_num)
    elif min_num <= current_num :
        return
    else :
        for i in range(0, n) :
            if visited[i] == 0 :
                tmp = current_num
                result.append(arr[i])
                visited[i] = 1
                if len(result) > 1 : 
                    tmp += map_list[result[-2]][i]
                    if map_list[result[-2]][i] != 0 :
                        func(i + 1, num + 1, tmp)
                else :
                    func(i + 1, num + 1, tmp)
                result.pop()
                visited[i] = 0

min_num = 1000000 * 10 + 1
func(0, 0, 0)
print(min_num)

1748번: 암호 만들기

한번에 맞을 수 있었으나..
프린트할 때 스페이스바 빼는걸 못보고 그대로 출력해버렸다.
sep=''를 넣어서 성공

import sys, copy
input = sys.stdin.readline

l, C = list(map(int, input().split()))
arr = list(input().split())

vowel = 'aeiou'
vowel_arr = []
not_vowel_arr = []
for c in arr :
    if c in vowel :
        vowel_arr.append(c)
    else :
        not_vowel_arr.append(c)

vowel_arr.sort()
not_vowel_arr.sort()

visited = [0] * C
result = []

vowel_list = []
not_vowel_list = []

my_result = []

def pick_arr(arr, idx, num) :
    if len(result) == num :
        if result[0] in vowel :
            vowel_list.append(copy.deepcopy(result))
        else :
            not_vowel_list.append(copy.deepcopy(result))

    else :
        for i in range(idx, len(arr)) :
            if visited[i] == 0 :
                result.append(arr[i])
                visited[i] = 1
                pick_arr(arr, i + 1, num)
                result.pop()
                visited[i] = 0

for i in range(2, l) :
    vowel_num = l - i
    not_vowel_num = i

    pick_arr(vowel_arr, 0, vowel_num)
    pick_arr(not_vowel_arr, 0, not_vowel_num)

    for n in vowel_list : 
        for m in not_vowel_list :
            word = n + m
            word.sort()
            # print(*word)
            my_result.append(word)

    vowel_list.clear()
    not_vowel_list.clear()

my_result.sort()
for i in my_result :
    print(*i, sep='')

14889번: 스타트와 링크

import sys
input = sys.stdin.readline

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

visited = [0] * n
start = []
minValue = (20 ** 2) * 1000

def sum_arr(team) :
    result_sum = 0
    for i in team :
        for j in team :
            result_sum += arr[i][j]
    return result_sum

def combination(idx) :
    global minValue
    if len(start) == n // 2 :
        link = []
        for i in range(n) :
            if not i in start :
                link.append(i)
        minValue = min(minValue, abs(sum_arr(start) - sum_arr(link)))
    else :
        for i in range(idx, n) :
            if visited[i] == 0 :
                visited[i] = 1
                start.append(i)
                combination(i + 1)
                visited[i] = 0
                start.pop()

combination(0)
print(minValue)

15661번: 링크와 스타트

start를 정한 뒤 link를 for문으로 넣어주는 방식으로 했었다. 여기서 시간초과가 나는 것 같아서 remove, insert 함수로 바꾸어주니 성공

import sys
input = sys.stdin.readline

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

visited = [0] * n
start = []
link = [x for x in range(n)]
minValue = (20 ** 2) * 1000

def sum_arr(team) :
    result_sum = 0
    for i in team :
        for j in team :
            result_sum += arr[i][j]
    return result_sum

def combination(idx, num) :
    global minValue
    if len(start) == num :
        # link = []
        # for i in range(n) :
        #     if not i in start :
        #         link.append(i)
        minValue = min(minValue, abs(sum_arr(start) - sum_arr(link)))
    else :
        for i in range(idx, n) :
            if visited[i] == 0 :
                visited[i] = 1
                start.append(i)
                removed_idx = link.index(i)
                link.remove(i)
                combination(i + 1, num)
                link.insert(removed_idx, i)
                visited[i] = 0
                start.pop()

for m in range(1, (n // 2) + 1) :
    combination(0, m)
print(minValue)

2529번: 부등호

<일 땐 현재 넣은 수보다 큰 수에서 후보를 찾아주고, >일 땐 작은 수에서 찾는 것으로 시간을 줄였다.

import sys, copy
input = sys.stdin.readline

k = int(input())
arr = list(input().split())

result = []
visited = [0] * 10

maxValue = 0
minValue = 99999999999
maxList = []
minList = []
def permutation(current_num, arr_idx, result_num) :
    global maxValue, minValue, minList, maxList
    if len(result) == k + 1 :
        if maxValue < result_num :
            maxList = copy.deepcopy(result)
            maxValue = result_num
        if minValue > result_num :
            minList = copy.deepcopy(result)
            minValue = result_num
    else :
        if arr[arr_idx] == '<' :
            for i in range(current_num + 1, 10) :
                if visited[i] == 0 :
                    visited[i] = 1
                    result.append(i)
                    permutation(i, arr_idx + 1, result_num * 10 + i)
                    visited[i] = 0
                    result.pop()
        elif arr[arr_idx] == '>' :
            for i in range(current_num - 1, 0 - 1, -1) :
                if visited[i] == 0 :
                    visited[i] = 1
                    result.append(i)
                    permutation(i, arr_idx + 1, result_num * 10 + i)
                    visited[i] = 0
                    result.pop()

for num in range(10) :
    result.append(num)
    visited[num] = 1
    permutation(num, 0, num)
    visited[num] = 0
    result.pop()

print(*maxList, sep='')
print(*minList, sep='')

14391번: 종이조각

참고 여부: OOO!!!! 이건 절대 혼자 못 풀 것 같기도 하고, 나중에 다시 혼자 풀이없이 풀어봐야겠다는 생각이 들어서 일단 참고 링크만 써놓으려 한다.

https://vixxcode.tistory.com/23