def insertion(a):
	for cur in range(1, len(a)):  # 인덱스 0까지는 정렬이 되어있다고 치고 1부터 수행
		temp = a[cur]  # 자리를 찾아가려는 원소를 temp에 저장
		prev = cur - 1  # a[cur-1]이 먼저 비교대상이 될 것임
		while 0 <= prev and a[prev] > temp:  # 대소 관계가 맞을 때까지 위치 교환
			a[prev+1] = a[prev]  # 한 칸 뒤로 땡겨
			prev -= 1  # 교환해야 될 애를 더 찾아 나가기 위해 인덱스 1 줄이기
		a[prev+1] = temp  # 마지막으로 비교연산 한 곳+1의 위치에 삽입


arr = [3, 1, 4, 3, 9, 10, 0]
insertion(arr)
print(arr)

# Insertion Sort
# 두번째 원소부터 시작해서/앞에 위치한 애들과 비교를 해서/더 큰 애들을 뒤로 땡긴 후/순서가 맞는 곳에 삽입
# 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더해서 i+1개의 배열을 만드는 과정을 반복한다.
# bubble sort나 selection sort와는 달리 한 개짜리 배열에서 시작해서 그 크기를 하나씩 늘려 나가는 정렬이다.
# 시간복잡도: O(n^2)
# 공간복잡도: n
# 장점: 최선의 경우 O(n)으로 빠르다. 거의 다 정렬이 되어있는 경우 bubble이나 selection sort보다 효율적이다. 
#		추가적인 메모리를 필요로 하지 않는다(in-place). 중복된 원소가 있는 경우 원래 순서를 보장한다(stable)
# 단점: 최악의 경우 O(n^2)로 그닥 효율적이지 않다.

스위칭의 필요성

모든 장치에 서로 링크를 연결하는 것은 문제가 있다.

장치가 많아질수록(큰 네트워크일수록) 링크가 많이 필요해져 비용이 많이 들기 때문이다.

또, 링크의 대다수가 유휴시간이 많아져서 효율이 떨어진다.

→ 스위치를 두어서 여러 장치들을 이 스위치에 연결되도록 구성하고, 스위치가 그때 그때 필요할 때마다 두 개의 장치를 연결시켜주도록 한다.

스위칭이란?

그때 그때 필요할 때마다 송신자와 수신자를 연결시켜 주는 것

링크를 효율적으로 사용하고, 비용을 줄이기 위해 나타난 것이 스위치

스위치들이 연결되어 큰 규모의 네트워크를 만들 수 있다. 

스위칭 방식의 종류

1. 회선 교환

- 두 장치 사이에 물리적인 선을 연결하는 방식. 전화망(PSTN: Public Switched Telephone Network)

- 회선이 연결되면 데이터를 주고 받는 동안 계속 유지된다. 즉, 자원이 연결되어 있는 동안 계속 점유된다.

- 두 장치 사이에 고정된 속도를 갖는다.

- 연결을 설정하는데 시간이 소요되고, 그 이후에는 지연시간이 없다.

- 데이터 전송이 많은 경우 유용하다.

2. 메시지 교환

- 전달할 메시지 전체를 한 번에 인접 노드에게 모두 보낸다(메시지 단위로 스위칭). 메시지를 수신한 노드는 다음 노드로 메시지를 전달한다(Store and forward).

- 유휴 링크는 다른 메시지 전송에 쓸 수 있어서 효율적이다.

- 단점은 각 노드가 메시지를 저장할 공간을 확보하고 있어야 한다. (→패킷 교환의 등장)

3. 패킷 교환

- 전체 메시지를 각 노드가 수용할 수 있는 크기(패킷)로 잘라서 보내는 방식

- 한 순간에 트래픽량이 확 늘어나는 형태(bursty)에 적합하다.

- 전송 속도를 다르게 해서 우선순위 적용이 가능하다.

- 링크에 문제가 발생하면 중간에 다른 링크를 선택할 수 있다.

1) 데이터그램(Datagram) 방식

