코드 챌린지 4일차 - 재귀와 정렬

재귀 - 자신을 정의할 때 자기 자신을 참조하는 것 
함수에서 자기 자신을 호출한다!

def fibo(n):
	if n<= 2 : 
    	return 1
    return fibo(n-1) + fibo(n-2)

항상 무한 루프에 빠지지 않도록 잘 설정해야 한다!

 

정렬 - 데이터를 오름차순 및 내림차순 등 특정한 기준으로 정렬하는 것
삽입 - 앞에서부터 차례대로 비교하여 자신의 위치를 찾는다 = 구현 간단, n^2
버블 - 두 수를 바꾸는 swap를 많이 사용한다. = 느리지(n^2)만 간단
합병 - 
퀵 - 피벗을 사용하여 기준으로 정렬한다.
힙 - 최대 힙(부모 노드가 자식 노드보다 큰 트리)

C++ - intro Sort
Python - Tim Sort
JAVA - 병합, 팀 정렬 

 

트리 위의 게임

• 시간 제한: 1 초

정점 N개의 트리에서 두 사람이 게임을 진행하려 한다.
각 정점은 1번부터 N번 까지 번호가 매겨져 있고 루트노드는 1번 노드이다.
게임은 서로 턴을 번갈아 가며 진행되고 트리 위에 놓을 수 있는 말과 함께 진행된다.
두 사람의 점수는 모두 0점으로 시작한다.

각 턴마다 두 사람은 다음과 같은 작업을 반복한다.

• 현재 말이 놓여 있는 정점의 번호만큼 자신의 점수에 더한다.
• 현재 말이 놓여 있는 정점의 자식 정점이 없다면 그대로 게임을 종료한다.
  자식 정점이 존재한다면 자식 정점 중 원하는 자식 정점으로 말을 옮긴다.

게임이 종료되었을 때 선공의 점수가 후공의 점수보다 높거나 같다면 선공이 승리하고 아니라면 후공이 승리한다.
두 사람이 최적으로 플레이할 때, 처음 말이 놓여져 있는 정점의 번호에 따라 선공이 이기는지 후공이 이기는지 구해보자.

 

입력

• 첫째 줄에 정점의 수 N이 주어진다.
  
  1≤N≤100000
• 둘째 줄부터 N−1개의 줄에 간선을 나타내는 정수 u,v가 주어진다.
  
  1≤u,v≤N
• • 이는 u번 정점과 v번 정점을 잇는 간선이 존재한다는 뜻이다.

---

출력

• N개의 줄에 걸쳐 정답을 출력한다.
• i번째 줄에는 말의 시작위치가 i번 정점일 때의 결과를 출력한다.
• 선공이 이긴다면 1을 후공이 이긴다면 0을 출력한다.

---

입력 예시 1

5
1 3
2 1
3 4
5 1

출력 예시 1

1
1
0
1
1

입력 예시 2

6
1 3
1 2
3 5
3 6
2 4

출력 예시 2

1
0
0
1
1
1

 

 

 

import sys
sys.setrecursionlimit(10**6)

def dfs(node):
    if not tree[node]:  # 리프 노드
        return node

    max_diff = -float('inf')
    for child in tree[node]:
        child_diff = dfs(child)
        max_diff = max(max_diff, node - child_diff)
    
    return max_diff

# 입력 처리
n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    u, v = map(int, input().split())
    tree[u].append(v)

# 각 노드에서 시작했을 때의 결과 계산
results = []
for start in range(1, n+1):
    score_diff = dfs(start)
    results.append(1 if score_diff >= 0 else 0)

# 결과 출력
for result in results:
    print(result)

아니네......