Skip to content

Latest commit

 

History

History
621 lines (390 loc) · 14.1 KB

_백준_강의_연습(2)_브루트포스_순열.md

File metadata and controls

621 lines (390 loc) · 14.1 KB

2529번: 부등호

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다.

제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력 (모든 입력에 답은 항상 존재)

## 2529번: 부등호
#### 첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 
#### 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력 (모든 입력에 답은 항상 존재)


def next_permutation(a):
    # 1) 뒤에서부터 시작해서 처음으로 내림차순(비오름차순)을 어기는 인덱스 찾기
    i = len(a)-1
    while i>0 and a[i-1] >= a[i]:
        i -= 1

    if i <= 0: ## 종료 조건(맨 첫 숫자까지 다 돌았는데 모두 '내림차순'인 경우 => 이미 '가장 마지막 순열')
        return False


    # 2) 기준점 뒤의 숫자들 중 가장 큰 수를 현재 i-1 번 숫자와 swap
    j = len(a)-1
    while a[i-1] >= a[j]:
        j -= 1

    a[i-1], a[j] = a[j], a[i-1]


    # 3) 현재 i부터 마지막까지 숫자 뒤집기
    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

    return True




def prev_permutation(a):
    # 1) 뒤에서부터 시작해서 처음으로 내림차순(비오름차순)을 어기는 인덱스 찾기
    i = len(a)-1
    while i>0 and a[i-1] <= a[i]:
        i -= 1

    if i <= 0: ## 종료 조건(맨 첫 숫자까지 다 돌았는데 모두 '내림차순'인 경우 => 이미 '가장 마지막 순열')
        return False


    # 2) 기준점 뒤의 숫자들 중 가장 큰 수를 현재 i-1 번 숫자와 swap
    j = len(a)-1
    while a[i-1] <= a[j]:
        j -= 1

    a[i-1], a[j] = a[j], a[i-1]


    # 3) 현재 i부터 마지막까지 숫자 뒤집기
    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

    return True


def check(perm, a):
    for i in range(len(a)):
        if a[i]=='<' and perm[i] > perm[i+1]:
            return False
        if a[i]=='>' and perm[i] < perm[i+1]:
            return False

    return True # 모두 만족해야 비로소 True



# 입력
k = int(input())
a = list(input().split()) # 입력으로 주어지는 k개의 부등호 리스트


# 답 출력
small = [i for i in range(0, k+1)] # 012...k 부터 시작
big = [9-i for i in range(0, k+1)] # 987...(9-k+1) 부터 시작


while True: ## 최소 정수 찾기
    if check(small, a):
        break # 답 찾음

    if not next_permutation(small):
        break # 다음 순열 존재 안 할 때



while True: ## 최대 정수 찾기
    if check(big, a):
        break # 답 찾음

    if not prev_permutation(big):
        break # 이전 순열 존재 안 할 때


print(''.join(map(str, big)))
print(''.join(map(str, small)))
2
< >
897
021

big = [9-i for i in range(0, k+1)]

big
[9, 8, 7]
  • <재귀>로도 구현 가능
  • 백트래킹 쓸 수 있어, 더 빠름
## 1339번: 단어 수학
#### 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
#### N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.




# (파이썬 시간초과)

def next_permutation(a):
    # 1) 뒤에서부터 시작해서 처음으로 내림차순(비오름차순)을 어기는 인덱스 찾기
    i = len(a)-1
    while i>0 and a[i-1] >= a[i]:
        i -= 1

    if i <= 0: ## 종료 조건(맨 첫 숫자까지 다 돌았는데 모두 '내림차순'인 경우 => 이미 '가장 마지막 순열')
        return False


    # 2) 기준점 뒤의 숫자들 중 가장 큰 수를 현재 i-1 번 숫자와 swap
    j = len(a)-1
    while a[i-1] >= a[j]:
        j -= 1

    a[i-1], a[j] = a[j], a[i-1]


    # 3) 현재 i부터 마지막까지 숫자 뒤집기
    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

    return True



