자주 나오는 함수 정리

EX1. 배열 90도 회전

• 새 배열 = 기존 배열[n-j-1][i] 를 기억하기!

def rotate(a):
	n = len(a)
	tmp = [0 * N for _ in range(n)] # 회전 결과 저장 배열
    
    for i in range(n):
    	for j in range(n):
        	tmp[i][j] = a[n-j-1][i]

EX2. 순열 함수

def permutation(arr, r):
    
    # 순열을 저장할 배열
    result = []
    
    # 실제 순열을 구하는 함수
    def permute(p, index):
        if len(p) == r:
            result.append(p)
            return

        for idx, data in enumerate(arr):
            if idx not in index: 
				# list는 mutable이기 때문에 새로운 리스트를 넘겨준다.
            	permute(p + [data], index + [idx])
				
    permute([], [])
    
    return result

for r in permutation(['A', 'B', 'C', 'D'], 2):
    print(r)

    
# --- Result ---
# ('A', 'B')
# ('A', 'C')
# ('A', 'D')
# ('B', 'A')
# ('B', 'C')
# ('B', 'D')
# ('C', 'A')
# ('C', 'B')
# ('C', 'D')
# ('D', 'A')
# ('D', 'B')
# ('D', 'C')

EX3. 조합 함수

# 재귀적으로 조합 구현

def combination(arr, r):
    
    # 조합을 저장할 배열
    result = []
    
    # 실제 조합을 구하는 함수
    def combinate(c, index):
        if len(c) == r:
            result.append(c)
            return 
        
        for idx, data in enumerate(arr):
            # 중복되는 조합이 생성되지 않게 마지막으로 들어온 원소의 인덱스보다
            # 새로 추가하는 원소의 인덱스가 큰 경우만 조합을 생성한다.
            if idx > index:
                combinate(c + [data], idx)
    
    combinate([], -1)
    
    return result

for r in combination(['A', 'B', 'C', 'D'], 2):
    print(r)
    
# --- Result ---
# ['A', 'B']
# ['A', 'C']
# ['A', 'D']
# ['B', 'C']
# ['B', 'D']
# ['C', 'D']

구현 문제 풀이

🧡 백준 브론즈2 시험 감독

문제번호	언어	메모리	시간
13458	Python 3	145440 KB	772 ms

유의점

• 모든 시험장에는 메인 시험감독이 무조건 한 명은 있어야 한다(학생이 있든 없든)
• math는 Python 3.7 기준 표준 라이브러리다. > math.ceil(), math.floor() 사용 가능

import math
N = int(input())
A = list(map(int, input().split()))
B, C = map(int, input().split())

result = N
for i in range(N):
    result += max(math.ceil((A[i]-B) / C), 0)
print(result)

🧡 백준 실버3 퇴사

문제번호	언어	메모리	시간
14501	Python 3	31120 KB	44 ms

유의점

• DP를 풀 때, Top-down으로 풀지, Bottom-up으로 풀지 생각해보아야 한다
• Bottom-up으로 풀 때, for문의 매개변수를 잘 생각해보자(시작위치, 끝위치(포함안됨), 각 반복문마다 더할 수)

N = int(input())
T = []
P = []
for i in range(N):
    a, b = map(int, input().split())
    T.append(a)
    P.append(b)

# dp[i] i날까지 얻을 수 있는 최대 이익
dp = [0 for i in range(N+1)]

for i in range(N-1, -1, -1):
    if i + T[i] <= N: #인 경우에만 상담을 할 수 있음
        # i날에 상담을 안하는 것과, 상담을 하는 것 중 큰 것 선택
        dp[i] = max(dp[i+1], P[i] + dp[i + T[i]])
    else:
        dp[i] = dp[i+1]
print(max(dp))

🧡 백준 실버1 스타트와 링크

First Try

문제번호	언어	메모리	시간
14889	Python 3	59328 KB	4052 ms

해설

• 조합사용
• 시간이 오래 걸려서 백트래킹으로도 풀어보기로 함

def combination(arr, cnt):
    result = []

    def combi(add, idx):
        if len(add) == cnt:
            result.append(add)
            return
        for id, data in enumerate(arr):
            if id > idx:
                combi(add + [data], id)

    combi([], -1)
    return result

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

def power(member):
    full = 0
    for i in member:
        for j in member:
            if i != j:
                full += S[i-1][j-1]
    return full

result = 10e9
for members in combination(list(i for i in range(1, N+1)), N//2):
    # 뽑힌 멤버들의 능력치 구하기
    power1 = power(members)

    # 뽑히지 못한 멤버들의 능력치 구하기
    members2 = list(i for i in range(1, N + 1))
    for i in members:
        members2.remove(i)
    power2 = power(members2)
    # 차를 구해서 최소값이면 update
    result = min(result, abs(power2-power1))

print(result)

Second Try

문제번호	언어	메모리	시간
14889	Python 3	31120 KB	5440 ms

유의점

• 백트래킹 사용
• 백트래킹이 시간이 덜 걸릴 줄 알았지만 조합 사용보다 시간이 더 걸림
• 메모리를 절약하긴 했지만, 조합 방법을 메모리 최적화할 수 있을 것 같음

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
visited = [False for _ in range(N)]
result = 10e9

def dfs(depth, idx):
    global result
    # 종료 조건 => power 구하고 리턴함
    if depth == N//2:
        power1, power2 = 0, 0
        for i in range(N):
            for j in range(N):
                # 둘 다 visited 했으면 power1에 추가
                if visited[i] and visited[j]:
                    power1 += S[i][j]
                # 둘 다 not visited 면 power2에 추가
                elif not visited[i] and not visited[j]:
                    power2 += S[i][j]
        result = min(result, abs(power1-power2))
        return

    # 백트래킹
    for i in range(idx, N):
        if not visited[i]:
            visited[i] = True
            dfs(depth+1, i+1)
            visited[i] = False

dfs(0, 0)
print(result)

🧡 백준 실버1 연산자 끼워넣기

문제번호	언어	메모리	시간
14888	Python 3	KB	ms

유의점