- 패킷 단위로 잘라서 보내는 것.

- 각 패킷이 서로 상관없이 독립적으로 처리 된다. 따라서 연결 설정 과정이 없다.

- 각 패킷이 서로 연관성이 없기 때문에 목적지에 순서와 상관없이 도착할 수 있다.

- IP

2) 가상회선(Virtual-circuit) 방식

- 데이터를 보내기 전에 연결 설정을 한다. 연결 설정을 할 때 가상 회선(경로)가 정해지고, 그 순서로만 전송된다. 즉, 동일한 경로로 순서대로 목적지에 도착한다.

- 회선 교환과의 차이점은 경로를 남들과 공유할 수 있다는 것이다.

2-1) SVC

- 가상 회선이 필요할 때만 연결되는 것

2-2) PVC

- 가상회선이 이미 연결 설정이 되어 있어 연결 설정이 없다.

https://developer.mozilla.org/ko/docs/Web/HTML/Element/article

https://developer.mozilla.org/ko/docs/Web/HTML/Element/section

article은 제목을 가진 독립적인, 재사용 가능한 범위를 나타낸다. 

section은 제목을 가진 범위를 나타낸다.

div는 일반적인 구역을 나타낸다.

범위는 article < section < div 이다.

https://developer.mozilla.org/ko/docs/Web/HTML/Element/Heading_Elements

- 제목을 나타낼 때 사용한다.

- <h1></h1> 와 같이 사용

사용 시 주의사항

* h1부터 h6까지 기본 크기를 가지고 있지만 css에서 크기를 재지정하고 사용하는 것이 바람직하다. 단, 글자를 키우기 위해서 h 태그를 사용하지는 않는다. '제목'이라는 기능에 충실하도록 써야 한다.

* 단계를 건너뛰지 않는다. (h1 하위에 바로 h3을 놓는 것 등을 하지 않는다) 브라우저들이 해석하면서 문제가 생길 수 있기 때문.

* h1은 페이지당 하나만 사용하는 것이 바람직하다.

https://developer.mozilla.org/ko/docs/Web/HTML/Element

블록 요소

- div, h1, p 등

- 사용 가능한 최대 가로 너비를 시작한다.

- 크기를 지정할 수 있다.

- width 100%; height: 0;로 시작한다고 생각하면 된다.

- 수직으로 쌓인다.

- margin, padding 위, 아래, 좌, 우 사용 가능

- 레이아웃을 잡는 용도

인라인 요소

- span, img 등

- 필요한 만큼의 너비를 사용한다.

- 크기를 지정할 수 없다.

- width 0; height: 0; 로 시작한다고 생각하면 된다.

- 수평으로 쌓인다.

- margin, padding 위, 아래는 사용할 수 없다. (padding의 아래는 시각적으로 표현이 되지만 실제로는 다른 요소와의 거리를 부여하지 못한다.)

- 텍스트를 작업하는 용도

블록 요소, 인라인 요소는 css의 display 속성으로 변경 가능하다.

http://boj.kr/1167 

맨 처음에는 인접 행렬을 통해서 완전 탐색을 하려고 했지만 메모리 초과가 났다.

우선 인접 행렬을 쓰면 메모리 초과가 난다. 인접 리스트를 써야 한다.

간선에 가중치가 존재하기 때문에 adj[시작노드] = [도착노드, 노드 간 거리] 이런 식으로 인접 리스트를 구성해주었다.

그리고 완전 탐색을 하면 아마 시간 초과가 날 것이다. 여기서는 특정 알고리즘(?)이 필요한데,

트리에서 아무 노드나 잡아서 그 노드에서 가장 먼 노드를 구한 후, 그 노드에서 또 가장 먼 노드를 구하면 그게 트리의 지름이 된다는 것이다.

생각을 해 보면 아무 노드나 잡은 후 가장 먼 노드를 구하면 루트나 리프 노드일 것이다. 거기서부터 가장 먼 노드를 구하면 그 사이 거리가 트리에서 가장 긴 거리가 될 것이다.