def calc(a, letters, d):
    m = len(letters)
    ans = 0 # 모든 n행의 전체 합

    ## 알파벳에 d[i] 배열 순서대로 수 배정하기 (딕셔너리 이용) 
    alpha = dict()
    for i in range(m):
        alpha[letters[i]] = d[i]

    ## 알파벳 별 숫자 배정에 따른 전체 수의 합
    for row in a:
        now = 0 # 행에서 합

        for x in row:
            now = 10*now + alpha[x] # 행에서 합

        ans += now # 모든 n행의 전체 합


    return ans



# 입력
n = int(input())
a = [''] * n

letters = set()
for i in range(n):
    a[i] = input()
    letters |= set(a[i]) # |= : 연산과 동시에 할당


# letters를 셋에서 리스트로 변경
letters = list(letters)

m = len(letters)
d = [i for i in range(9, 9-m, -1)] # 9876.. 부터 시작
d.sort()

ans = 0
while True:
    res = calc(a, letters, d)

    if ans < res:
        ans = res ## 최대합 비교

    if not next_permutation(d):
        break


print(ans)
2
AAA
AAA
1998

# 입력
n = int(input())
a = [''] * n

letters = set()
for i in range(n):
    a[i] = input()
    letters |= set(a[i]) # |= : 연산과 동시에 할당


# letters를 셋에서 리스트로 변경
letters = list(letters)

m = len(letters)
d = [i for i in range(9, 9-m, -1)] # 9876.. 부터 시작
d.sort()

ans = 0
while True:
    res = calc(a, letters, d)

    if ans < res:
        ans = res ## 최대합 비교

    if not next_permutation(d):
        break


print(ans)
2
GCF
ACDEB
99437

# 이전 순열 시도 (파이썬 시간초과)

def prev_permutation(a):
    # 1) 뒤에서부터 시작해서 처음으로 내림차순(비오름차순)을 어기는 인덱스 찾기
    i = len(a)-1
    while i>0 and a[i-1] <= a[i]:
        i -= 1

    if i <= 0: ## 종료 조건(맨 첫 숫자까지 다 돌았는데 모두 '내림차순'인 경우 => 이미 '가장 마지막 순열')
        return False


    # 2) 기준점 뒤의 숫자들 중 가장 큰 수를 현재 i-1 번 숫자와 swap
    j = len(a)-1
    while a[i-1] <= a[j]:
        j -= 1

    a[i-1], a[j] = a[j], a[i-1]


    # 3) 현재 i부터 마지막까지 숫자 뒤집기
    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

    return True



def calc(a, letters, d):
    m = len(letters)
    ans = 0 # 모든 n행의 전체 합

    ## 알파벳에 d[i] 배열 순서대로 수 배정하기 (딕셔너리 이용) 
    alpha = dict()
    for i in range(m):
        alpha[letters[i]] = d[i]

    ## 알파벳 별 숫자 배정에 따른 전체 수의 합
    for row in a:
        now = 0 # 행에서 합

        for x in row:
            now = 10*now + alpha[x] # 행에서 합

        ans += now # 모든 n행의 전체 합


    return ans



# 입력
n = int(input())
a = [''] * n

letters = set()
for i in range(n):
    a[i] = input()
    letters |= set(a[i]) # |= : 연산과 동시에 할당


# letters를 셋에서 리스트로 변경
letters = list(letters)

m = len(letters)
d = [i for i in range(9, 9-m, -1)] # 9876.. 부터 시작


ans = 0
while True:
    res = calc(a, letters, d)

    if ans < res:
        ans = res ## 최대합 비교

    if not prev_permutation(d):
        break


print(ans)
2
GCF
ACDEB
99437

# 입력
n = int(input())
a = [''] * n

letters = set()
for i in range(n):
    a[i] = input()
    letters |= set(a[i]) # |= : 연산과 동시에 할당


# letters를 셋에서 리스트로 변경
letters = list(letters)

m = len(letters)
d = [i for i in range(9, 9-m, -1)] # 9876.. 부터 시작
d.sort()

