문제를 보았을때 대략 단계가 있는 그래프 형태를 생각했습니다. 각 학생들이 저런식으로 있고, 1번 레이어는 의존성이 없는 학생들, 2번 레이어는 최대 1번 레이어에 의존성을 가지는 학생들, n+1번 레이어는 커야 n번 레이어에 의존성을 가지는 학생들입니다. 저런식으로 분류가 가능하다면, 각 레이어들을 순서대로 출력하는 방식으로 문제를 해결할 수 있습니다. 다만 가장 간단한 방식으로 순서대로 구현해보기로 했습니다. 우선 학생수가 32000명이니, 32000^2 = 10억 정도로 가능성이 있다고 봤습니다. 브루트 포스 방식 student_left = student_count for i in range(student_count): if student_left == 0: break for student in s..
BOJ 30049 영업의 신 문제에 대한 글입니다. 문제 입력은 조금 복잡해 보일 수 있으나 1 ~ N+2번 줄에서 base 입력을 받고, N+3번 줄부터 매출 변경에 관한 입력을 받으며 입력을 받을 때마다 계산하여 답을 출력해 주는 문제입니다. 크게 어려운 부분은 없는 구조이나, 관건은 시간복잡도를 잘 맞추는 것입니다. 조건으로 인하여 구현에 번거로운 부분 없이 편하게 문제를 풀 수 있습니다. 초기 입력 부분은 인원 300명에 가게 10000명으로 많아야 300만 정도의 입력을 받지만, N+3번부터 들어가는 계산은 N = 1,000,000 이기에 마지막 부분의 시간복잡도를 잘 고려해서 문제를 풀어야 합니다. 저의 초기 코드는 아래와 같은 방식으로 작성했습니다. int time; cin >> time; ..
이진 트리는 노드들이 최대 2개의 자식 노드를 가지는 트리를 말합니다. 이러한 이진 트리를 순회하는 방법에는 전위 순회, 중위 순회, 후위 순회가 있습니다. 전위 순회 (Pre-order traversal) : 루트 노드부터 시작하여, 루트를 방문하고 왼쪽 서브 트리를 순회하고, 오른쪽 서브 트리를 순회합니다. 순서는 루트 -> 왼쪽 -> 오른쪽입니다. (예시: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) 중위 순회 (In-order traversal) : 왼쪽 서브 트리부터 시작하여, 왼쪽 서브 트리를 순회하고, 루트를 방문하고, 오른쪽 서브 트리를 순회합니다. 순서는 왼쪽 -> 루트 -> 오른쪽입니다. (예시: 3 -> 2 -> 5 -> 4 -> 6 -> 1 -> 8 -> 7)..
