태야

<내 코드>

def dfs(v):
    done.append(v)  # 방문한 노드 추가
    # print(done)
    # 해당 행(노드) 탐색(1행 ~ n행)
    for i in range(1, n+1):
        if (i not in done) and (matrix[v][i] == 1):
            dfs(i)

    return done


def bfs(start):
    queue = [start]
    done = [start]

    while queue:
        v = queue.pop(0)
        for i in range(1, n+1):
            if (i not in done) and (matrix[v][i] == 1):
                queue.append(i)
                done.append(i)

    return done


n, m, v = map(int, input().split())
done = []
matrix = [[0]*(n + 1) for _ in range(n + 1)]

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

print(*dfs(v))
print(*bfs(v))

그래프를 표현하기 위해 여기서는 '인접 행렬' 방식으로 구현했다. DFS(깊이 우선 탐색)은 주로 스택과 재귀를 통해 구현하고 BFS(너비 우선 탐색)은 큐로 구현을 많이 한다.

<내 코드>

N, M = map(int, input().split())
cnt_block = 1


if N == 1:
    cnt_block = 1
elif N == 2:
    if (M >= 7):
        cnt_block = 4
    else:
        cnt_block = (M+1) // 2

elif N >= 3:
    if(M >= 7):
        cnt_block = (M - 2)
    elif(M >= 4):
        cnt_block = 4
    else:
        cnt_block = M

print(cnt_block)

경우 별로 따져줘야 할 조건이 까다로웠다... 문제 자체는 어렵지 않으나 경우 별로 조건을 잘 못하면 머리가 복잡해지는 문제다..

<내 코드>

N = int(input())
H = list(map(int, input().split()))
result = [0] * N

for i in range(N):
    cnt_zero = 0

    for j in range(N):
        if cnt_zero == H[i] and result[j] == 0:
            result[j] = i + 1  # 수 1 ~ N
            break
        elif(result[j] == 0):
            cnt_zero += 1

print(*result)

입력 값으로 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. 그리고 줄을 선 순서대로 키를 출력하면 된다. 

# result
# 입력: [2, 1, 1, 0]
[0, 0, 1, 0]
[0, 2, 1, 0]
[0, 2, 1, 3]
[4, 2, 1, 3]

차례대로 각자 왼쪽에 큰 사람이 몇 명인지를 0의 개수로 판단해서 자리에 넣어준다. 예를 들어 왼쪽에 2명이 있다 하면 결과값 배열에 [0, 0, 현재,...] 즉, 자신보다 큰 2명의 자리를 비워두고 자리에 들어가면 된다. 그렇게 되면 다음 사람은 앞전보다 큰 사람이기 때문에 앞사람 위치는 무시하고 자신보다 큰 사람 수와 0의 수만 같으면 그 자리에 들어가면 된다.

<내 코드>

N = int(input())

weights = [int(input()) for _ in range(N)]
weights.sort(reverse=True)  # 내림차순


for i in range(N):
    weights[i] = weights[i] * (i+1)

print(max(weights))

문제 접근 방법

- 로프를 병렬로 연결하면 각 로프에는 w/k만큼의 동일한 중량이 걸린다.

- 즉, 가장 작은 무게를 들 수 있는 로프가 들 수 있는 질량 * 병렬연결 로프 개수 = 최종 무게

- 가장 무거운 무게를 들 수 있는 로프부터 내림차순으로 정렬한다.

처음에는 너무 어렵게 접근해서 복잡하게 생각했다. 그래서 디큐를 활용해 하나씩 빼고 넣고 하려고 했다가 실패했다. 이렇게 단순하게 풀릴지는... 후..