시행착오 기술 블로그

문제

풀이

memo[n] = memo[n-1] + memo[n-2] *2

여기서 *2 하는 이유는
2*1 직사각형이 오는 경우와 2*2 직사각형이 오는 경우 2가지 이기 때문

코드

n = int(input())

if n == 1:
    print(1)
else:
    memo = [0 for i in range(n + 1)]
    memo[0] = 1
    memo[1] = 1
    for i in range(2, n + 1):
        memo[i] = memo[i - 1] + memo[i - 2] * 2
    print(memo[n] % 10007)

문제

풀이

2xn 사각형

n=1 이면 f(1) =1
n=2 이면 f(2) = 1 + f(1) = 2
n=3 이면 f(3) = f(2) +f(1) = 3
n=4 이면 f(4) = f(3) + f(2) = 5

점화식
f(n) = f(n-1) + f(n-2)

코드

n = int(input())

if n <= 2:
    print(n)
else:
    memo = [0 for i in range(n + 1)]
    memo[1] = 1
    memo[2] = 2
    for i in range(3, n + 1):
        memo[i] = memo[i - 1] + memo[i - 2]

    print(memo[n] % 10007)

이 문제도 역시 재귀로 하면 시간초과 발생

bottom up 방식으로 반복문 이용하여 풀어내기

문제

풀이

조건2) 크기를 쪼갤 수 있다.
조건1) 작은 문제들이 큰 문제의 답을 알려준다. == 어딘가에 메모해놓아야 효율적 (memorization)

점화식
f(1) = 0번
f(2) = 1번
f(3) = 1번
f(4) => 4/2 => 2/2 => 1 = 2번 [f(4) = 1 + f(2) = 2번]
f(5) = 5-1 => ... f(4)와 동일 [f(5) = 1 + f(4) = 3번]



정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.


점화식을 세워보면
f(n) = min(f(n/3)+1, f(n/2)+1, f(n-1)+1)

코드

n = int(input())
memo = [0] * (n + 1)