ans = 0
while True:
    res = calc(a, letters, d)

    if ans < res:
        ans = res ## 최대합 비교

    if not prev_permutation(d):
        break


print(ans)
2
AAA
AAA
1998
  • <그리디>로도 구현 가능

14888번: 연산자 끼워넣기

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

(식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.)

## 14888번: 연산자 끼워넣기
#### N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
#### 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 



def next_permutation(a):
    # 1) 뒤에서부터 시작해서 처음으로 내림차순(비오름차순)을 어기는 인덱스 찾기
    i = len(a)-1
    while i>0 and a[i-1] >= a[i]:
        i -= 1

    if i <= 0: ## 종료 조건(맨 첫 숫자까지 다 돌았는데 모두 '내림차순'인 경우 => 이미 '가장 마지막 순열')
        return False


    # 2) 기준점 뒤의 숫자들 중 가장 큰 수를 현재 i-1 번 숫자와 swap
    j = len(a)-1
    while a[i-1] >= a[j]:
        j -= 1

    a[i-1], a[j] = a[j], a[i-1]


    # 3) 현재 i부터 마지막까지 숫자 뒤집기
    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

    return True




# (문제 조건) 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.
def div(a, b):
    if a < 0:
        return -(abs(a)//b)

    else:
        return a//b



def calc(a, b):
    ans = a[0]
    for i in range(1, len(a)):
        if b[i-1]==0:
            ans += a[i]

        if b[i-1]==1:
            ans -= a[i]

        if b[i-1]==2:
            ans *= a[i]

        if b[i-1]==3:
            ans = div(ans, a[i])

    
    return ans




# 입력
n = int(input())
a = list(map(int, input().split())) # 입력으로 주어지는 n개의 수
cnts = list(map(int, input().split())) # 사용가능한 n-1개의 각 연산자 별 갯수


b = []
for i, cnt in enumerate(cnts):
    for k in range(cnt):
        b.append(i)


# 답 구하기
ans = []

while True:
    temp = calc(a, b)
    ans.append(temp)

    if not next_permutation(b):
        break ## 다음 순열 더이상 존재 안하면 종료



print(max(ans))
print(min(ans))
3
3 4 5
1 0 1 0
35
17
  • <재귀>로도 구현 가능

14889번: 스타트와 링크

축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다. (팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.)

## 14889번: 스타트와 링크
#### 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
#### 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다. (팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.)


def next_permutation(a):
    # 1) 뒤에서부터 시작해서 처음으로 내림차순(비오름차순)을 어기는 인덱스 찾기
    i = len(a)-1
    while i>0 and a[i-1] >= a[i]:
        i -= 1

    if i <= 0: ## 종료 조건(맨 첫 숫자까지 다 돌았는데 모두 '내림차순'인 경우 => 이미 '가장 마지막 순열')
        return False


    # 2) 기준점 뒤의 숫자들 중 가장 큰 수를 현재 i-1 번 숫자와 swap
    j = len(a)-1
    while a[i-1] >= a[j]:
        j -= 1

    a[i-1], a[j] = a[j], a[i-1]


    # 3) 현재 i부터 마지막까지 숫자 뒤집기
    j = len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

    return True


# 입력
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]

# 첫 순열 만들기
b = [0 if i< n//2 else 1  for i in range(n)] # 00...11...부터 시작

ans = -1
while True:
    # permute인 b배열에 따라 스타트, 링크 팀에 배정
    first = []
    second = []

    for i in range(n):
        if b[i] == 0:
            first.append(i)
        else:
            second.append(i)



    # 답 구하기
    one = 0
    two = 0
    
    for i in range(n//2):
        for j in range(n//2):
            if i == j:
                continue # pass

            one += s[first[i]][first[j]]
            two += s[second[i]][second[j]]


    diff = abs(one - two)
    if ans==-1 or ans > diff:
        ans = diff # 최소합 비교



    # 다음 순열
    if not next_permutation(b):
        break # (종료 조건)




print(ans)
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0
0