태야

<내 코드>

n = input().split('-')
result = 0

for i in n[0].split('+'):
    result += int(i)

for j in n[1:]:
    for k in j.split('+'):
        result -= int(k)

print(result)

적절한 괄호를 쳐서 최솟값을 만드는 문제다. 최솟값을 만들려면 -의 값이 커야 하기에 - 사이에 +로 연결된 값들을 다 더한 후 마지막 빼주면 최솟값을 만들 수 있다. 어떤 점에서 그리디 문제인지는 감이 오지 않는 문제다...

<내 코드>

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

print(memo[-1])

처음에 재귀호출을 통해 풀었을 때, 예상대로 시간초과가 났다. 

Bottom-up은 바닥에서 올라오는 것, 즉, 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것이다. 첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 풀면 세 번째 피보나치 수를 구하는 문제를 풀 수 있다. 두 번째 피보나치 수를 구하는 문제와 세 번째 피보나치 수를 구하는 문제를 풀면 네 번째 피보나치 수를 구하는 문제를 풀 수 있다....이걸 반복하면 n번째 피보나치 수를 구할 수 있다.

<내 코드>

n, k = map(int, input().split())
people = [i for i in range(1, n+1)]
key = 0
temp = k - 1
order = []
while people:
    key = (key+temp) % len(people)
    order.append(people.pop(key))

print('<'+', '.join(map(str, order))+'>')

순열 규칙을 찾으면 간단하게 해결되는 문제였다. 

<내 코드>

case = int(input())
for _ in range(case):
	# n : 자료 개수 , m : 찾고자 하는 자료 위치
    n, m = map(int, input().split())
    imp = list(map(int, input().split()))
    temp = [0 for _ in range(n)] #리스트 표현식으로 0인 리스트 생성
    temp[m] = 1 # 찾고자 하는 m번째를 1로 표시
    cnt = 0

    while imp:
        if imp[0] == max(imp):
            cnt += 1
            if temp[0] == 1:
                print(cnt)
                break
            else:
                imp.pop(0)
                temp.pop(0)
        else:
            imp.append(imp[0])
            temp.append(temp[0])
            del(imp[0])
            del(temp[0])

- 중요도를 표시하는 imp 입력을 리스트로 만든다.

- imp 리스트와 비교하기 위한 temp 리스트를 만든다.

- imp[0]이 젤 큰 값인지 판단해, 아니라면 imp, temp 첫 요소를 뒤로 보내고 한 칸씩 땡긴다.

- imp[0]이 최댓값이면서 찾고자 하는 값이면 cnt 값을 출력하고 종료한다. 만약 찾고자 하는 값이 아니면 지우고 한 칸씩 땡긴다.

재귀 호출은 함수가 자기 자신을 다시 호출하는 것을 뜻한다. 알고리즘 공부에 있어서 중요한 개념이므로 확실하게 공부해야 한다. 재귀 호출에서 중요한 것이 반드시 '종료 조건'이 있어야 한다는 것이다. 만약 종료 조건이 없으면 무한루프에 빠지기 때문이다.

재귀 호출의 일반적인 형태

def func(입력):
	if 입력 값이 충분히 작으면: #종료 조건
    	return 결과
    ...
    func(더 작은 입력 값)  	# 더 작은 값으로 재귀 호출
    ...
    return 결과

재귀 호출의 세 가지 요건

1. 함수 안에서 자기 자신을 다시 호출한다.
2. 재귀 호출할 때 인자로 주어지는 입력 크기가 작아진다.
3. 특정 종료 조건이 만족되면 재귀 호출을 종료한다. 즉, 종료 조건이 있어야 한다.

[예 제]

1. 1부터 n까지 더하기

def call_sum(n):
    if n <= 1:
        return n

    return n + call_sum(n-1)


print(call_sum(100))

함수 안에서 자기 자신을 계속해서 호출하는 방식으로 1부터 n까지 합을 구한다. 

2. 팩토리얼 구하기

def fact(n):
    if (n <= 1):
        return 1

    return n * fact(n-1)


print(fact(1))  # 1
print(fact(10))  # 10! = 3628800

종료 조건으로 n이 1과 같거나 작아지면 1을 리턴하게 해 마지막으로 1이 곱해지면서 결과를 리턴한다.

3. 최댓값 찾기

def find_max(nums, n):
    if n == 1:
        return nums[0]

    max_num = find_max(nums, n-1)

    if (max_num > nums[n-1]):
        return max_num
    else:
        return nums[n-1]


a = [17, 92, 18, 24, 35]
print(find_max(a, len(a)))  # 92

사실 리스트에서 최댓값, 최솟값을 구할 때 max(), min() 함수를 사용하면 쉽게 구할 수 있다.

<내 코드>

import sys
from collections import deque

n = int(sys.stdin.readline())
deque = deque()


def push(queque, x):
    deque.append(x)


def pop(deque):
    if(not deque):
        return -1
    else:
        return deque.popleft()


def size():
    return len(deque)


def empty():
    if(not deque):
        return 1
    else:
        return 0


def front():
    if(not deque):
        return -1
    else:
        return deque[0]


def back():
    if(not deque):
        return -1
    else:
        return deque[-1]


for i in range(n):
    oper = sys.stdin.readline().split()

    if (oper[0] == "push"):
        push(deque, oper[1])
    elif(oper[0] == "pop"):
        print(pop(deque))
    elif(oper[0] == "size"):
        print(size())
    elif(oper[0] == "empty"):
        print(empty())
    elif(oper[0] == "front"):
        print(front())
    elif(oper[0] == "back"):
        print(back())

이 문제는 시간 복잡도가 O(1)이 되어야 하는데, 일반적인 리스트의 pop() 함수를 사용하면 첫 번째 요소를 pop 할 때는 O(n)의 시간이 소요된다. 그래서 collections의 deque를 사용했다. pop 부분에서 popleft를 이용해 시간을 단축시킬 수 있다. deque는 스택과 큐를 합친 자료구조이다.

<내 코드>

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

dots = sorted(dots, key=lambda x: (x[1], x[0]))

for i in dots:
    print(*i)