memo[1] = 0
for i in range(2, n + 1):
    memo[i] = memo[i - 1] + 1

    if (i % 2 == 0) and (memo[i] > memo[i // 2] + 1):
        memo[i] = memo[i // 2] + 1
    if (i % 3 == 0) and (memo[i] > memo[i // 3] + 1):
        memo[i] = memo[i // 3] + 1

print(memo[n])

재귀로 풀면 시간초과 발생

memorization 이용하여 배열에 작은 문제의 값들을 다 저장하고 큰 문제를 풀때 가져다 쓰기

평일

하루 1문제씩 풀기

주말

하루 2문제씩 풀기

순서는 정하지 않고 풀되, 같은 알고리즘은 연속으로 풀기

수학

브루트포스

다이나믹 프로그래밍

다이나믹프로그래밍 2

큐와 그래프

BFS

시뮬레이션과 구현

프로그래머스 체육복

여분 체육복 O :  1   3   5

                    X :     2   4 

1번이 2번에게 빌려주고, 3번이 4번에게 빌려준다.

또는

3번이 2번에게 빌려주고, 5번이 4번에게 빌려준다.

위 과정에서 머릿속으로 그린 그림을 절차적으로 기술하는 것이 곧 알고리즘의 핵심이다.

탐욕법: 알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택한다. 탐욕스럽게!

[방법1]

학생의 수는 기껏해야 30명. 학생 수만큼 배열을 확보하고, 각자가 가지고 있는 체육복의 수를 기록한다.

그리고 번호 순서대로 스캔하며 빌려줄 관계를 정한다. 시간복잡도는 O(N)

- 단, n이 커지면 시간초과 문제가 발생한다.

- 또한 n배열로 인해 메모리가 매우 많이 필요하고

- n번을 순차탐색해야해서 비효율적이다.

def solution(n, lost, reserve):
	# 모두 1벌씩
    students = [1] * (n + 1) 
    
    # 잃어버린 경우
    for l in lost:
        students[l] -= 1
    
    # 여분 있는 경우
    for r in reserve:
        students[r] += 1
        
    # 앞뒤 확인하며 빌려줄 수 있는 경우 찾기
    for idx, s in enumerate(students):
        if s == 2: # 2벌
            if students[idx - 1] == 0: # 좌 확인
                students[idx - 1] += 1
                students[idx] -= 1
            elif (idx+1 <= n) and students[idx + 1] == 0: # 우 확인
                students[idx + 1] += 1
                students[idx] -= 1
    return len([i for i in students[1:] if i != 0])

[방법2] 

n이 매우 크다면? reserve 학생(K)은 매우 적다면? reserve 정렬 후, 하나하나 살펴보면서 빌려줄 앞, 뒤 학생을 찾는다.

이때 reserve의 길이를 K라고 하면 여벌의 체육복을 가져온 학생들을 정렬하는 데에 O(K * log K) 이다.

K만큼 O(K) 반복하면서 빌려줄 수 있는 다른 학생을 찾아서 처리한다. 해시 사용하면 O(1)만에 처리가 가능하다.

프로그래머스 완주하지 못한 선수

어떤 자료 구조를 택하느냐에 따라 시간복잡도가 달라진다.

(1) 인덱스로 이중 반복문을 이용해 하나씩 비교하는 방법: O(n^2)이 걸린다. => 

(2) 해시는 key를 기준으로 해시 테이블에 저장하는 방법 : 이름-등장횟수(동명이인의 수)를 key-value로 기록.

[방법1] 해시

파이썬에서 해시테이블은 dict()를 이용한다.

1. participant 배열에 있는 참가자들을 dict[key] += 1 이렇게 count를 한다.

2. completion 배열에 있는 완주자들은 dict[key] -= 1 이렇게 빼준다.

3. 그 결과 해시 테이블에는 완주하지 못한 사람은 숫자가 0이 아닐 것이다.

def solution(participant, completion):
    hash = dict()

    for p in participant:
        if p in hash:
            hash[p] += 1
        else:
            hash[p] = 1

    for c in completion:
        hash[c] -= 1

    for h in hash:
        if hash[h] != 0:
            return h

[방법2] 

약간의 아이디어만 떠올리면 가능한 단순 비교

participant 배열과 completion 배열을 각각 정렬해서 일대일 비교하는 과정

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

리모컨

문제 풀이

• 재귀호출을 이용한 완전탐색을 하려고 한다. 
• 채널은 무한대까지 있지만, 수빈이가 최대 500000까지 이동할 수 있다. 모든 버튼이 고장났다는 가정하에, 500000번으로 이동하려고 하면 +버튼으로 100 -> 500000 도 가능하지만 -버튼으로 999900 -> 500000도 가능하기 때문에 범위는 500000+499900 으로 지정함.
• possible 함수는 입력으로 들어온 number의 모든 자리를 확인하며 고장난 버튼이 없으면 자릿수를 반환해준다.
• 자릿수에 +또는-로 이동해야하는 거리를 더하면, 최소로 버튼을 누르는 경우가 완성된다.

소스 코드

# 골드 55
n = int(input())
m = int(input())
broken_btn = [False] * 10

###########################################################
# 이 부분 추가해야 완전탐색 방법으로 런타임에러 없이 통과가 된다.
# 고장난 버튼 0개인 경우
if m > 0:
    broken = list(map(int, input().split(' ')))
else:
    broken = []
###########################################################

for i in broken:
    broken_btn[i] = True

answer = abs(100-n)

def possible(number):
    if number == 0:
        if broken_btn[number]:
            return 0
        else:
            return 1
    len_num = 0
    while number > 0:
        c = number % 10
        if broken_btn[c]:
            return 0
        number = number//10
        len_num += 1

    return len_num

for i in range(500000+499900):
    len_num = possible(i)
    if len_num > 0:
        btn_press = abs(n-i)
        if answer > len_num + btn_press:
            answer = len_num + btn_press
print(answer)

날짜계산

문제 풀이

완전탐색을 이용하여 세개의 변수를 선언하고, 숫자를 1씩 증가시킨다.

입력받은 숫자와 같은 값까지 도달하면 현재 연도를 리턴해준다.

세자리 숫자의 시작은 1, 1, 1이고 범위는 각각 1~15, 1~28, 1~19 이다.

모듈러(%)를 이용해 나머지를 구하면 범위를 넘어가는 경우를 해결할 수 있다.

단, 문제가 있는데 %를 하면 0으로 가는데, 이 나라의 연도 시작이 1이라는 점이다.

따라서 범위를 살짝 바꿔보면

시작은 0, 0, 0 이고 범위는 0~14, 0~27, 0~18로 바꾸면 된다.

그리고 각각 %15, %28, %19를 하면 된다.

코드

# 실버5

e, s, m = list(map(int, input().split(' ')))
E, S, M = 0, 0, 0

year = 1

while True:
    if (E + 1 == e) and (S + 1 == s) and (M + 1 == m):
        break
    E = (E + 1) % 15
    S = (S + 1) % 28
    M = (M + 1) % 19
    year += 1
    
print(year)