태야

<내 코드>

N = int(input())
P = int(input())
# 인덱스 번호 맞추기 위해 한 줄 추가
graph = [[0]*(N+1) for _ in range(N+1)]
done = []

for _ in range(P):
    x, y = map(int, input().split())
    graph[x][y], graph[y][x] = 1, 1


def dfs(v):
    done.append(v)
    for k in range(1, N+1):  # 1 ~ n번까지
        if (k not in done) and (graph[v][k] == 1):
            dfs(k)

    return (len(done) - 1)  # 1번을 제외한 컴퓨터 수


print(dfs(1))

문제 자체는 DFS를 구현한다면 어렵지 않았다. 아직은 DFS를 자유롭게 구현하는게 힘들다...이 문제에서 인접행렬 방식을 이용해 DFS를 구현했다.

<내 코드>

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())
tri = [list(map(int, input().split())) for _ in range(n)]
k = 2
for i in range(1, n):
    for j in range(len(tri[i])):
        if j == 0:  # 가장 왼쪽값일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][j] + tri[i][j]
        elif j == len(tri[i])-1:    # 가장 오른쪽일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][-1] + tri[i][j]
        else:  # 양 끝값이 아닌, 중간일 경우, 대각선 왼쪽과 오른쪽 중 큰 값과 더함
            tri[i][j] = max(tri[i-1][j-1], tri[i-1][j]) + tri[i][j]
    k += 1
print(max(tri[n-1]))

규칙을 찾아서 재귀 형태의 점화식을 찾아내는 것이 중요했다. 삼각형의 가장 왼쪽과 오른쪽 값은 위의 값과 바로 더해주면 되고, 중간의 값들은 대각선 왼쪽과 오른쪽의 값 중 최댓값과 더해줬다. 

<내 코드>

n = int(input())
memo = [0 for _ in range(101)]

for i in range(0, 4):
    memo[i] = 1
for j in range(4, 6):
    memo[j] = 2

for _ in range(n):
    m = int(input())
    for k in range(6, m+1):  # 6 ~ m-1
        memo[k] = memo[k-1] + memo[k-5]

    print(memo[m])

피보나치 수열과 비슷한 맥락으로 규칙을 찾아 점화식을 세우면 간단하게 풀 수 있었다.

인덱스 0번 ~ 4번까지는 1과 2로 넣어주고 그 다음부터는 점화식을 통해 값을 구해나가는 구조였다. 인덱스 값을 0번째 부터 설정해서 뒤에서 조금 헷갈린거 말고는 크게 어렵지 않았다.

<내 코드>

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번째 피보나치 수를 구할 수 있다.

<내 코드>

def binarySearch(M, tree):
    start = 1
    end = max(tree)

    while start <= end:
        leng = 0
        mid = (start + end) // 2

        for i in tree:
            if i >= mid:
                leng += i - mid

        if leng >= M:
            start = mid + 1
        else:
            end = mid - 1

    return end


N, M = map(int, input().split())
tree = list(map(int, input().split()))

sortTree = sorted(tree)
print(binarySearch(M, sortTree))

이분 탐색 알고리즘을 이용해서 푸는 문제다. 알고리즘만 알고 있으면 생각보다 간단한 문제였다. 같은 코드로 채점 했는데 pypy3는 588ms가 걸리고 python3는 2984ms 가 걸리면서 다소 큰 차이가 있었다. 

<내 코드>

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 값을 출력하고 종료한다. 만약 찾고자 하는 값이 아니면 지우고 한 칸씩 땡긴다.