그러니까...DFS를 두 번 도는 이유는 첫번째는 루트나 리프, 어쨌든 끝점을 구하기 위해서라고 해도 될 것 같다. 두번째는 거기서부터 제일 먼 점을 구하는 거고.

일단 트리의 지름을 구하는 알고리즘은 이렇고, 한 노드에서 가장 먼 노드를 구하는 것도 은근 일이다.

나는 최단경로찾기 할 때처럼 max_dist 를 전역변수로 두고, DFS로 계속해서 자식 노드를 찾아가되 리프 노드를 발견하면 거리를 비교해 max_dist를 갱신하는 방식으로 풀었다.

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


def dfs(parent, dist, visited):
    global max_dist
    visited[parent] = 1
    leaf = True
    for child in adj[parent]:  # child = [노드번호, 거리]
        if not visited[child[0]]:
            leaf = False
            dfs(child[0], dist+child[1], visited)
    if leaf:  # leaf or root
        if max_dist[1] < dist:
            max_dist = [parent, dist]


n = int(input())

adj = {i: [] for i in range(1, n+1)}  # 인접 리스트
for _ in range(n):  # 입력 받기
    tmp = list(map(int, input().split()))
    start = tmp[0]
    endpoint = 1
    while tmp[endpoint] != -1:
        adj[start].append([tmp[endpoint], tmp[endpoint+1]])  # adj[시작점] = [[도착점, 거리], ...]
        endpoint += 2

max_dist = [-1, float('-inf')]  # [노드 번호, 거리]
visited = [0 for _ in range(n+1)]
dfs(1, 0, visited)  # 아무 점에서부터 제일 먼 점을 찾는다. 여기서는 1을 선택

max_dist[1] = float('-inf')  # 위에서 구한 점으로부터 최대 거리를 구하기 위해 값 초기화
visited = [0 for _ in range(n+1)]
dfs(max_dist[0], 0, visited)  # 아까 아무 점에서 제일 먼 점을 구했으면, 그 점에서 제일 먼 점을 또 구한다

print(max_dist[1])

http://boj.kr/11725 

우선 주어진 입력을 인접 딕셔너리로 바꾼다. 주어진 입력에 방향이 없으므로 양쪽 다 인접 딕셔너리에 추가해야 한다.

그런 다음 루트인 1에서부터 find_parent 를 시작한다.

find_parent에서는 1의 자식을 순회하면서 그 자식의 부모가 1이라고 표시한다.

첫번째 테스트케이스에서 1의 자식은 4, 6이다. line 6에서 4와 6을 차례로 순회하게 되는데, 

line 8에서 각각 parent[4] = 1, parent[6] = 1 이라고 표시하게 되서 부모를 저장할 수 있게 된다.

그리고 4와 6을 다시 부모 삼아서 find_parent를 호출한다. 더 이상 자식이 없을 때까지 호출된다.

1의 자식이 4와 6이라고 했지만 주어진 입력을 인접 딕셔너리로 바꿀 때 양방향으로 추가해줬으므로 4와 6의 자식이 1이기도 한데, visited 배열에 방문 표시를 해줘서 사이클이 생기지 않도록 한다.

import sys


def find_parent(node, graph):
    visited[node] = True
    for child in graph[node]:
        if not visited[child]:
            parent[child] = node
            find_parent(child, graph)


def solution(lst):
    tree = {i: [] for i in range(1, n+1)}  # 인접 딕셔너리 (0은 제외)
    for a, b in lst:
        tree[a].append(b)  # 주어진 입력에 방향이 없으므로 양쪽 다 추가
        tree[b].append(a)

    visited[1] = True
    find_parent(1, tree)  # 루트=1에서부터 출발

    for i in range(2, len(parent)):
        print(parent[i])


sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
n = int(input())
adj = [list(map(int, input().split())) for _ in range(n-1)]  # 입력
visited = [0 for _ in range(n+1)]  # 0(제외), 1~7
parent = [0 for _ in range(n+1)]
solution(adj)