hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
피보나치 힙 구조
피보나치 힙은 최소-힙 특성을 만족시키는 트리들을 모아 놓은 것이다. 즉, 자식의 키는 항상 부모의 키보다 크거나 같다. 이것은 최소 키가 항상 트리들 중 한 트리의 루트에 있다는 것을 의미한다.
이항 힙에 비해, 피보나치 힙의 구조는 좀더 유연하다. 트리는 규정된 모양을 가지지 않는다. 극단적인 경우, 힙의 모든 구성요소가 서로 떨어진 별개의 트리에 존재할 수도 있다. 이러한 유연성으로 인해, 일부 연산은 “게으른” 방식으로 수행할 수 있다. 즉 나중 연산으로 작업을 연기(뒤로 미룸)하는 방식이다. 예를 들어, 힙의 병합(merge)은 두개의 리스트로 구성된 트리를 단순히 결합함으로써 가능하다. 그리고 키 감소 연산(decrease key operation)은 이 노드의 부모로부터 노드를 절단한 후, 새로운 트리를 형성하는 식으로 수행한다.
피보나치 힙 구조
그러나, 요구되는 실행시간을 달성하기 위해 어느 시점에 어떤 순서가 힙에 도입될 필요가 있다. 특히, 노드의 degree(여기서 degree란 자식의 수를 의미한다)가 상당히 낮게 유지된다. 즉 모든 노드는 degree가 많아야O(log n)이 되며, degree가 k인 노드를 루트로 하는 하위트리의 크기는 적어도Fk+2이다. 여기서Fk 은 k번째 피보나치 수이다. 이것은 루트가 아닌 노드(non-root node)에서는 최대 하나의 자식을 절단할 수 있다는 규칙에 의해 달성된다.
두번째 자식이 절단될 때, 이 노드 자체는 이것의 부모로부터 절단될 필요가 있으며, 이것이 새로운 트리의 루트가 된다. (아래의 Proof of degree bounds 참조). 최솟값 삭제 연산 (delete minimum)을 수행하면 트리의 수가 감소되는데, 이 최솟값 삭제 연산에서 트리가 함께 연결(link) 되기 때문이다.
유연한 구조로 인해 그 결과, 어떤 연산은 긴 시간이 소요될 수 있으나, 반면 다른 연산은 매우 빠르게 수행된다.
피보나치 힙 구조
분할 상환된 실행시간 분석을 위해, 우리는 잠재비용 방법(potential method)을 사용하였는데, 매우 빠른 연산을 실제 소요되는 시간보다 약간 더 긴 시간이 소요되는 것처럼 하였다. 이때 추가된 시간을 나중에 결합하고, 실제 실행시간에서 감하였다. 잠재비용 함수를 이용하여 이후에 사용을 위해 아껴두었던 시간의 양을 어떤 주어진 시점에 측정한다.
피보나치 힙의 잠재비용은 다음과 같다.
Potential = t + 2m
여기서 t는 피보나치 힙 내의 트리 수이며, m 은 표시(mark)된 노드의 수이다.
어떤 노드가 만일 자신의 자식 중 적어도 하나가 절단되었다면 이 노드를 표시(mark)한다. 왜냐하면 이 노드는 다른 노드 (모든 루트는 표시되지 않는다)의 자식으로 만들어졌기 때문이다. 어떤 연산에 대한 분할상환된 시간은 실제 시간과 잠재비용의 차이에 c를 곱한 값을 더하여 구한다. 이때 c는 상수이다 (실제 시간에 대한 O notation에서 매치되는 상수 요소를 찾아 선택한다)
그러므로, 힙 내에서 각 트리의 루트는 한 단위의 시간을 보유(store)하게 된다. 이렇게 보유한 한 단위의 시간을, 나중에 이 트리를 다른 트리에 연결(link)할 때 사용할 수 있다. 그렇게 되면 결국 0 분할상환된 시간 안에 트리를 연결하게 된다. 표시된 각 노드 또한 두 단위의 시간을 보유(store) 한다. 한 단위 시간은 이 노드를 자신의 부모에서 절단할 때 사용할 수 있다. 만일 이 일이 발생하면, 이 노드는 부모가 되고, 나머지 두 번째 시간 단위는 이 노드 안에 여전히 보유한다. 다른 루트 노드가 하나의 시간 단위를 보유한 것처럼 말이다.
피보나치 힙 연산의 구현
삭제와 결합을 빠르게 수행하기 위해, 모든 트리의 루트는 circular, doubly linked 리스트를 사용하여 연결한다. 각 노드의 자식들 또한circular, doubly linked 리스트를 이용해 연결한다. 각 노드 별로, 우리는 이 노드의 자식 노드 수, 그리고 이 노드가 표시된 노드인지 여부를 유지한다. 또한 우리는 최소 키를 포함하고 있는 루트에 대한 포인터를 유지한다.
피보나치 힙 최솟값 찾기
최솟값 찾기 연산은 이제 쉬워지는 것은 최소 키를 가진 루트 노드에 대한 포인터를 유지하기 때문이다. 이것이 힙의 잠재비용을 변경하지는 않는다. 따라서 실제 비용 및 분할상환된 비용 모두 상수(일정한 값)이다.
앞서 언급하였듯이, merge 연산은 두 힙의 트리 루트의 리스트를 결합하여 쉽게 구현 가능하다. 상수 시간 안에 이 연산이 수행될 수 있으며 잠재 비용은 변함없다. 따라서 이것 역시 분할상환 시간을 상수로 만든다.
피보나치 힙 삽입
삽입 연산은 하나의 구성요소를 가지고 새로운 힙을 생성한 후, 병합함으로써 수행된다. 이러한 삽입 연산에는 상수 시간이 소요되며, 잠재비용은 1만큼 증가하는데, 트리의 수가 증가되기 때문이다. 분할상환된 비용은 그러므로 여전히 상수이다.
삽입의 좀더 상세한 그림은 아래와 같다.
피보나치 힙 삽입
의사코드는 아래와 같다.
1 degree[x] 0
2 p[x] NIL
3 child[x] NIL
4 left[x] x
5 right[x] x
6 mark[x] FALSE
7 concatenate the root list containing x with root list H
8 if min[H] = NIL or key[x] < key[min[H]]
9 then min[H] x
10 n[H] n[H] + 1
1-4행에서는 노드 x의 구조적인 속성들의 일부를 초기화하며, 5행에서는 피보나치 힙 H가 비어 있는지를 검사한다. 만약 비었다면 6~7행에서 x를 H의 루트 리스트에서 유일한 노드로 만들고 min[H]가 x를 가리키도록 지정한다. 비어 있지 않으면 8~10행에서 x를 H의 루트 리스트에 삽입하고 필요하다면 min[H]을 변경한다. 마지막으로 11행에서 새로운 노드의 추가를 반영하기 위해 n[H]를 증가 시킨다.
피보나치 힙 최솟값 추출
최솟값 추출 연산 (Operation extract minimum)(최솟값 삭제와 동일) 세 단계로 수행된다. 첫번째, 우리는 최소 값을 가진 루트를 꺼내 제거한다. 이것의 자식들은 새로운 트리의 루트들이 된다. 만일 자식의 수가 d라면, 모든 새로운 루트를 처리하는데O(d)의 시간이 소요되며, 잠재비용은 d-1 만큼 증가한다. 그러므로 이 단계에서의 분할상환 실행시간은O(d) = O(log n)이다.
피보나치 힙 최솟값 추출
최솟값 추출 연산을 완료하기 위해서는, 마지막으로 최소 키를 가진 루트를 가리키는 포인터를 업데이트 해야 한다. 불행히도 우리가 체크해야 할 루트는 최대 n개가 될 수도 있다. 두번째 단계에서 그러므로 동일한 degree를 가진 루트들을 서로 연결하여 루트의 수를 감소시킨다. 두 루트인 u와 v 가 동일한 degree를 가진다면, 더 작은 키를 가진 것이 루트가 될 수 있도록 하여 둘 중 하나를 나머지 트리의 자식으로 만든다. 그러면 degree는 1 증가할 것이다. 이러한 작업은 모든 루트의 degree가 서로 다를 때까지 반복한다. 동일한 degree를 가지는 트리를 효율적으로 찾기 위하여, 우리는 길이가O(log n)인 어레이를 사용한다. 이 어레이 내에 각 degree 별로 루트를 가리키는 포인터를 저장한다. 두번째 루트가 동일한 degree인 것을 발견하면, 이 두 개의 트리를 연결하고, 어레이를 업데이트한다. 실제 실행시간은O(log n + m)이다. 여기서 m은 두번째 단계를 시작한 시점에서의 루트의 수이다. 마지막에 결국 우리는 최대O(log n) 만큼의 루트를 가지게 된다. (왜냐하면 각각은 서로 다른 degree를 가질 것이기 때문임) 그러므로, 이 단계의 전과 후 잠재비용 함수의 차이는: O(log n) − m, 또한 분할상환된 실행 시간은 최대O(log n + m) + c(O(log n) − m)이다. 충분히 큰 c값을 선택하면, 이것은O(log n)으로 단순화된다.
세번째 단계에서 우리는 남은 루트 각각을 체크하여 최솟값을 찾는다. 이것에O(log n)만큼의 시간이 소요되며, 잠재비용은 변함없다. 최소 추출 연산의 전체적인 분할상환 실행시간은 그러므로 O(log n)이다.
글만으로 이해하기 어려울 것 같아 아래의 그림으로 상세하게 설명하면 아래와 같다.
피보나치 힙 키 감소
키 감소 연산 (Operation decrease key)은 노드를 취하여 키를 감소시킨다. 이로 인해 힙의 특성이 위반되었다면 (새로운 키가 부모의 키보다 작다), 이 노드를 부모로부터 절단한다. 만일 부모가 루트가 아니면, 이 노드를 표시한다. 만일 이 노드가 이미 표시된 것이라면, 이것을 절단하고 부모를 표시한다. 이 과정을 반복하면서 위로 올라가는데, 루트 또는 표시되지 않은 노드를 만날 때까지 계속한다. 이것이 새로운 최솟값이라면, 이제 최솟값 포인터를 감소된 값으로 설정한다. 이 과정에서 우리는 신규 트리를 생성한다. (이때 이 신규 트리의 수를 k라 하자). 첫번째 트리를 제외한 신규 생성된 트리 각각은 원래 표시된 것이었겠으나, 루트로는 표시되지 않은 (unmarked) 것이 된다. 하나의 노드는 marked될 수 있다. 그러므로, 표시된 노드의 수는 −(k − 1) + 1 = − k + 2 만큼 변경된다. 두 변경을 결합하면, 잠재 비용은 2(−k + 2) + k = −k + 4만큼 변경된다. 절단을 수행하는데 소요되는 실제 시간은O(k)이었으므로, (다시 한번 충분히 큰 c값을 선택하면) 분할상환된 실행 시간은 상수이다.
피보나치 힙 키 감소
마지막으로, 삭제 연산(operation delete)은 삭제하고자 하는 구성요소의 키를 무한대로 마이너스하여 감소시킨다. 이렇게 하여 이 노드를 전체 힙에서 최솟값을 보유한 노드가 되게 한다. 이제 최솟값 추출 함수를 호출하여 이것을 찾아 제거한다. 이 연산의 분할상환된 실행시간은 O(log n)이다.
아래의 그림으로 더 자세하게 설명하겠다
피보나치 힙 Degree 경계의 증명
피보나치 힙의 분할상환된 성능은 임의의 트리 루트의 degree(자식 노드의 수), 즉O(log n)에 따라 달라지는데, 여기서n 은 힙의 크기이다.
여기서 우리는 힙 내에서 degree가 d인 임의의 노드 x를 루트로 하는 (하위)트리의 크기는 적어도Fd+2가 되어야만 한다. 여기서Fk 은 k번째 피보나치 수이다.
Degree 경계는 이것부터 시작하여 다음의 사실, 그러니까 d≥0 인 모든 정수에 대해  (유도를 통해 쉽게 증명됨)를 따른다. 여기서 φ=((1+√5))⁄2=1.618이다. (그리고서 우리는  을 가지며, 양 변에 기초가 φ 인 로그를 취하면 d≤〖log〗_φ n 을 얻는다).
임의의 노드 x가 힙 내 어느 곳에 존재한다고 하면 (x는 메인 트리 중 하나의 루트 노드일 필요는 없다). size(x)는 x (x 자신을 포함하여 x의 자손의 수)를 루트로 하는 트리의 크기로 정의하자. 우리는 높이 x (x로부터 자손 leaf까지 도달하는 가장 긴 단순 트리의 길이)에 대해size(x) ≥ Fd+2 임을 증명한다. 여기서 d는 x의 degree이다.
피보나치 힙 Degree 경계의 증명
기초 사례: 만일 x가 높이 0을 가진다면, d=0이고size(x) = 1 = F2.
귀납적 사례: x가 양의 높이를 가졌고, degree d>0라고 하자. y1, y2, ..., yd는 x의 자식이고, x의 자식으로 최근 생성된 순서대로 인덱스되었다. (즉 y1 은 가장 오래전 것, yd 은 가장 최근 것), c1, c2, ..., cd 은 각각의 degree라고 한다. 우리는2≤i≤d인 각 i에 대해ci ≥ i-2 라고 주장한다. yi이 x의 자식으로 생성되기 바로 전, y1,...,yi−1 은 이미 x의 자식이다. 그러니 x는 이 시점에 적어도 i-1 의 degree를 가졌다. 트리의 루트들이 degree가 동일할 때에만 트리들은 결합되므로, 이것이 x의 자식이 되는 시점에만 yi는 적어도 i-1의 degree를 가진다. 이 시점에서부터 현재까지, yi는 최대한 하나의 자식을 잃을 수 있다 (이것은 marking 과정에 의해 보장된다). 그래서 이것의 현재 degree인 ci 은 적어도i−2이다. 이로써 이 주장이 증명되었다.
모든yi 의 높이가 x의 높이보다 엄격하게 더 작으므로, 우리는 이 귀납적 가정을
을 구하기 위하여 이들에 적용할 수 있다. 노드x 와 y1는 각각 적어도 1을size(x)에 기여한다. 그래서 우리는 다음을 얻는다.
피보나치 힙 최악의 경우
피보나치 힙이 매우 효율적인 것처럼 보이기는 하지만, 다음과 같은 두 단점이 있다 (“Pairing Heap: A new form of Self Adjusting Heap”이라는 논문에서 언급한대로). “피보나치 힙은 코딩하기에는 복잡하다. 또한 이론적으로는 덜 효율적인 다른 형태의 힙들에 비해 실제적으로는 그렇게 효율적이지 않은데, 가장 단순한 버전 조차도, 다른 구조체가 노드 당 두개 또는 세개의 포인터를 요구하는데 비해, 노드 별로 네 개의 포인터를 유지하기 위한 저장공간과 조작이 필요하기 때문이다.” 이러한 다른 구조체는 이진 힙, 이항 힙, Pairing Heap, Brodal Heap, Rank Pairing Heap 등을 일컫는다.
피보나치 힙 최악의 경우
빈 자료구조에서부터 시작해서 몇 개의 연산을 순차적으로 수행하는데 걸리는 전체 실행시간은 위에서 계산하였던 경계값 내에서 그 범위가 정해지기는 하지만, 이 순차 수행하는 연산 중 일부 연산 (매우 적기는 하지만)은 완료하는데 매우 오랜 시간이 소요될 수 있다 (특히, 삭제연산 및 최솟값 삭제연산은 최악의 경우 실행하는데 선형 시간(linear time)이 소요된다). 이러한 이유로 피보나치 힙과 다른 분할상환된 자료 구조는 실시간 시스템에는 적합하지 않을 수 있다. 최악의 경우의 성능이, 피보나치가 가지는 분할상환 성능과 동일한 자료 구조를 새로 만드는 것이 가능하다. 그러한 구조 중 하나가 Brodal queue인데, 이것을 창안한 창안자의 말을 빌리자면 “상당히 복잡한” 그리고 “현실적으로는 응용가능하지 않을” 구조라고 하였다. 2012년에 만들어진 엄격한 피보나치 힙은 동일한 최악의 경우의 경계값을 가지는 보다 단순한 구조이다 (Brodal의 것에 비하면 그렇다) 이 보다 엄격한 피보나치 힙이 실제로 적용했을 때 효율적인지 여부는 알려지지 않았다. 실행에서 다소 유연한 Driscoll et al.의 힙은 merge를 제외한 나머지 연산에 대해 피보나치 힙보다 보다 나은 최악 경우의 성능을 보였다.
피보나치 힙 수행시간
다음의 시간 복잡도는 Binary Heap, Binomial Heap, Fibonacci Heap에 대해서만 나타난 것이다.
맥스 미틀먼
맥스웰 브레이든 "맥스" 미틀먼(영어: Maxwell Braden "Max" Mittelman, 1990년 9월 5일 ~ )은 미국의 성우이다. 일본 애니메이션 《잔잔한 내일로부터》의 주인공 히카리 역, 《원펀맨》의 주인공 사이타마 역, 프랑스 애니메이션 《미라큘러스: 레이디버그와 블랙캣》의 플랙 역이 그의 대표작이다.
크라운 하이츠 어페어
크라운 하이츠 어페어(Crown Heights Affair)는 미국의 알앤비 / 펑크 / 디스코 그룹으로, 70년대 초반 뉴욕 브룩클린에서 결성되었다.
크라운 하이츠 어페어 음악 활동
크라운 하이츠 어페어는 1970년대 초, 베이스 연주자이자 후에 밴드의 매니저가 되는 도니 린튼에 의해 뉴욕에서 결성되었다. 결성 당시 밴드의 이름은 더 뉴 데이 익스프레스 (The Nue Day Express)였으나, 이후 브룩클린 중심부에 위치한 지역인 크라운 하이츠 (Crown Heights)의 이름을 따 현재 밴드의 이름인 크라운 하이츠 어페어로 바꾸었다. 처음 그룹은 뉴 데이 익스프레스의 멤버였던 도니 린튼, 필립 토마스, 윌리엄 엔더슨, 레이 락, 제임스 버나드, 스탠 존슨, 데릴 깁스, 줄리우스 딜리가드로 구성되었으며 이후 아놀드 "뮤키" 윌슨이 도니 린튼의 자리를 대신한다.
크라운 하이츠 어페어는 RCA 레코드와 계약하고, 1974년 자신들의 첫 앨범인 "Crown Heights Affair" (밴드이름과 동명)을 발매하였다. 밴드는 앨범의 타이틀 곡인 "Super Rod"와 "Leave The Kids Alone"을 통해 뉴욕에서 자신들의 이름을 알리는 데 성공한다.
크라운 하이츠 어페어 음악 활동
데뷔 앨범의 발매 이후 밴드에서는 다수의 멤버교체가 이루어졌다. 색소폰의 데릴 깁스가 버트 리드로 교체되었고, 밴드의 보컬을 담당하던 줄리우스 딜리가드는 트롬본과 보컬을 맡게 된 레이몬드 리드로 교체되었다. 스탠 존슨과 제임스 베이너드 또한 각각 호위 영과 타이론 데몬스로 교체되었다.
밴드 멤버의 전면적인 교체 이후 크라운 하이츠 어페어는 소속사를 De-Lite 레코드로 옮겼으며, 1975년에 그들의 두 번째 앨범 "Dreaming A Dream"을 발매하였다. "Dreaming A Dream"은 프로듀서들 (작곡가인 Freida Nerangis, Britt Britton과 매니저인 Donny Linton, Thomas Nerangis)의 적극적인 지지 속에 탄생한 음반답게 앨범의 싱글인  "Dreaming A Dream", "Every Beat Of My Heart", "Foxy Lady" and "Dancin'"이 큰 인기를 얻었으며, 크라운 하이츠 어페어를 단숨에 당대 펑크 씬의 주류로 끌어 올렸다.
크라운 하이츠 어페어 음악 활동
이후, 1978년에 발매된 밴드의 4번째 앨범 "Dream World"의 수록곡인 "Galaxy Of Love", "I'm Gonna Love You Forever''가 영국의 팝차트안에 드는 성과를 거두며 밴드는 미국이 아닌 영국에서도 자신들의 이름을 크게 알리게 된다. 한편 이 무렵 밴드를 잠시 떠나있던 제임스 베이너드가 타이론 데몬즈를 대신해 다시 밴드에 합류했으며, 1979년에 발매된 5집 앨범인  "Dance Lady Dance"부터는 스킵 보어들리(Skip Boardley)가 단독으로 메인보컬을 담당하던 필립토마스와 함께 보컬을 맡게되었다.
1980년, 밴드는 새로운 프로듀서인 Bert DeCoteaux의 프로듀싱 능력과, 밴드 내 멤버들의 작곡능력이 점점 향상되어감에 따라 더욱 더 큰 인기를 얻게 되는데, 당시 그들이 발매한 싱글인 "You Gave Me Love"는 영국 차트 10위권에 드는 데 성공한다. 이는 밴드의 가장 높은 차트 성과였다.
크라운 하이츠 어페어 음악 활동
밴드의 7번째 앨범인 "Think Positive"의 수록곡  "Somebody Tell Me What To Do"는 미국에서 히트한 그들의 마지막 곡으로 평가받는다.  이후 밴드의 정규음반 발매는 1983년 8번째 앨범인 "Struck Gold"가 마지막이였으나, 크라운 하이츠 어페어는 80년대 초의 성공 이후 약 10년간 많은 싱글을 내며 활발히 활동하였다. 또한, 밴드 멤버인 버트 리드와 레이몬드 리드 형제, 그리고 윌리엄 앤더슨, 레이 락 등은 밴드활동 외에도 프로듀서나 보컬로서의 역량을 발휘하여 많은 펑크 밴드들의 작곡이나, 프로듀싱을 담당하였고, Empress (가수 Gail Smith와 크라운 하이츠 어페어가 결성한 그룹), Rocket (레이 락이 주도하여 레이 리드를 메인 보컬로 내세운 프로젝트 그룹)과 같은 그룹을 만들어 활동하기도 했다.
크라운 하이츠 어페어 근황
2004년 12월 12일, 그룹에서 색소폰을 연주했던 버트 리드가 폐암으로 사망했다
2007년, 필립 토마스가 알앤비 그룹 더 플라밍고스 (The Flamingos)에 합류했다.
2013년 5월 21일, 레이몬드 리드가 암으로 사망했다, 향년 60세.
2013년 6월 22일, 밴드는 영국 런던에서 공연하기 위해 재결합하였다.
분할 상환 분석
컴퓨터 과학에서, 분할 상환 분석 (amortized analysis)은 주어진 알고리즘의 시간 복잡도나 프로그램을 수행하는데 소요되는 시간 또는 메모리 같은 자원 사용량을 분석하기 위해서 사용하는 기법이다. 알고리즘을 분석할 때에 각각의 연산마다 최악의 경우를 따져본다는 것은 굉장히 힘든 일이기 때문에, 이를 쉽게 해결하기 위해 분할 상환 분석이라는 방법론이 나오게 되었다.
분할 상환 분석
어떠한 임의의 알고리즘에 대해서, 어떤 연산은 자원적 측면에서 상당한 비용을 소모할 수 있지만, 반면 다른 연산은 그렇게 고비용을 소모하지 않을 수 있다. 분할상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하는 기법이라 하겠다. 이것은 다른 종류의 입력, 입력의 길이, 이 알고리즘의 성능에 영향을 미치는 다른 요인들을 전부 고려한다. 
수행된 모든 연산에 대해 자료구조 연산만의 어떤 시퀀스를 수행하는데 필요한 시간의 평균을 구한다. 비록 그 시퀀스에서 하나의 연산비용이 비싸더라도, 그 일련의 연산에 대해 평균을 구하면 연산 하나의 평균 비용이 작다는 것을 분할 상환 분석을 이용해 보일 수 있다. 분할 상환 분석은 확률이 포함되지 않으므로 평균비용 분석과는 다르다. 분할 상환 분석은 최악의 경우에도 각 연산의 평균 수행성능을 보장한다.
분할 상환 분석 역사
분할 상환 분석은 총계분석(aggregate analysis)이라는 기법으로부터 유래되었다. 하지만 현재는 총계분석이 분할 상환 분석에 포함되어있다. 이 기법은 1985년 Robert Tarjan의 논문 “분할상환 계산 복잡도(Amortized Computational Complexity)”에서 처음으로 소개되었다. 이 논문에서는 기존에 흔히 사용되던 확률론적 방식보다 유용한 형태의 분석 방법론이 필요하다는 점을 시사하고 있다. 처음에 분할상환(Amortization) 방식은 이진 트리같은 자료구조를 분석할 때 매우 한정적으로 사용되었다. 그러나 지금은 다른 자료구조나 알고리즘을 분석할 때 분할 상환 분석을 매우 흔하게 사용하고 있다.
분할 상환 분석 방법
이 방법은 어떤 연산의 시리즈가 가능한지에 대한 지식을 필요로 한다. 연산들 사이에서도 사라지지 않고 계속 유지되는 상태를 가지는 자료 구조를 가지는 경우가 대부분이다. 기본적인 아이디어는 이것이다. Worst case 연산은, worst case(최악의 경우)가 긴 시간동안 다시는 일어나지 않도록 상태를 변경할 수 있다는 것이다. 그러므로 이는 비용을 “분할상환”하는 것이다.
분할상환 분석을 수행하는 방법은 일반적으로 세 가지가 있다. 총계 방식(aggregate method), 회계 방식(accounting method), 잠재비용 방식(potential method)이다. 이 세 가지 방식이 만들어내는 답은 모두 동일하다. 이들의 활용성 차이는 주로 상황에서 비롯되며, 개인적 선호의 차이다.
분할 상환 분석 방법
총계분석에서는 모든 n에 대해 n개 연산들의 어떤 시퀀스는 최악의 경우 전체적으로 T(n)의 시간 복잡도를 가짐을 보인다. 따라서 최악의 경우 연산당 평균 비용또는 분할상환비용은 일련의 n 연산 수행에 소요되는 전체 비용에 대해, 상위 경계값을 T(n)으로 결정하고, 분할상환 비용을 T(n) / n 이라고 계산한다. 이때 전체 일련의 연산에 여러종류의 연산이 있을지라도 이런 분할상환 비용은 모든 연산에 동일하게 적용됨을 주의해야한다.
총계 분석의 예로서 이진카운터 증가를 통해 들 수 있다. 0부터 수를 세어가는 k비트 이진 카운터의 증가시키기 문제를 살펴보면, 카운터로는 비트의 배열인 A[0..k-1]을 사용할 것이다. 이때 A.length = k다. 카운터에 저장되는 2진수 x는 최하위 비트가 A[0]에, A[k-1]에 위치하므로 x=(i=0에서 k-1까지)A[i]*2i이 된다. 초기값은 x=0이므로 i=0,1,…,k-1에 대해 A[i]=0이 된다. 1을 카운터의 값에 더하기 위해서 다음 절차를 사용한다.
분할 상환 분석 방법
또한 오른쪽 그림은 초기값인 0에서 시작해 16번 증가시켜 16으로 끝나게 하면 카운터에 어떤변화가 일어나는지를 보여준다. 2~4행의 while 루프에서 반복의 처음 부분에서 i위치에 매번 1이 더해진다. A[i]가 i라면 i를 더하는 것은 i위치의 1을 0으로 반전시키고 자리올림을 하나 발생시켜 루프의 다음 번 반복에서 i+1위치에 다시 i를 더하게 된다. A[i]=0인 경우는 while루프가 끝나고, i<k인 경우 6행은 위치 i에 0을 1로 반전시켜 1을 더한다. 그러므로 INCREMENT연산의 비용은 비트가 반전되는 횟수에 비례한다.
16번의 INCREMENT연산에 의해 0부터 16까지 변하는 8비트 이진 카운터. 다음값으로 넘어가는 과정에서 값이 반전되는 비트들은 회색으로 표시되었고, 비트를 반전시키는 수행 비용은 오른쪽에 표시되어 있다.
분할 상환 분석 방법
N개 INCREMENT 연산들의 시퀀스에 대해 INCREMENT가 불릴 때마다 모든 비트의 반전되지 않는다는 관찰에 근거해, 최악의 경우 O(n)의 비용을 가지도록 분석을 더 엄격하게 할 수 있다. 그림과 같이 A[0]은 INCREMENT가 불릴때마다 반전된다. 다음 자리인 A[1]은 두번에 한 번 꼴로 반전되며, 초기값은 0을 가지는 카운터에 대한 n번의 일련의 INCREMENT연산은 A[1]을 [n/2]번 반전되게 한다. 마찬가지로 비트 A[i]는 초기값0을 가지는 카운터에 대한 n개의 INCREMENT 연산 시퀀스에서 [n/2i]번 반전되게 한다. 이때 i>=k인 비트A[i]는 존재하지 않으므로 반전할 수 가 없다. 따라서 이 시퀀스에서 뒤집히는 총횟수는 2n이다. 그러므로 초기값 0을 가지는 카운터에 대한 n개의 INCREMENT 연산의 시퀀스에서 최악의 경우 수행시간은 O(n)이다. 이때 각각의 연산에 대한 평균비용, 즉 분할상환 비용은 O(n)/n=O(1)이다.
분할 상환 분석 방법
회계 방식(accounting method)은 각 연산에 대한 개별적인 비용 계산을, 이 연산의 즉각적인 수행시간과 미래 연산의 수행시간에 대한 이것의 영향력을 결합하여 계산한다. 보통쓰는 방식은, 수행시간이 짧은 많은 연산에 대해, 작은 증가분을 가지게 하여 “빚”으로 적립한다. 반면 긴-수행시간을 가지는 몇 개 안되는 연산에 대해 이것의 수행시간을 상당한 양 감한다.
분할 상환 분석 방법
총계분석과 마찬가지로 이진카운터 증가시키는 방법을 예로 회계방식을 설명할 수 있다. 0부터 시작하는 이진 카운터의 INCREMENT 연산을 분석해보면, 앞서 이미 살펴봤듯이 이연산의 수행시간은 반전비트의 개수에 비례한다. 이 비트의 개수는 이예에서 비용으로 쓰인다. 분할 상환 분석을 위해 비트 하나를 1로 만드는데 2달러의 분할 상환 비용을 부과한다고 하자. 비트 하나가 1이 될 때 1달러를 해당비트를 1로 만들기 위한 비용으로 지불하고, 나머지 1달러는 나중에 해당 비트를 0으로 반전 시킬 때 쓰기 위해 그 비트위에 둔다. 이렇게 하면 어떤 순간에도 카운터의 모든 1은 그 자신위에 1달러의 크레딧을 가지고 있게 되고, 그비트를 다시 0으로 만들때는 아무것도 부과할 필요가 없게 된다. 즉, 다시 0으로 만들때는 그 비트위에 있는 1달러로 비용을 지불하면된다. 이저 INCREMENT의 분할상환 비용을 결정할 수 있다. while루프에서 비트를 다시 0으로 만드는 비용은 그 비트위에 놓인 1달러로 지불할 수 있다. INCREMENT 프로시저는 6행에서 최대 하나의 비트를 1로 바꾸므로 INCREMENT연산의 분할상환 비용은 최대 2달러다. 카운터에서 1인 비트의 개수는 결코 음수가 될 수 없으므로, 크레딧의 총합은 항상 0보다 크거나 같다. 그러므로 n개의 INCREMENT연산에 대한 분할 상환비용의 총합은 O(n)이고 이는 실제 비용 총합의 상환이 된다.
분할 상환 분석 방법
잠재비용 방법(potential method)은 회계방식과 유사하다. 그러나 연산에 과비용을 초기에 부과하고 나중에 이보다 낮은 값으로 청구하여 이를 보상한다. 미리 지불한 작업을 자료구조에서 특정 객체들과 함께 저장되는 선불 크레딧의 형태로 표현하는 대신, 분할상환 분석의 잠재비용방법은 미리 지불한 작업을 향후의 연산들의 비용을 지불하기 위해 사용될 수 있는 “잠재적 에너지”또는 단순히 “잠재비용”의 형태로 표현한다. 자료 구조의 특정 객체 보다는 자료구조 전체에 대한 잠재 비용을 부여한다. 잠재 비용 방법은 다음과 같이 동작된다. 먼저 초기의 자료구조 D0에서 시작하여 n개의 연산을 수행한다. i=1,2,…,n에 대해 ci는 i번째 연산의 실제 비용을, Di는 자료구조 Di-1에 i번째 연산을 적용한 결과로 만들어진 자료구조를 나타낸다. 잠재적 비용함수 Ф는 각 자료구조 Di를 실수 Ф(Di)에 대응시키는데, 그 숫자는 자료구조 Di와 연관된 잠재비용(potential)이다. 잠재비용 함수 Ф에 대한 i번째 연산의 분할상환비용은 각연산들의 분할 상환 비용은 실제 비용에 그연산으로 인한 잠재 비용의 변화를 더한 값이다.
잠재 비용 방법의 예로서 앞서 설명한 이진카운터 증가에 대해서 얘기할 수 있다. 이번에는 i번째 INCREMENT 연산을 수행한 후의 카운터 잠재비용은 bi이고 이값은 i번째 연산 이후의 카운터에서 1의 개수로 정의한다. ICREMENT연산이 ti개의 비트를 0으로 재설정했다고 가정하면, 재 설정된 ti개의 비트들 외에 최대 한 개의 비트가 1로 더 설정될 수 있으므로 이 연산의 실제 비용은 최대 ti+1이 된다. bi=0이라면 i번째 연산은 모든 k개의 비트를 재설정하므로 bi-1=ti=k가 된다. bi>0이면, bi=bi-1-ti+1이다. 어느 경우라도 bi<=bi-1-ti+1이고 잠재 비용의 차이는 1-t가 되며, 분할 상환비용은 2가 된다. 카운터가 0에서 시작했다면 Ф(D0)=0이 된다. 모든 i에 대해 Ф(Di)>=0이므로 연속된 n개의 INCREMENT 연산의 총 분할상환 비용은 실제 총비용의 상한이고 n개의 INCREMENT연산의 최악의 경우의 비용은 O(n)이다.
분할 상환 분석 동적 배열
Java에서 ArrayList나 C++ std의 vector와 같은 동적 배열이 있다고 하자. 이 배열에는 더 많은 요소가 삽입되면 용량이 그만큼 동적으로 늘어나야 한다. 우선 용량이 4인 동적 배열에서부터 시작한다고 하면, 이 배열에 4개의 요소를 배열 끝에 삽입(pushback)하는 연산은 상수 시간이 소요될 것이다. 그러나 다섯 번째 요소는 자리가 없어 보다 큰 용량을 새롭게 확보한 다음 기존 요소를 옮겨야 하기 때문에 비교적 많은 시간이 소요된다. 용량이 부족할 때 두 배로 용량을 늘린다고 가정하자. 최초 용량이 4이므로 용량이 8인 공간을 확보한 다음 기존 배열에 저장되었던 요소들을 새 배열에 옮기는 작업이 필요하다. 하지만 그 다음부터는 상수 시간이 소요된다. 즉, 상수 비용이 소요되다가 저장된 요소의 개수가 2의 거듭제곱이 되면 O(n)의 비용이 소요된다. 이것을 수학적으로 분석하여 n개의 요소를 동적 배열에 삽입하는 비용을 분할 상환 분석을 하게 되면 전체 비용은 상수 비용이 된다. 즉, 고비용 연산이 가끔 발생하지만 전체적으로는 비용이 높지 않다는 것을 알 수 있다.
분할 상환 분석 동적 배열
Enqueue 연산(큐에 데이터를 삽입하는 연산)은 입력 어레이에 구성요소를 push하는 연산이다. 이 연산은 입력 또는 출력의 길이에 종속되지 않는다. 그러므로 수행시간은 상수이다.
그러나, dequeue 연산(큐에서 데이터를 빼내는 연산)은 보다 복잡하다. 만일 출력 어레이가 이미 그 안에 몇 개의 구성요소를 보유하고 있다면, dequeue 연산의 수행은 상수시간이다. 그렇지 않다면 dequeue연산은 O(n) 이 소요되는데 입력 어레이에서 출력 어레이로 모든 구성요소를 더해야 하기 때문이다. 여기서 n 은 입력 어레이의 현재 길이이다. 입력 어레이에서n 개의 구성요소를 카피한 후, n번의 dequeue연산을 수행할 수 있다. 이때 각각의 dequeue연산은 상수시간이 소요된다. 이 작업은 출력 어레이가 다시 빈 상태가 되기 전까지 수행가능하다. 그러므로, n번의 dequeue연산을 수행하는데 O(n)의 시간만이 소요되며, 이것은 각 dequeue연산의 분할상환 시간이 O(1)임을 의미한다.
분할 상환 분석 동적 배열
또 다른 방식으로, 우리는 해당 아이템에 대한 앞서의 enqueue 연산을 수행하기 위해 입력 어레이에서 출력 어레이로 아이템을 카피하는데 드는 비용을 부과할 수 있다. 이 부과 방식은 enqueue에 대한 분할상환 시간은 두배로 만들지만, dequeue에 대한 분할상환시간은 O(1)으로 한다.
멜라 리
멜라 리(영어: Mela Lee, 1976년 7월 31일 ~ )은 미국의 성우이다. 일본 애니메이션 《페이트/스테이 나이트》의 토오사카 린 역, 《로젠 메이든》의 신쿠 역으로 유명하다.
TODAY IS ANOTHER DAY
《TODAY IS ANOTHER DAY》(투데이 이즈 어나더 데이)는 일본의 밴드 ZARD의 일곱 번째 정규 앨범으로, 1996년 7월 8일 발매되었다. (CD: JBCJ-1009) 사카이 이즈미가 프로듀서로 이름을 올린 최초의 앨범이며, FIELD OF VIEW의 〈그대가 있어서〉, 〈DAN DAN 마음이 이끌려〉, 〈돌연〉 세 곡이 리메이크 되어 실려있는 것이 특징이다.
12번 트랙에 실려있는 오리지널 곡 〈바라보고 있고 싶어요〉는 팬에게 바치는 헌정곡이다. 미야기 현 소재 고등학교의 선생님이 자신이 담임을 맡던 학생이 사고사 당했는데, 그 학생이 굉장히 좋아했다며 편지를 보내온 적이 있다. 1996년 7월의 인터뷰에서, 사카이는 이 곡의 편곡을 듣던 중 생사를 헤메이는 세계가 떠올랐고 2년전에 받았던 이 편지가 생각났다고 한다. 학교에서 그의 별명은 "3학년 G반의 골키퍼"였는데, 이는 "3G의 키퍼도 천국에서 보고있네"라고 가사에 반영되며, 앨범에 수록된 가사집의 말미에는 "Dedicate to KIYOTAKA SATOH"라고 적혀있다.
TODAY IS ANOTHER DAY 크레딧
아래는 《TODAY IS ANOTHER DAY》 음반에 적혀있는 내용을 발췌한 것이다:
재니스 가와에
재니스 히로미 가와에(Janice Hiromi Kawaye, 1970년 4월 28일 ~ )는 미국의 성우이다. 가와에 히로미(河江 弘美)라는 일본어 이름을 가진 일본계 미국인으로, 작품에서도 일본어가 유창한 인물을 연기하곤 한다. 애니메이션 《퍼피아미유미 쇼》에서 아미 역, 《영 저스티스》에서 샘 역을 맡았으며, 게임 닌자 가이덴 시리즈의 아야네 역으로도 알려져 있다.
네메트 크리스티안
네메트 크리스티안(헝가리어: Németh Krisztián, 1989년 1월 5일 ~ )은 넴제티 버이녹샤그 I 소속 팀인 데브레첸에서 스트라이커로 활약하고 있는 헝가리의 축구 선수이다.
2015년 FIBA 아시아 남자 농구 선수권 대회
2015년 FIBA 아시아 남자 농구 선수권 대회(영어: 2015 FIBA Asia Championship)는 2015년 9월 23일부터 10월 3일까지 중화인민공화국 후난성 장사시에서 열렸다.
K리그 주니어 2016
K리그 주니어 2016은 K리그 주니어의 아홉 번째 시즌이다. 아디다스가 후원하여 2016 아디다스 K리그 주니어가 정식 명칭이다. 전기리그 결과 A조에서는 성남 FC U-18과 FC 서울 U-18이, B조에서는 울산 현대 U-18과 포항 스틸러스 U-18이 각각 우승과 준우승을 차지하였다.
1981년 여자 하키 월드컵
1981 여자 하키 월드컵은 아르헨티나 부에노스 아이레스에서 열린 4번째 여자 하키 월드컵이다.
제다 조약
제다 조약(Treaty of Jeddah)은 1927년 5월 20일, 영국과 이븐 사우드가 체결한 조약이다. 이 조약에서, 영국은 이븐 사우드가 지배하는 네지드-헤자즈 왕국의 독립을 인정했다.
향후 5년동안 이븐 사우드는 자신의 네지드 왕국과 헤자즈 왕국을 별도로 관리했다. 1932년 9월 23일 알-하사, 카티프, 네지드, 헤자즈는 사우디아라비아 왕국으로 통합되었다.
1927년 제다 조약으로 1915년 영국과 이븐 사우드가 체결한 다린 조약을 대체했다.
디부스 데네시
디부스 데네시(헝가리어: Dibusz Dénes, 1990년 11월 16일 ~ )는 페렌츠바로시와 헝가리 축구 국가대표팀에서 뛰고 있는 헝가리의 축구 선수이다.
디부스 데네시 클럽 경력
2015년 5월 20일, 디부스는 비데오톤과의 4-0으로 이긴 경기에서 페렌츠바로시 소속으로 데뷔했다.
Sha la la☆Summer Time
〈Sha la la☆Summer Time〉은 Kis-My-Ft2의 17번째 싱글이다.
Sha la la☆Summer Time 개요
초회 생산 한정반 A, 초회 생산 한정반 B, 통상 반의 3 형태로 발매되었다.
이번 싱글에 처음으로 커플링에 유닛곡이 들어가 있다.
첫회 생산 한정반 A, 초회 한정반 B, 통상 반 (첫회 프레스 분)에 일련 번호가 봉입되어 있으며, 일련 번호를 특설 사이트에 입력하면 레코딩 영상과 멤버들의 코멘트를 시청할 수 있다. (8월 23일 정오부터 10월 31일 정오까지 시청 가능)
표제곡 〈Sha la la☆Summer Time〉는 「우나 코와」 CM송 , DREAM STAGE는「모시모 투어즈」 테마곡이다.
2016년 오스트레일리아 의회 선거
2016년 오스트레일리아 총선 (2016 Australia Federal General Election)은 2016년 7월 2일에 치러진 오스트레일리아의 총선이다. 이번 선거에서 선출되는 연방의회 국회의원 수는 상하원을 합쳐 총 226명이다. 투표에 앞서 8주간 공식 선거운동 기간이 진행됐고 투표는 7월 2일 아침 8시부터 오후 6시까지 진행됐다. 이번 총선은 양원 해산을 통해 치러지는 선거로 1987년 총선 이래 처음이다.
오스트레일리아의 선거 제도는 소선거구제와 과반수득표제, 우선순위투표제를 절충한 형태이다. 투표 시 유권자가 후보별로 선호 순위를 직접 적어 넣으며, 여기서 후보 1명이 과반수 득표를 하면 바로 당선된다. 1위 후보가 과반에 미달할 경우, 우선순위투표제를 적용해 최저 득표자부터 탈락자들이 받은 표를 차례로 산정하며 당선자가 뒤바뀔 수 있다.
2016년 오스트레일리아 의회 선거 이슈
선거 당일 스카이 TV가 투표에 가장 큰 영향을 끼친 이슈를 묻는 설문조사를 실시했다. 조사에 따르면 응답자의 72%가 보건 및 의료 보험 문제를 꼽았고, 교육이 63%로 뒤를 이었다. 두 이슈 모두 노동당의 주요 공약과 관련이 있었다. 반면 여당인 연합이 역점을 둔 예산과 경제문제는 3위에 그쳤다. 여당의 맬컴 턴불 총리는 경제성장과 정부지출 축소, 강경한 난민정책 등을 강조했으나 유권자의 주요 관심사는 파악하지 못했다는 의견이 제기됐다.
한편 선거운동 막바지에 당락이 결정됐던 브렉시트(영국의 유럽 연합 탈퇴) 관련 2016년 영국 유럽 연합 회원국 국민투표 결과는 선거에 큰 영향을 미치지 못한 것으로 보였다.
2016년 오스트레일리아 의회 선거 출구 조사
나인 네트워크 방송과 갤럭시 리서치가 25개 적중 지역구 대상으로 공동 실시한 출구조사에서 양당 선호도가 50% 대 50%를 기록했다. 이로 인해 나인 네트워크에서는 과반 정당이 없는 헝 의회로 결과가 날 수도 있다고 예측했고, 유력지인 <시드니 모닝 헤럴드>도 "어느 당을 승자로 꼽기 어려운 접전 상황"이라며 역시 헝 의회 가능성을 제기했다.
타 방송의 출구조사도 마찬가지였는데, 세븐 네트워크 방송과 리치텔(ReachTEL) 공동 출구조사의 양당 선호도 조사에서도 연합과 노동당이 51%대 49%로 상당한 근소를 보인 것으로 나타났다.
다만 어느 당이 승리할 것인지를 물은 스카이 TV 출구조사에서는 응답자의 62%가 여당인 자유당/국민당 연합을 택했고, 노동당은 19%에 그쳤다. 모르겠다는 응답자는 19%였다.
2016년 오스트레일리아 의회 선거 결과
취소선은 이번 선거에 출마하지 않고 사퇴한 의원들이다.
주
1  2015년 선거구 개편으로 뉴사우스웨일스 주내에서 자유당이 차지하고 있던 바튼 구와 도벨 구, 패터슨 구는 관념적으론 근소한 차의 득표로 노동당에게 넘어갔다.
2  7월 19일 퀸즐랜드 주 허버트 구에서 재검표가 이뤄졌다. 재검 전에는 노동당이 자유국민당을 불과 8표차로 따돌린 것으로 집계됐다. 7월 31일 오스트레일리아 선거위원회는 노동당이 37표차로 허버트 선거구에서 승리했다고 확정했다. 이에 대해 자유국민당은 법적 조치를 고려하고 있다고 밝히기도 했다.
마지막 상원 투표 결과는 8월 4일에 발표되었다. 현 여당인 자유당/국민당 연합이 30석을 얻어 3석이 줄었다. 보수연합은 뉴사우스웨일스, 퀸즐랜드, 사우스오스트레일리아, 웨스턴오스트레일리아에서 각각 네 석을 잃었으나 빅토리아에서 한 석을 얻었다. 야당인 노동당은 26석을 차지했는데 웨스턴오스트레일리아에서 1석이 늘었다. 중립 정당은 획득 의석이 2석에서 20석으로 증가했다. 자유당/국민당 연합이 상원내 과반을 차지하기 위해선 추가로 아홉 석이 더 필요하게 되었는데 이전보다 세 석이 늘어난 결과였다.
국가판무관
국가판무관(國家辦務官, 독일어: Reichskommissar 라이히스코미사르[*])은 독일 근대사에서 여러 다양한 지방관 관직들을 가리키는 직함으로 사용된 호칭이다.
국가판무관 독일 제국
1871년 독일 제국이 통일된 뒤 국가판무관은 특수임무를 감독하는 관직으로서 존재했다. 예컨대 함부르크에는 이민국가판무관(Reichskommissar für das Auswanderungswesen)이 설치되었다.
또한 독일 제국의 보호령(이라고 하지만 사실상 식민지)들 대부분을 다스린 일종의 총독직도 국가판무관이라고 했다.
카메룬 국가판무관
1884년 7월 14일 – 1884년 7월 19일 구스타프 나흐티갈 (1834년 생 – 1885년 몰)
1884년 7월 19일 – 1885년 4월 1일 막시밀리안 무흐너(권한대행) (1846년 생 – 1921년 몰)
1885년 4월 1일  – 1885년 7월 4일 에두아르트 폰 크노르 (1840년 생 – 1920년 몰)
국가판무관 독일 제국
토골란드 국가판무관
1884년 7월 5일 – 1884년 7월 6일 구스타프 나흐티갈, 서아프리카 국가판무관 직함
1884년 7월 6일 – 1885년 6월 26일 하인리히 란다트, 임시집정관 직함
1885년 6월 26일 – 1887년 5월  에른스트 팔켄탈 (1858년 생 – 1911년 몰)
1887년 7월  – 1888년 10월 17일 예슈코 폰 푸트카머(권한대행) (1855년 생 – 1917년 몰)
1888년 10월 17일 – 1891년 4월 14일 오이겐 폰 치머러 (1843년 생 – 1918년 몰)
1891년 4월 14일 – 1892년 6월 4일 공석
1892년 6월 4일 – 1893년 11월 예슈코 폰 푸트카머
국가판무관 전간기
프란츠 폰 파펜이 프로이센 쿠데타를 일으켰을 당시 프로이센 총리직을 일시 폐지하고 국가판무관직을 설치, 자신이 취임했다.
국가판무관 나치 독일
아돌프 히틀러는 제2차 세계 대전 당시 점령한 국가들에 국가판무관 직함의 지방관을 파견하고 그 기관을 국가판무관부라 했다.
동방 국가판무관
1941년 7월 17일 – 1944년 9월 26일 – 힌리히 로흐제 (1896년 생 – 1964년 몰), 나치 당료
1944년 9월 26일 – 1945년 2월 2일 – 에리히 코흐 (1896년 생 – 1986년 몰), 나치 당료. 소련 붉은 군대가 1944년 10월 13일 리가를 점령하면서 사실상 쫓겨났지만 동방 국가판무관부는 1945년 2월 2일까지 공식적으로 해체되지 않았다.
우크라이나 국가판무관
1941년 8월 20일 – 1943년 10월 6일 – 에리히 코흐 (1896년 생 – 1986년 몰), 나치 당료
1942년 – 1943년 9월 30일 – 파울 다르겔(권한대행) (1903년 생 – 19??년 몰), 나치 당료
1943년 10월 – 1944년 – 쿠르트 폰 고트베르크 (1896년 생 – 1945년 몰), 나치 당료
도러시 일라이어스판
도러시 앤 일라이어스판(영어: Dorothy Ann Elias-Fahn, 1962년 3월 13일 ~ )은 미국의 성우이다. 활동 초기에는 도러시 멜런드레즈(Dorothy Melendrez)라는 예명으로 활동하였으며, 2010년대 이후로는 조해나 루이스(Johanna Luis)로도 활동중이다. 일본 애니메이션 《바람의 검심》의 카미야 카오루 역, 《러브히나》의 나루 역, 《사쿠라 대전》의 이홍란 역, 《로젠 메이든》의 도모에 역, 《카노콘》의 치즈루 역이 대표작이다. 같은 성우인 톰 판과 결혼하였다.
뵈데 다니엘
뵈데 다니엘(헝가리어: Böde Dániel, 1986년 10월 24일 ~ )은 퍽시에서 스트라이커로 활약하고 있는 헝가리의 축구 선수이다.
2016년 내셔널축구선수권대회
내셔널 축구선수권대회 2016은 내셔널 축구선수권대회의 열 두 번째 시즌이다. 이 대회는 한화생명과 타이틀 스폰서쉽을 맺어 대회명칭은 한화생명 2016 NATIONAL 축구선수권대회라는 이름으로 강원도 양구에서 개최되었다.
6월 1일 개막하여, 6월 14일 결승전을 끝으로 막을 내렸으며 울산 현대미포가 통산 세 번째 우승을 차지하였다.
로브렌치치 게르괴
로브렌치치 게르괴(헝가리어: Lovrencsics Gergő, 1988년 9월 1일 ~ )는 헝가리의 전 축구 선수이다.
로브렌치치 게르괴 경력 통계
2016년 5월 21일 기준
1 폴란드 슈퍼 컵 포함
동정군
동정군(洞庭郡)은 지금의 후난성 지역에 있었을 것으로 추정되는 중국의 옛 군이다. 기존 전래 문헌에는 전혀 나타나지 않았으나 2002년 발견된 이야진간(里耶秦簡)에 처음으로 존재가 확인되었으며, 이를 통해 기존 후난성 지역에 있는 것으로 알려진 진나라의 검중군·장사군·창오군, 한나라의 장사군·무릉군 등에 대한 새로운 논의가 시작되는 계기를 만들었다.
동정군 위치
기존에는 진나라에서 초나라의 무군(巫郡)·검중군(黔中郡)을 정복해 새로 검중군을 세우고, 검중군에서 장사군을 분할한 것으로 여겼다. 그러나 이야진간에서는 둥팅호 주변에 동정군·창오군·남군의 이름은 보이나 검중군·장사군의 이름이 나타나지 않는다. 한편 이야진간 중 동정군과 관련된 기록을 살펴보면 천릉(遷陵)·유양(酉陽)·익양(益陽)·영양(零陽)·잔릉(孱陵)·삭(索)·임원(臨沅) 등의 지명이 나타나는데, 이를 이어보면 대략 상수(湘水)·원수(沅水)·풍수(灃水) 유역과 충칭 시의 일부에 이른다. 이를 바탕으로 진나라의 장사군은 사실 동정군의 오기이며, 이후 동정군을 분할해 장사군과 무릉군을 설치한 것과 혼동한 것으로 보는 견해가 있다.
동정군 위치
한편, 위의 논의에서 장사군을 동정군의 영역에 포함시키는 주 원인은 장사군 익양현인데, 이에 대한 이견이 있다. 익양은 동정군이 아니라 동정군 외부의 현으로서 동정군과 상호작용을 하기 때문에 기록된 것이라는 견해로, 한대의 장사군 지역은 동정군의 영역이 아니었다는 것이다. 이는 후난 성을 지나는 장강의 큰 네 지류인 상수·원수·풍수·자수(澬水) 중 원수·풍수와 상수·자수 유역은 설봉산(雪峰山)이 자연 경계로 갈라지기에 상호간의 교류가 미약하다는 점에도 기인한다. 이에 따라 원수·풍수 유역만이 동정군의 영역이었을 것으로 보는 논의가 있으며, 한나라의 행정구역으로 보면 대략 무릉군의 영역과 비슷해진다. 비슷한 논의를 거쳐서 익양현에 더해 한대의 무릉군에 속하는 한산(佷山)현과 잔릉(孱陵)현을 동정군이 아닌 남군의 관할로 빼기도 한다. 이 경우 장사군은 동정군과는 무관하게 창오군의 옛 이름으로 보기도 하고, 동정군·창오군과 공존했다고 보기도 한다.
동정군 군수
다음 군수 목록은 이야진간에서 나타나는 군수들의 이름을 정리한 것이다.
동정군 치소
치소에 대해서는 임상(臨湘), 임원(臨沅), 원릉(沅陵), 장사(長沙), 삭(索), 신무릉(新武陵)→임원(臨沅)→원양(沅陽) 등의 설이 있다.
대럴 길보
대럴 길보(영어: Darrel Guilbeau, 1962년 3월 31일 ~ )는 미국의 성우이다. 일본 애니메이션 《누라리횬의 손자》에서 주인공 누라 리쿠오 역을 맡았다.
빅 미뇨나
빅터 조지프 "빅" 미뇨나(영어: Victor Joseph "Vic" Mignogna)는 미국의 성우, 배우, 가수이다. 일본 애니메이션 《강철의 연금술사》의 주인공 에드워드 엘릭 역으로 가장 유명하며, 이외에 《드래곤볼 Z》의 브로리 역, 《오란고교 호스트부》의 타마키 역, 《블리치》의 마다라메 잇카쿠 역이 알려져 있다. 비디오 게임에서는 소닉 시리즈의 오메가, 페르소나 시리즈의 이오리 준페이의 담당 성우이다.
존 수셰이
존 수셰이(John Suchet, /ˈsuːʃeɪ/; 1944년 3월 29일 ~ )는 영국의 언론인으로, ITN의 앵커이다. 배우 데이비드 수셰이의 형이다.
김돈시
김돈시(金敦時, 1120년 ~ 1170년 음력 9월)는 고려 중기의 문신이다.
김돈시 생애
김부식의 아들이다. 의종 때 시랑(侍郞)이 되었으며 그 뒤 상서우승(尙書右丞)에 올랐다. 하지만 무신정변이 일어나자 형인 김돈중과 함께 김악산으로 숨어있었으나 형의 종자가 밀고하자 함께 처형되었다.
대구급 호위함
대구급 호위함은 대한민국 해군이 운용하는 호위함으로, FFX 사업의 일환으로 건조되었다.
대구급 호위함 개발
2010년 3월 26일, 천안함 격침 사건으로 유명한 배수량 1,200톤급 포항급 초계함 천안함의 후속 버전인 배수량 2,800톤급 호위함 사업으로서, 쉽게 말하면 차기 천안함 사업이다.
2016년 6월 2일 대구급 호위함 1번함인 대구함이 진수식을 가졌다. 대구급 호위함은 FFX Batch-I 사업으로 전력화 된 인천급 호위함(FFG-I)에 비해 길이는 8m, 배수량은 600톤이 늘어났고, 16개의 발사관으로 구성된 한국형수직발사체계(KVLS)를 탑재하는 등 인천급 호위함에서 지적된 각종 문제점들을 개선했다.
또한 한국 해군 전투함 최초로 추진전동기(전기모터)와 가스터빈 엔진을 결합한 하이브리드 추진체계를 적용해 수중소음을 많이 줄이게 됐다. 2,800톤 대구급이 배치되면서 천안함의 1,200톤급 초계함들이 모두 퇴역할 것이다.