hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
니켈 동위 원소
62Ni는 니켈 동위 원소 중 3.634%를 차지하며 항성의 핵융합으로 인해 생성되기도 하며 초신성 폭발을 통해서도 생성한다.
왜냐하면 62Ni는 모든 원소들 중 핵자간 결합 에너지가 가장 높으므로 가장 안정적 동위 원소이기 때문이다.
( 62Ni의 결합 에너지는 8.794549 MeV, 58Fe의 결합에너지는 8.792221 MeV, 56Fe의 결합에너지는 8.790323 MeV )
따라서 62Ni가 항성의 핵융합으로 인해 생성되는 최종 동위 원소이다. 그럼에도 불구하고 62Ni는 철보다 희귀하며 니켈 동위 원소들 중에서도 희귀하다.
이유는 30P의 헬륨 과정은 54Co를 형성할 때에 항성의 중심핵은 응축하기 시작한다. 그 다음 산물인 58Cu는 에너지를 방출하므로 순탄하게 일어나지만 이미 항성의 중심핵이 응축하기 시작하여 시간이 많지 않으므로 58Ni은 많은 양이 형성되지 않는다.
그 다음 산물인 62Ga은 58Cu보다 결합 에너지가 낮기 때문에 에너지를 흡수해야 생성되며, 58Cu에 비해 형성될 시간적 여유가 더욱 더 없으므로 미량 생성된다. 형성된 62Ga은 어마어마한 에너지를 내뿜는데 3번의 B+ 붕괴를 통해 총 14.75 MeV의 엄청난 에너지를 내뿜고 62Ni로 붕괴한다.
따라서 62Ni는 항성의 핵융합을 통해서도 생성되지만 상당비율이 초신성 폭발을 통해서 생성된다.
61Ni과 64Ni는 초신성 폭발의 R-과정을 통해 생성된다.
니켈 주요 성질
니켈은 은백색의 강한 광택이 있는 금속이다. 철족 원소로 단단하며 가단성과 연성이 있다. 황 화합물인 침상니켈석이나 비소 화합물인 홍비니켈석, 황/비소 화합물인 황비니켈석 광물에서 산출된다.
공기 중에서 변하지 않고, 산화 반응을 일으키지 않아 도금이나 합금 등을 통해 동전의 재료로 사용된다. 자성을 띠며 코발트와 함께 산출된다.
니켈은 강자성을 띠는 다섯 원소 중 하나이다.
일반적인 산화 상태는 +2로, 0, +1, +3 상태도 관찰된다.
니켈-62은 존재하는 원소 중 가장 안정성이 뛰어난 핵종으로, 그 다음은 철-58이다.
니켈 지구에서의 존재
니켈은 지구의 외핵과 내핵의 성분 중 하나이다. 지각에는 84ppm이 존재하지만 지구 자체에는 1.83%가 존재하는데 지구 내핵의 5.8%가 니켈로 이루어져 있다.
후지시마 고스케
후지시마 코우스케(일본어: 藤島康介/ふじしま こうすけ, 1964년 7월 7일 - )는 일본의 만화가이고 도쿄도에서 태어났지만 지바현 출신이다.
1986년에 코믹 모닝게재의 "Making BE FREE!"로 데뷔했다.
대표작은 "오! 나의 여신님", "체포하겠어!"이다. 모두 애니메이션화나 영화화되었다.
라페루즈 해협
라페루즈 해협(러시아어: пролив Лаперуза) 또는 소야 해협(宗谷海峡 (そうやかいきょう))은 홋카이도의 소야 곶과 러시아 사할린섬 사이에 있는 해협이다. 이름의 유래는 1787년 8월 15일에 이 해협을 지나간, 배로 세계일주를 시도한 프랑스인 탐험가 라페루즈 백작이다.
가장 깊은 곳의 수심은 60~70m로, 비교적 얕은 해협이다. 동물 분포의 경계선의 하나인 동물지리학상의 분포경계선이 통과한다고 여겨진다.
한학수
한학수(韓鶴洙, 1969년 12월 7일~)는 문화방송의 PD이다.
한학수 생애 및 경력
1987년에 서울대학교 경영학과에 입학하여 1993년에 졸업, 1997년에 동 대학 경영대학원에서 마케팅학 석사학위를 받았다. 1997년 MBC에 시사교양 프로듀서로 입사하여 《생방송 모닝스페셜》, 《생방송 화제집중》등 생활정보 프로그램들을 연출하다가, 2001년 《PD수첩》을 연출하면서 시사문제에 대해 다루기 시작했다. 특히 《PD수첩》의'SOFA, 미군 범죄의 면죄부인가', '그들만의 재판, 미군은 무죄인가?'를 연출하면서 이로 인해, 묻힐뻔한 미선이 효순이 사건이 큰 관심사가 되어 촛불시위의 도화선이 되었다.
그밖에, '사형제도를 사형시켜라', '양심적 병역 거부', '군 사법제도를 기소하라', '음지의 절대권력, 국가정보원', '불패신화, 삼성무노조' 등을 연출하였고, 2004년에는 《이제는 말할 수 있다》에서 '신의 아들과의 전쟁', '한국의 진보' 3부작 등을 연출하였다.
한학수 생애 및 경력
2005년 다시 《PD수첩》으로 자리를 옮겨 황우석 사건을 파헤치게 된다. 비록 취재 과정에서 사소하나마 취재윤리 위반 논란이 있었으나 결국 황우석 교수의 줄기세포 조작사실을 밝혀내고 이를 보도하여 큰 파장을 일으켰고, 이듬해인 2006년 이 보도로 당시 《PD수첩》 책임 프로듀서였던 최승호 PD와 한국PD연합회에서 수여하는 '올해의 PD상'을 공동 수상하였다.
이후 《MBC 스페셜》로 자리를 옮겨 이른바 '눈물 시리즈'의 한 부분을 이루는 대형 자연 다큐멘터리인 《아프리카의 눈물》을 취재, 연출하는 등 한동안 다큐멘터리 제작에 전념하였다.
이후 2012년 이명박 정권의 언론장악 움직임에 맞선 전국언론노동조합 MBC 본부의 이른바 '180일 총파업'에 적극 참여하였고, 파업이 실패한 이후 사측의 보복으로 시사교양국에서 쫓겨나 한때는 상암 MBC 사옥 앞의 스케이트장 관리직으로 배치되는 등 약 5년 동안 비제작부서를 전전하였다.
2017년 3월 박근혜 대통령의 탄핵과 5월 문재인 대통령의 당선 이후 같은 해 9월부터 약 3개월 간 진행된 전국언론노동조합 MBC 본부의 파업으로 박근혜 정권 아래 임명된 MBC 경영진이 사퇴하고 해직 PD 출신인 최승호 PD가 새 MBC 사장이 된 뒤 시사교양국에 복귀, 2018년 1월부터 3년 간 《PD수첩》의 진행을 맡았다. 2021년 《PD수첩》 진행자 자리에서 물러난 이후 주로 외주제작 프로그램의 관리를 맡았으며, 2025년 현재 《생방송 오늘아침》의 책임프로듀서를 맡고 있다.
한학수 황우석 사건
황우석 교수의 논문 조작 의혹과 관련된 제보를 황우석박사팀의 전연구원인 류영준으로부터 받고, 이를 오랫동안 추적 조사하여 자세한 내용을 《PD수첩》에서 5회에 걸쳐 방송하였다.
YTN과 윤현수, 안규리 등이 미국 피츠버그대 출장을 통해 취재윤리 문제를 제기하였고, 한 때 위기에 몰렸으나 생물학정보연구센터(BRIC)를 중심으로 한 젊은 과학자들과 네티즌들의 진실규명노력에 힘입어 노성일의 '체세포핵이식 줄기세포가 없다'는 결론을 이끌어낸다. 결국, 황우석은 수차례의 기자회견을 통해 현재 줄기세포가 없다는 사실과 사이언스지의 줄기세포수를 부풀려 논문을 작성했다는 자백을 하게 된다. 그에 이어진 서울대조사위원회의 조사활동과 검찰의 수사로 인해 황우석박사의 논문조작과 난자채취를 둘러싼 많은 문제점들이 드러나게 되고 황우석은 서울대 교수직에서 파면됨과 동시에 사기 및 횡령 등의 혐의로 법정에 서게 된다.
한학수 PD는 이 공로로 올해의 PD상 등 정론직필의 언론인에게 주어지는 영광스런 수상의 영예를 누리게 되었다.
한학수 저서
<진실, 그것을 믿었다 - 황우석 사태 취재 파일>
한학수 (지은이) | 사회평론 | 2014년 9월
<여러분! 이 뉴스를 어떻게 전해 드려야 할까요? - 황우석 사태 취재 파일>
한학수 (지은이) | 사회평론 | 2006년 11월
<아프리카의 눈물 : 슬프도록 아름다운 삶이 춤추는 땅>
장형원 , 한학수 지음 21세기북스 2012년 6월
<신화의 추락, 국익의 유령 - 황우석, 피디수첩 그리고 한국의 저널리즘>
원용진, 전규찬, 진중권, 문종대, 한학수, 양문석, 이형기, 최영재, 강양구, 조이여울, 최승호, 반현 (지은이) | 한나래 | 2006년 5월
<PD수첩, 한국 PD저널리즘의 보고>
최진용, 조능희, 임채유, 김환균, 이근행, 이우환, 김진만, 김현철, 한학수 (지은이) | 커뮤니케이션북스 | 2002년 6월
모르드바어군
모르드바어(Mordvin(ic), 러시아어: мордовские языки)는 러시아의 볼가강 중류에 사는 모르드빈인이 사용하는 우랄어족 계통의 언어이다. 하나의 언어로 보기도 하고 에르자어와 목샤어로 이루어진 언어군으로 보기도 한다. 중세에 일부 볼가핀족이 사용하던 언어들(메셰라어 등)이 모르드바어의 일종이었을 것으로 추정된다.
목샤어
목샤어(Moksha)는 에르자어와 같이 모르도바어의 한 방언으로, 모르도바 공화국에서 러시아어, 에르자어와 함께 공용어로 지정된 언어이다. 그 화자를 목샤인이라 한다.
목샤어 지역
현재 목샤어를 사용하는 사람들은 50만명이며 전통적으로 모르도바 공화국, 특히 그 서부에 분포되어 있다. 일부는 모르도비야 밖에도 거주한다.
다르긴인
다르긴인(다르기어: Дарганти, 러시아어: Дарги́нцы)은 다게스탄 공화국에 살고 있는 캅카스계 민족이다.
고유 언어인 북동캅카스어족의 다르기어를 사용한다. 오래 전부터 오늘날의 거주 지역에 살던 다게스탄의 원주민족으로서 인근의 체첸인, 아바르인 등과도 먼 친연 관계이다. 인구는 약 60만 명으로 추산되며 다게스탄 내에 그 중 425,526명이 거주하여 다게스탄에서 아바르인 다음의 제2민족이다. 종교는 대다수가 수니파 이슬람을 믿는다.
쿠르드어
쿠르드어(쿠르드어: Kurdî, 페르시아어: کردی)는 중동에 있는 쿠르디스탄에서 쓰이는 인도유럽어족 이란어군의 언어 또는 언어군이다.
역사적으로 쿠르디스탄이라고 불리는 지역에서 4천5백60만명의 쿠르드족에 의해 사용된다. 이라크와 이라크령 쿠르디스탄에서는 아랍어와 함께 공용어이며, 쿠르드족이 가장 많이 살고 있는 터키 동남부 지역에서도 일상어로서 위치가 확고한 편이다. 이란과 시리아의 쿠르드족 거주 지역에서도 널리 사용되며, 아르메니아에서도 지역 소수 언어로 공인되어 있다. 문자는 쿠르드족이 속한 각 나라마다 라틴 문자, 아랍 문자, 키릴 문자 등이 쓰이며, 여러 라틴 문자 정서법들도 서로 조금씩 차이가 있다.
단일 언어가 아닌 방언연속체로 이루어진 언어군으로 여겨지며, 크게 쿠르만지어(북부 방언), 소라니어(중부 방언), 그리고 팔레와니어(남부 방언)으로 나뉜다. 세 방언은 각각 터키, 이라크, 이란에 다수의 화자가 거주하나 분포는 국경과 큰 일치를 보이지는 않는다.
쿠르디스탄
쿠르디스탄(쿠르드어: Kurdîstan, 아랍어: كردستان, 페르시아어: کوردستان, 튀르키예어: Kürdistan, 영어: Kurdistan)은 쿠르드족의 인구나 문화의 분포 등을 기반으로 정의되는 서아시아의 역사적 지역이다. 주로 아나톨리아 반도(튀르키예) 동남부와 이란, 이라크, 시리아 등에 걸친 산악지대를 가리키며, 면적은 대략 30~40만 km²이다.
쿠르디스탄은 "쿠르드족의 땅"이라는 뜻으로, 쿠르드족이 인구의 대부분을 차지하고 있다. 2004년 이후 이라크에 쿠르드 자치구가 설립되고, 2013년 시리아에도 로자바라는 미승인 국가에 준하는 자치 지역이 설립되었다. 쿠르드인들은 현재 시리아와 이라크에서 IS 퇴치에 가장 큰 공헌을 하였다.
쿠르디스탄 역사
16세기에 쿠르드인의 거주 지역은 사파비 왕조와 오스만 제국에 걸쳐 존재하였다. 쿠르디스탄의 분할은 1514년에 칼디란 전투의 여파 속에 일어났다.
쿠르디스탄 지리
쿠르디스탄 지역은 북위 36도에 걸쳐 있다. 쿠르디스탄은 아르빌, 슐레이마니아 두혹, 키르쿠크, 디얄라 및 니네바의 일부 등 6개 자치 구역을 가지고 있다. 이 지역은 농업 및 관광 산업이 발달되어 있으며, 천연자원의 보고이다. 특히, 이 땅은 석유가 많이 매장되어 있다.
쿠르디스탄 인구
튀르키예에는 약 1천500만 명의 쿠르드족이 거주하고 있으며, 이는 중동 외(外) 지역 거주자 200만 명을 뺀 쿠르드족 전체 인구의 48%를 차지한다. 튀르키예에서 쿠르드족을 같은 튀르키예인으로 부르며 산악지대에 많이 살았기 때문에 '산악 튀르키예인'이라고 부르기도 한다. 튀르키예 공화국이 독립한 이후 튀르키예에서는 쿠르드족의 언어 사용 불법화(현재 폐지), 고유 의상 착용 금지 등 쿠르드족의 민족의식을 없애려고 하였다. 현재 튀르키예 정부와 이라크 북부로 이동한 쿠르드족의 독립 운동을 주도하는 PKK는 극렬 대립하고 있다.
이란에는 약 800만 명의 쿠르드족이 거주하고 있다. 이란의 쿠르드인들은 제2차세계대전 직후 소련의 지원 이래 마하바드 공화국을 세웠으나, 소련군이 철수하자 독립국은 인정받지 못하였다. 이후 자치주 성향의 지역이 되었으며 이란은 자국 내 쿠르드족들을 탄압하면서 정작 이란-이라크 전쟁 당시 이란 편에서 군인으로 활약하던 이라크 쿠르드인들을 지지하기도 했다.
쿠르디스탄 인구
이라크에는 약 600만 명의 쿠르드족이 거주하고 있으며, 사담 후세인의 집권 기간 동안 이란의 편에 있던 쿠르드인들을 탄압하여 국제적 비난을 받았다. 이라크 전쟁이 시작되자 이라크내의 쿠르드족들은 미국 편에서 싸워 사담 후세인을 물리치고 이라크에 새로운 정권이 들어서는 것에 많은 영향을 끼쳤다. 이라크 전쟁 이후 이라크 북부 유전 지대에는 쿠르드족 자치구가 생겨났으며 완전한 독립 국가를 시도하고 있다. 쿠르드족인 잘랄 탈라바니가 이라크의 대통령이 되었다.
시리아에는 약 200만 명의 쿠르드족이 거주하고 있다. 시리아의 북동쪽에 로자바라는 자치구가 설립되어 있다. 자세한 것은 시리아령 쿠르디스탄 문서에 있다.
아연
아연(영어: Zinc 징크[*],亞鉛←일본어: 亜鉛 아엔[*])은 화학 원소로 기호는 Zn(←라틴어: Zincum 징쿰[*]), 원자 번호는 30이다. 아연의 가장 일반적인 산화 상태는 +2이다. 사용량 기준으로 철, 알루미늄, 구리에 이어 네 번째로 중요한 금속으로 꼽힌다.
실온에서 약간 부서지기 쉬운 금속이며, 산화가 제거되면 반짝이는 회색 외관을 가진다. 주기율표 12족(IIB)의 첫 번째 원소이다. 어떤 측면에서 아연은 화학적으로 마그네슘과 유사하다. 두 원소 모두 하나의 정상적인 산화 상태(+2)만 나타내며 Zn2+ 및 Mg2+ 이온은 비슷한 크기이다. 아연은 지각에서 24번째로 풍부한 원소이며 5개의 안정 동위원소라는 특징을 지닌다. 가장 흔한 아연 광석은 황화 아연 광물인 섬아연석(아연 혼합)이다. 작업 가능한 가장 큰 광맥은 호주, 아시아 및 미국에 있다. 아연은 광석의 거품 부유, 로스팅 및 전기를 사용한 최종 추출(전기채취)을 통해 정제된다.
아연
아연은 인간, 동물, 식물 및 미생물에 필수적인 미량 원소이며 출생 전 및 출생 후 발달에 필요하다. 이는 철 다음으로 인간에게 두 번째로 풍부한 미량 금속이며 모든 효소 종류에 나타나는 유일한 금속이다. 아연은 또한 많은 효소의 중요한 보조 인자이기 때문에 산호 성장에 필수적인 영양소 요소이다.
아연 결핍은 개발도상국의 약 20억 명에게 영향을 미치며 많은 질병과 관련이 있다. 어린이의 경우 결핍은 성장 지연, 성적 성숙 지연, 감염 감수성 및 설사를 유발한다. 반응 중심에 아연 원자가 있는 효소는 인간의 알코올 탈수소효소와 같이 생화학에 널리 퍼져 있다. 아연을 과잉 섭취하면 운동실조, 무기력증, 구리 결핍이 발생할 수 있다. 해양 생물군계, 특히 극지방 내에서 아연 결핍은 일차 조류 군집의 활력을 손상시켜 잠재적으로 복잡한 해양 영양 구조를 불안정하게 만들고 결과적으로 생물 다양성에 영향을 미칠 수 있다.
아연
구리와 아연을 다양한 비율로 합금한 황동은 기원전 3천년 전부터 에게해 지역과 현재 이라크, 아랍에미리트, 칼미키아, 투르크메니스탄, 조지아가 포함된 지역에서 사용되었다. 기원전 2000년경에는 현재 서인도, 우즈베키스탄, 이란, 시리아, 이라크, 이스라엘을 포함한 지역에서 사용되었다. 아연 금속은 고대 로마인과 그리스인에게 알려졌지만 인도에서는 12세기까지 대규모로 생산되지 않았다. 라자스탄의 광산은 아연 생산이 기원전 6세기로 거슬러 올라간다는 확실한 증거를 제공한다. 현재까지 순수 아연에 대한 가장 오래된 증거는 순수 아연을 만들기 위해 증류 공정이 사용되었던 서기 9세기 초 라자스탄의 자와르(Zawar)에서 나왔다. 연금술사들은 아연을 공기 중에서 태워서 "철학자의 양모" 또는 "하얀 눈"이라고 부르는 것을 형성했다.
이 원소는 연금술사 파라셀수스(Paracelsus)가 독일어 단어 Zinke(갈래, 치아)를 따서 명명했을 것으로 본다. 독일의 화학자 안드레아스 지기스문트 마르그라프(Andreas Sigismund Marggraf)는 1746년 순수 금속 아연을 발견한 것으로 알려져 있다. 루이지 갈바니와 알레산드로 볼타의 연구는 1800년까지 아연의 전기화학적 특성을 밝혀냈다. 철의 부식 방지 아연 도금(용융 아연도금)은 아연의 주요 응용 분야이다. 다른 응용 분야로는 전기 배터리, 소형 비구조 주조물, 황동과 같은 합금이 있다. 탄산아연 및 글루콘산아연(식이보충제), 염화아연(탈취제), 아연 피리티온(비듬 방지 샴푸), 황화아연(발광 페인트), 디메틸아연 또는 디에틸아연과 같은 다양한 아연 화합물이 유기 실험실에서 일반적으로 사용된다.
아연 주요 성질
아연은 청색을 띤 회색의 금속이다. 아연은 산, 알칼리, 금속에 반응한다. 100 °C(212 °F)부터 210 °C(410 °F) 사이의 온도에서 전성과 연성이 매우 크며, 210 °C(410 °F)를 넘거나 실온에서는 금속이 부서지고 두들기면 가루가 된다. 비자성이며 모스 굳기는 2.5이다. 습한 공기 중에는 표면만 산화되며 이로 인해 내부가 보호된다.(그래서 산화될 가능성이 높은 수도관 등을 아연으로 도금하기도 한다.) 공기 중에서 내식성은 아연의 순도가 높으면 높을수록 좋다고 한다. 공기 중에서 가열하면 흰색의 불꽃을 내며 탄 후, 녹색의 산화물이 된다. 적열 상태에서는 물을 분해해 수소를 발생시키기도 한다.
아연 인체 내에서 역할
인체 내에서 아연은 세포를 구성하고 생리적인 기능을 다루는 대표적인 무기물 중 하나이다. 임신한 여성에게 아연이 부족하게 되면 기형아나 저체중아를 낳을 수 있다. 아연이 부족할 경우 성장발육에 문제가 있게 되며, 아연을 과잉섭취하게 되어도 미네랄 불균형이 생기어 사망 확률도 있다. 한편 셀레늄처럼 아연은 효소(enzyme)의 보조인자(cofactor)로 작용하여 효소의 기능을 완수하도록하는 것으로 알려져 있다.
아연 식물 내에서 역할
식물체 내에서의 아연은 식물체 내에서 발생하는 유해한 활성산소를 제거하는 효소 구성 성분으로, 망가니즈나 마그네슘 등과 같이 효소를 활성화시키는 역할을 한다.
아연 제조 방법
아연광석에는 다른 금속의 황화물 등의 불순물이 다량으로 함유되어 있으므로(아연 함유량은 보통 4～10%), 부유선광을 통해 아연 함유량을 60% 정도로 높인 다음, 이 광석을 융해점 419.5 °C 이하에서 가열하는 건식증류법 (乾式蒸溜法) 또는 습식제련법(濕式製鍊法)으로 제련하여 고순도의 아연을 만든다.
아연 사용
국내 경북 봉화, 강원 정선, 충북 제천·괴산 및 중국, 미국, 호주 등에서 생산되는 아연은
동적 계획법
수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
동적 계획법 설명
주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 이것은 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문이다. 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, 동적 계획법은 최적의 해법이라고 말할 수 있다.
동적 계획법 설명
때로는 단순한 재귀함수에 저장 수열(이전의 데이터를 모두 입력하는 수열)을 대입하는 것만으로도 최적해를 구할 수 있는 동적 알고리즘을 찾을 수 있다. 그러나 대다수의 문제는 이보다 훨씬 더 복잡한 프로그래밍을 요구한다. 그 중에 일부는 여러 개의 매개 변수를 이용하여 재귀 함수를 작성해야 하는 것도 있고, 아예 이러한 방법으로 동적 알고리즘을 짤 수 없는 문제 또한 존재한다. 이러한 퍼즐로는 대표적으로 Egg Dropping Puzzle이 있다.
동적 계획법은 위에서 설명했듯이, 가능한 모든 방법을 고려해야 한다는 단점이 있다. 이러한 단점을 극복하기 위하여, 동적 계획법 대신 그리디 알고리즘이 등장했다. 그리디 알고리즘은 항상 최적해를 구해주지는 않지만, 다행히 Minimum Spanning Tree(최소 신장 트리 문제) 등의 여러 문제에서 그리디 알고리즘이 최적해를 구할 수 있음이 이미 입증되었다.
동적 계획법 설명
그리디 알고리즘과 동적 계획법을 비교하자. 우리가 차량 정체 구간에서 A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 하자. 이 문제에서 동적 계획법을 사용한다면, 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로를 찾아낸다. 반면 그리디 알고리즘은 전체적인 상황을 고려하지 않고, 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색하여 찾아줄 것이다.
물론 동적 계획법으로 경로를 검색하는 동안 우리가 운전을 잠깐 쉬어야 하듯이, 우리는 동적 계획법을 사용하면 약간의 시간이 걸린다는 단점이 있다. 그러나 이렇게 얻어낸 경로는 (교통 환경이 변하지 않았다는 가정 하에) 우리가 갈 수 있는 가장 빠른 길이 된다고 장담할 수 있다.
반면 그리디 알고리즘은 즉효성이 있는 대신, 항상 최적의 경로를 찾아주지는 않는다. 각 구간마다 최적의 경로를 찾는다고 해도 그것이 전체적으로 최적의 경로가 되지는 않기 때문이다. 즉, 동적 계획법은 그리디 알고리즘에 비해 시간적으로는 효율적이지 못할 수는 있어도, 그 결과에 대해서는 효율적인 값을 구할 수가 있다.
동적 계획법 역사
수학자인 리처드 벨만이 1940년대에 사용하던 용어였다. 1953년, 벨만은 큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 데 사용하는 이 방법을 '동적 계획법'이라 이름붙였다.
벨만은 그의 자서전, '태풍의 눈'에서 다음과 같이 말했다.
동적 계획법 역사
나는 RAND 코퍼레이션에서 1950년의 가을을 보냈다.
 여기에서 내게 주어진 첫 과제는 다단계(multistage) 의사 결정 프로세스에 대해 적절한 용어를 명명하는 것이었다.
 '동적 계획법'이라는 이름이 어디에서 왔는지 궁금하지 않은가?
 1950년대는 내가 수학에 대해 연구하기에는 좋지 못한 시기였다.
 우리는 그 때 워싱턴에서 윌슨이라는 사람과 함께 일하고 있었다.
 윌슨은 연구라는 것에 대해 굉장히 병적인 공포를 가지고 있었다.
 사람들이 그 앞에서 연구에 대해 이야기를 꺼내면 그는 완전히 미치다시피 했다.
 그러나 불행히도 RAND는 공군 소속의 회사였고, 윌슨은 그 공군의 간부인 국방 위원장이었다.
 그래서 내가 RAND 안에 있었을 때 윌슨을 비롯한 공군들이 내가 수학에 대해 연구하는 것을 보이지 않게 막는다는 것을 알 수 있었다.
 처음 올 때는 나는 위의 문제에 대해 '의사 결정 프로세스'라는 이름을 사용했지만,
 여기에서 '프로세스(Process)'라는 단어를 사용하는데 여러 가지 차질이 생겨버리고 만 것이다.
 그래서 나는 사람들이 알지 못하게 '계획법(Programming)'이라는 단어를 붙였다.
 또한 나는 이 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, '동적(Dynamic)'이다라는 개념(idea)이 전달되길 원했다.
 이 단어야말로 내가 연구하는 알고리즘의 성질을 정확하게 짚어내었고,
 게다가 윌슨에게도 피해를 입히지 않으며 공군도 이 단어에선 꼬투리를 잡지 못했으니 그야말로 일석이조의 효과를 누린 것이다.
즉, 'Dynamic'이라는 말은 벨만이 이런 알고리즘의 '시가변적이며 다단계적인' 특성을 나타내기 위해서 채택한 용어인 것이다. 또한 'Programming'이라는 단어는 공군 내에서도 워드 프로세서 교육이나 군수 물자 운송 등에 이용되는 단어였기 때문에 사용하는데 아무 제약이 없었던 것이다. 이렇게 만들어진 '동적 계획법'이라는 단어는 선형 계획법이나 수리 계획법처럼 하나의 프로그래밍 기법을 나타내는 단어가 되었다.
동적 계획법 예제
보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.
이때, fib(5)를 구한다고 한다면 계산은 다음과 같이 이루어진다.
여기에서 세 번째 줄의 fib(2)가 중복되어 계산되고, 이것은 전체적인 계산 속도를 떨어뜨린다. 이 알고리즘의 시간 복잡도는 지수 함수가 된다.
여기에서 각 함수의 계산값을 저장하는 객체 m을 추가하면, 이 알고리즘은 다음과 같이 바뀐다.
이렇게 각 계산값을 저장하면, 중복 계산이 줄어들고 시간 복잡도는 O(n)이 된다.
베틀루가강
베틀루가강(러시아어: Ветлу́га)은 마리옐 공화국과 니즈니노브고로드주를 흐르는 강이다. 볼가강의 지류이고 코지모데먄스크에서 가깝다. 배가 항행할 수 있다.
코지모데미얀스크
코지모데먄스크(러시아어: Козьмодемья́нск, 초지마리어: Цикмä, 산지마리어: Чыкма)는 러시아 마리옐 공화국의 도시이다. 베틀루가강과 인접해 있으며 인구는 22,771명(2002년 기준)이다.
피아노 소나타 16번 (모차르트)
《피아노 소나타 16번 다장조 K. 545》는 볼프강 아마데우스 모차르트가 작곡한 가장 유명한 피아노 소나타 가운데 하나이다. 1788년에 빈에서 작곡되었다. 초심자용 피아노 소나타로도 불린다. 모차르트의 생전에는 출판되지 않았었고 1805년에야 출판되었다
피아노 소나타 16번 (모차르트) 구성
구성은 다음과 같다.
1. 알레그로 (Allegro)
2. 안단테 (Andante)
3. 론도 (Rondo)
구논회
구논회(具論會, 1960년 6월 20일~2006년 11월 5일)는 대한민국의 교육인 출신의 정치인으로, 제17대 국회의원이다.
구논회 생애
1960년 충청남도 보령에서 태어났고, 1985년 충남대학교 경제학과를 나왔다.
1995년 2월 위암 3기 선고를 받아 투병·수술을 하였으며, 이듬해 폐결핵을 앓게 되었다. 동시에 제약회사 영업사원과 학원강사로 활동하였으며, 1996년에는 대전 중구에 입시전문학원인 대학학원을 설립하여 대전 지역 명문 대형학원으로 성장시켰다.
1999년 이후 시민단체 후원과 난치병 어린이 돕기, 북한동포 돕기 등으로 사회에 봉사하였다.
2004년 5월 제17대 열린우리당 소속으로 국회의원으로 당선되었다. 2006년 열린우리당 원내부대표, 대전지역 지방선거 기획단장, 국회 정치개혁특별위원회 위원과 교육위원회 교육위원, 신행정수도 후속대책특위 위원, 행정자치위원으로 활동하였다.
위암이 2006년 4월 중순에 재발하여 늑막암 말기 진단을 받고 7개월간 투병하였고, 2006년 11월 5일에 46세로 별세했다.
조용순
조용순(趙容淳, 1898년 2월 19일~1975년 8월 27일)은 대한민국의 법조인이다. 제7대 법무부 장관과 제2대 대법원장을 역임했다. 본관은 임천, 호는 춘산(椿山)이며 충청남도 대덕군 출신이다.
조용순 생애
1918년 3월에 경성고등보통학교(현재의 경기고등학교의 전신) 본과를 졸업했으며 1922년 3월에 경성법학전문학교를 졸업했다. 1923년 3월부터 경성지방법원 개성지청에서 서기과 서기 겸 통역생으로 근무했고 1925년 4월에 실시된 판검사 특별 임용고시에 합격하여 판사 활동을 시작하였다. 1926년 7월 30일에는 해주지방법원 재령지청 판사로 임명되었고 1928년 11월 16일에는 일본 정부로부터 쇼와 대례 기념장을 받았다.
1932년 10월 28일에는 평양지방법원 판사로 임명되었고 1936년 8월 14일부터 1940년 8월 31일에 퇴직할 때까지 광주지방법원 순천지청 판사로 근무했다. 1937년 8월에는 일본 정부로부터 훈6등 서보장을 받았고 1940년 9월에는 종5위에 서위되었다. 1941년 5월 10일에는 황해도 해주부에서 변호사로 개업했으며 1943년 5월부터 1945년 8월 광복 때까지 황해도 해주부 부회의원을 역임했다. 이러한 행적으로 인해 민족문제연구소의 친일인명사전에 수록되었다.
조용순 생애
1945년 11월 19일에 대전지방법원 재판장으로 임명되었으며 1946년 4월 4일부터 1946년 5월 16일까지 대법원장을 역임했다. 1948년 8월 13일부터 1948년 11월 13일까지, 1952년 2월 7일부터 1953년 11월 6일까지 대구고등법원장을 2차례 역임했고 1954년 4월 18일부터 1958년 3월 31일까지 중앙선거위원회 위원장을 역임했다.
1954년 6월 30일부터 1955년 9월 15일까지 법무부 장관을 역임했고 1955년 11월 2일부터 1958년 6월 8일까지 사정위원회 위원장을 역임했다. 1958년 6월 20일부터 1960년 5월 16일까지 대법원장을 역임했다.
건설국민승리21
건설국민승리21(建設國民勝利21)은 1997년에 창당(정당 등록일은 11월 18일)된 대한민국의 진보정당으로, 약칭은 국민승리21이다.
건설국민승리21 역사
1990년 민주화 이후 최초의 진보정당인 민중당이 창당되었으나 선거득표 기준에 미치지 못하여 선관위에 의해 해산되었다. 민중당의 해산으로 인해 민중당 창당에 참여했던 노동운동가들은 분열을 겪었으며 이들은 민중당 재건파와 민자당 입당파로 나뉘었다. 이재오, 김문수 등을 위시로 한 민자당 입당파는 통일민주당의 대통령 후보였던 김영삼을 따라 민자당에 입당했으며 민중당 재건파는 진보정치연합을 창당하여 재기를 노렸다. 1995년 진보정치연합은 저명한 노동운동가인 권영길 민주노총 위원장을 대표로 추대했으나 권영길 민주노총 위원장은 "지금은 노동운동, 농민운동, 빈민운동에 집중할 시기"라 하여 진보정치연합에 선을 그었다. 이후 한국 최대 규모의 진보정치 단체인 민주주의 민족통일 전국연합이 진보정치연합에 합류하였으나 전국연합은 당 내 노선 갈등으로 인해 진보정치연합을 탈퇴하였고, 전국연합은 건설국민승리21 창당에 회의적이었던 진보정치연합과는 달리 직접적으로 국민승리21 창당에 참여하였다. 결국 전국연합의 탈퇴로 세력이 위축된 진보정치연합은 노선을 바꾸어 국민승리21에 합류하기로 결정하였다.
건설국민승리21 역사
이후 1996년 신한국당의 노동법 날치기 사건을 겪은 뒤 자극받은 노동운동계와 노동운동가들이 1997년 대한민국 대통령 선거에서 진보 진영의 대통령 후보를 추대하기 위해 전국민주노동조합총연맹이 건설국민승리21 창당에 합류하였고 이후 1997년 9월 7일에 당시 민주노총 위원장이던 권영길을 대통령 후보로 추대했는데, 그는 '일어나라 코리아'라는 구호 아래 '정치세력을 물리치고 참된 개혁과 진보의 정치를 펴자'라는 구호를 내걸고 대선에 뛰어들었으며, 투표 결과 306,026표를 획득하여 1.2%의 득표율을 기록하였다. 이후 국민승리21은 공동대표제를 실시하여 민주노총의 초대 위원장을 지낸 권영길과 민주주의 민족통일 전국연합의 대표를 지낸 이창복을 공동대표로 선출하였다.
1998년에 실시된 대한민국 제2회 지방 선거 때에는 노동계와 연대하면서 무소속 후보로 출마했으며, 울산광역시에서 2명의 기초단체장을 당선시키는 데에 기여했다.이 외에 성남시와 전라남도에서도 노동계 무소속 후보와의 연대를 통해 기초의원 당선자를 배출했다. 이후 국민승리21의 당원수가 급격히 증가하고 영향력이 커지자 민주노동당으로 당명을 변경하였다.
신태영 (1891년)
신태영(申泰英, 일본식 이름: 平山輔英히라야마 스케히데, 1891년 2월 1일 ~ 1959년 4월 8일)은 일제강점기의 군인이자 대한민국의 군인, 정치인이다. 본관은 평산이다. 일본군 장교, 학생 동원을 위한 군사교관 등으로 참전과 병력 동원을 위한 선전에 협력하여 친일반민족행위자에 이름을 올렸다.
신태영 (1891년) 생애
한성부에서 태어나, 14세 때에 대한제국의 육군유년학교에 입학하였으며 이어서 무관학교에서 수학하였다.
1912년 일본육군사관학교에 입학하여 1914년 5월 28일 제26기로 졸업하였다. 졸업 동기 중 한국인은 후에 일본군 중장을 지낸 홍사익을 비롯하여 지청천, 이응준, 조철호 등 13명이었다.
1917년 러시아 혁명을 계기로 일본이 군을 파병한 ‘시베리아 간섭전쟁’ 당시, 신태영은 북만주 이북에 파견된 일본군 연대 소속 장교로 일제의 침략 전쟁에 참가했다. 태평양 전쟁 당시 일본 제국 육군 중좌였다. 그는 특히 1943년 무렵에는 학생들을 전쟁에 동원하기 위한 ‘임시특별지원병제도 종로익찬위원회’에 참여해 병력 동원의 선전, 선동에 협력했다. 조선총독부 기관지인 ‘경성일보’에 발표한 ‘잡아라 철의 신념, 첫 출진의 목표는 야스쿠니 신사’라는 제목의 수기에서는 “제국의 신민이 되어 대화민족과 혼연일체가 되어 일본인을 중심으로 동아시아를 개척할 것”을 주장하는 한편 자신의 첫 출진의 목표가 “야스쿠니 신사(안장)”였다고 밝히기도 했다.
신태영 (1891년) 생애
광복 후 육사 동기생 대부분이 남조선국방경비대에 참여하였으나, 그는 근신하는 뜻으로 군문에 들어가지 않았다. 그 뒤 여순 14연대 반란사건이 터진 이후 자진 입대, 1948년 11월 대령계급과 함께 육군본부 행정참모부장 겸 국방부 제1국장이 되었다.
1949년 준장으로 진급, 호국군참모부장이 되었으며, 1949년 10월 소장진급과 함께 제3대 대한민국 육군 참모총장이 되었으나 재임 기간 7개월 만인 1950년 4월에 스스로 물러났다. 그것은 당시의 국방부 수뇌들과 의견이 맞지 않았고, 정세 판단에서도 낙관적인 견해를 보인 당시의 미국 고문관들과 달랐기 때문이다. 한국 전쟁이 발발하자 육군 전라북도 편성관구사령관으로서 이 지역의 방어에 임하였다. 그러나 이 때도 당시의 국방장관 신성모와 작전상의 의견충돌을 빚었으며 이에 따라 1950년 7월 해임되었다. 1952년 1월 복직되면서 곧 중장으로 승진하였으며, 2개월 후 1952년 3월, 육군 중장 예편과 동시에 국방부 장관이 되어 휴전 협정이 성립되기 직전까지 1년 3개월간 재임하였다. 같은 해 대한민국 재향군인회 회장(대한 제대장병보도회 회장)도 지냈다.
1959년 사망하여 국립현충원 장군 제2묘역에 묻혔다.
신태영 (1891년) 친일반민족행위자 수록
2008년 민족문제연구소에서 친일인명사전에 수록하기 위해 정리한 친일인명사전 수록예정자 명단에 선정되었으며 2009년 친일반민족행위진상규명위원회가 발표한 친일반민족행위 705인 명단에도 포함되었다.
김용우 (정치인)
김용우(金用雨, 1912년 4월 29일 ~ 1985년 9월 13일)는 대한민국의 정치인이다. 제2대 국회의원을 지냈으며 제6대 국방부 장관이다.
김용우 (정치인) 이력
배재고등보통학교 졸업을 거쳐 연희전문학교 수물과 본과와 미국 서던캘리포니아대학을 나온 후 남가주 대학교 대학원 수물과를 수료하였다. 서울특별시 후생국장, 중앙기술교육위원회 사무총장, 중앙관재처 운영처장, 조선주택영단이사장을 거쳐 1950년 제2대 국회의원에 당선되고 1954년 국회 사무총장을 거쳐, 1955년부터 1956년까지는 제6대 국방부차관, 1956년부터 1957년까지 제6대 국방부장관을 역임하고, 1957년 주영국 초대 대사에 임명되어 10월 28일, 영국 런던에 도착하였다. 1972년부터 1975년까지 대한적십자사 제11대 총재를 역임하였다. 국방부장관 재직시인 1957년 4월 3일 장관 특명 ‘국방총제2288호’를 통해 각 군 참모총장에게 안식교인 병사들을 위생병 또는 기타 직접 무기를 휴대치 않는 병과에 가급적 배치할 것을 명령했다.
김용우 (정치인) 이력
주영국 대사 김용우는 1958년 2월 24일부터 개막되어 4월 28일에 막을 내린 제네바 국제해양법회의에서 한국 측 대표로 참석하였다. 중요 5개 의제 중 하나였던 영해 문제에 대하여, 미국은 영해를 6리로 하고, 영해선에서 다시 6리를 연안국의 독점어업구역으로 하되, 부대조건으로서 독점어업구역에 있어서는 동 구역 내에서 과거 5년 이상 어로를 한 실적이 있는 국가의 기득권은 인정하되 연안국가와 이의가 있을 경우에는 5개국으로 구성되는 중재위원회의 재결을 받도록 하자고 제안하였다. 이와 같은 미국안에 대하여 한국 대표단은 전기한 독점어업권에 이의를 가져 이를 반대할 생각을 갖고 있었다. 그런데 미국대표단에서는 사람을 통하여 은근히 한국 대표단에게 자국안을 지지해 줄 것을 바라는 눈치를 보였다. 그러나 한국 대표단은 부대조건에 찬동할 수 없다는 태도를 표명하였다.
김용우 (정치인) 이력
미국대표단 아서 딘은 과거 판문점회담에서 유엔측 대표로 참석한 일도 있었고 제네바 회의에 나오기 전까지는 덜레스 미국무장관의 사설 법률사무소 사무국장으로 있었던 사람인데, 아서 딘은 일본정부 당국과 매우 친근한 사이로 널리 알려진 인사였다. 김용우 수석대표는 한국의 입장으로서는 도저히 미국안에 찬동할 수 없다고 결심하고 있었으니, 특히 한국은 당시 동해를 사이에 두고 일본과 어노문제로 야릇한 이해관계를 갖고 있음을 생각할 때 아무리 불가분의 우호관계에 있는 미국안이라고 해도 이를 받아들일 수는 없다는 것이 김용우의 배짱이었다. 미국대표단 측에서는 한국 측에서 명백히 미국안에 반대하리라는 것을 예측하자 본국과 연락하여 즉각적으로 서울과 지시가 내려 주한 미국대사관을 통하여 한국 외무부로 교섭이 닿았을 것으로 추측되었다. 4월 15일 총회에서 미국안에 대하여 김용우는 반대표를 던졌다. 표결 결과는 38대 36으로 아슬아슬하게 미국안이 부결되었다. 그런데 표결이 있던 날 아침 김용우는 돌연히 정부로부터 "긴급훈령"을 접수하였다. 긴급훈령의 내용은 영해6리를 제안하는 미국안에 찬동하라는 내용으로 추정되었다. 단, 미국안 중 중요한 부대조항에 대해서는 언급이 없었다. 김용우는 이 훈령에 대하여 망설이다가 반대표를 던진 것이었다. 유럽지역 주재 공관장 회의에 참석하기 위하여 귀국한 김용우는 사표를 제출하였다. 어쨌든 정부는 미국측과의 외교 신의를 깨뜨린 체면을 세워야 했다. 사표를 냈지만 "의원면직"이 아닌 "해임"이 김용우 대사에게 내려졌다.(5월 14일)
1962년 동양방송 TV(현 KBS 2TV)를 설립하였다.
족제비
족제비(학명: Mustela sibirica)는 식육목 포유동물이다. 족제비는 대한민국, 북한, 중국, 러시아 연해주 지역에 분포하며, 인가에도 흔히 나타난다.
족제비 생태
몸길이는 수컷이 40cm, 암컷이 30cm이고 꼬리 길이는 수컷 20cm, 암컷 10cm 정도이다. 털빛은 보통 황적갈색으로서 광택이 나는데, 등쪽은 갈색이고 입술과 턱은 흰색이며 주둥이 끝은 흑갈색을 띤다. 몸은 가늘고 길며 다리는 짧다. 귀는 둥글고 넓적하다. 짝짓기는 늦겨울에서 초여름까지이며, 임신기간은 30~35일이고 한배에 2~10마리의 새끼를 낳는다. 수명은 7년 정도이다. 먹이는 주로 들쥐, 집쥐, 메추라기, 새알, 새우, 올챙이, 개구리, 가재, 게, 물고기 등을 잡아먹으나 사육하는 닭이나 오리 등의 가금류를 해치기도 한다. 털가죽은 목도리나 밍크의 대용, 서예용 붓을 만드는 데 쓰인다. 주로 개울을 끼고 있는 숲, 굴, 빈 나무, 인가 근처, 나무뿌리·돌무덤 등의 굴에 서식한다. 평소 땅위에서 생활 하지만 나무에 오르는 것을 좋아한다. 그 외에도 야생성이 짙은 특색상 족제비는 숨어 있는 공간까지도 쉽게 지나가는 것을 가지고 있으며, 심지어는 음식까지 훔쳐 먹게 되는 경우도 간혹 있다.보경
족제비 계통 분류
다음은 2018년 로(Law) 등의 연구에 기초한 족제비아과의 계통 분류이다.
데이크스트라 알고리즘
컴퓨터 과학에서 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다.
이 알고리즘은 변형이 많다. 데이크스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다.
데이크스트라 알고리즘
그래프에서 주어진 소스 꼭짓점에 대해서, 데이크스트라 알고리즘은 그 노드와 다른 모든 꼭짓점 간의 가장 짧은 경로를 찾는다.:196–206 이 알고리즘은 어떤 한 꼭짓점에서 다른 한 도착점까지 가는 경로를 찾을 때, 그 도착점까지 가는 가장 짧은 경로가 결정되면 멈추는 식으로 사용할 수 있다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다. 따라서 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 IS-IS (Intermediate System to Intermediate System)와 OSPF(Open Shortest Path First)에서 주로 사용된다. 또한 데이크스트라 알고리즘은 존슨 알고리즘 같은 알고리즘의 서브루틴으로 채택되었다.
데이크스트라 알고리즘
데이크스트라의 원래 알고리즘은 우선순위 큐를 사용하지 않았기 때문에 시간 복잡도가  (는 꼭짓점의 개수이다)이다. 이 알고리즘의 개념은 Leyzorek 외. 1957에서도 사용된다. 최소 우선 큐에 기반한 알고리즘은 피보나치 힙으로 수행되며 시간복잡도는 Fredman & Tarjan 1984 때문에  (는 변의 개수이다)이다. 이 알고리즘은 알려진 제한 없는 음이 아닌 가중치를 가지는 무작위 유향 그래프에서의 단일 소스 최단 경로 알고리즘 중 점근적으로 가장 빠른 알고리즘이다. 하지만, 특별한 경우(제한이 있는 정수 가중치나 유향 비순환 그래프 등의 경우)에는 다른 § 세분화된 변형으로 개선할 수 있다.
어떤 분야, 특히 인공 지능 분야에서, 데이크스트라 알고리즘이나 그 변형은 균일 비용 탐색으로 알려져 있으며 최상 우선 탐색의 일반적인 아이디어의 예시로 공식화되어있다.
데이크스트라 알고리즘 역사
로테르담에서 흐로닝언까지, 일반적으로 한 도시에서 다른 도시로 가는 가장 짧은 길은 무엇일까요? 이것은 제가 이십 분 동안 생각해낸 최단 거리를 찾는 알고리즘입니다. 어느 날 아침에 저는 제 약혼녀와 암스테르담에서 쇼핑을 하고 있었고, 지쳤었기 때문에 카페 테라스에 앉아서 커피를 마시면서 그 문제에 대해서 생각하다가 최단 거리를 찾는 알고리즘을 고안했습니다. 제가 말했듯이, 이것은 이십 분 짜리 발명품입니다. 사실, 이 알고리즘은 삼 년 뒤인 1959년에 발표했습니다. 그 간행물을 여전히 읽을 수 있습니다. 사실은 꽤 괜찮습니다. 이것이 괜찮은 이유 중 하나는 제가 이 알고리즘을 고안할 때 연필과 종이 없이 고안했다는 것입니다. 제가 나중에 알게 된 바로는 연필과 종이 없이 고안하는 것의 좋은 점은 고안 할 때 피할 수 있는 복잡성을 피하도록 거의 강요되기 때문이라고 합니다. 갑자기 그 알고리즘이 나타남이 저를 놀랍게 했으며 제 명성의 초석이 되었습니다.— 에츠허르 데이크스트라, Philip L과의 인터뷰에서. Frana, Communications of the ACM, 2001
데이크스트라 알고리즘 역사
데이크스트라는 1956년에 네덜란드 국립 수학 정보과학 연구소에서 새로운 컴퓨터 ARMAC의 수용력을 입증하는 프로그래머로 일할 때 최단 경로 문제에 대해서 생각했다. 이제 해야 할 일은 컴퓨터를 다루지 않는 사람들도 이해할 수 있도록 문제와 (컴퓨터가 만들어낸)해법을 둘 다 선택하는 것이었다. 그는 최단 거리 알고리즘을 고안하고, 이후 ARMAC에서 약간 단순화된 네덜란드 도시 64개(도시의 숫자를 표시하기 위해서 6 비트만 필요하도록 64를 선정했다)의 교통 지도에 대해서 수행했다. 일 년 뒤, 데이크스트라는 기관의 다음 컴퓨터를 작업하던 하드웨어 엔지니어들의 문제를 직면했다: 기계의 후면 패널에 있는 핀을 연결할 때 필요한 전선의 개수를 최소화하는 것이다. 그 해법으로, 프림 최소 신장 트리 알고리즘으로 알려진 알고리즘을 재발견 했다(이전에는 Jarník에 의해 알려져 있었고, 또한 프림에 의해 재발견 되었었다). 데이크스트라는 이 알고리즘을 프림이 발표한 지 2년 뒤이고 Jarník이 발표한 지 29년 뒤인 1959년에 발표했다.
데이크스트라 알고리즘 알고리즘
시작할 꼭짓점은 초기점으로, 꼭짓점 Y의 거리를 초기점에서 Y까지의 거리로 정의한다. 데이크스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 거듭하며 개선시킬 것이며, 이 개선시키는 것을 간선 완화(edge relaxation)이라고 한다.
현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 그 시험적 거리를 현재 꼭짓점에서 계산한다. 새로 계산한 시험적 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣는다. 예를 들어, 현재 꼭짓점 A의 거리가 6이라고 표시되었고, 인접 꼭짓점 B로 연결되는 변의 길이가 2라고 한다면, A를 통한 B까지의 거리는 6 + 2 = 8이 된다. 이전의 B까지의 거리가 8보다 컸다면 8로 바꾸고, 그렇지 않다면 그대로 놔둔다.
경로를 계획하고 있을 때, 사실은 위에서 했던 것처럼 도착점이 "방문"한 상태가 될 때까지 기다릴 필요가 없다: 도착점이 "미방문" 꼭짓점들 중 가장 시험적 거리가 작아지면 (그리고 다음 "현재 위치"로 선택될 수 있다면) 알고리즘을 종료할 수 있다.
데이크스트라 알고리즘 설명
참고: 이 문단에서는 이해를 돕기 위해서 교차로, 도로 그리고 지도라는 용어를 사용했지만, 공식적인 용어는 각각 꼭짓점, 변 그리고 그래프이다.
도시의 지도에서 출발지와 목적지 사이의 가장 짧은 거리를 찾는다고 하자. 데이크스트라 알고리즘에서는 교차점마다 출발지로부터의 거리를 적어서 가장 짧은 거리를 찾는다.
데이크스트라 알고리즘에서는 우선 모든 교차점에 무한대를 적어놓는다. 이 표시는 실제 거리가 무한대라는 뜻이 아니라 교차로에 가보지 않았다는 것을 의미한다. 변형된 데이크스트라 알고리즘에서는 표시되지 않음을 써놓기도 한다.
다음으로는 모든 교차점을 표시할 때까지 반복한다. 우선 현재 위치를 정하고 시작점으로부터의 거리를 쓴다. 시작할 때의 현재 위치는 시작점이다. 그리고 시작점으로부터의 거리는 당연히 0이다.
그 다음 현재 위치와 연결되어있는 교차로들의 거리를 갱신한다. 현재 위치에는 시작점으로부터 가장 짧은 거리가 쓰여 있다. 현재 위치 에 쓰여 있는 거리를 , 이웃 교차로로 연결된 도로의 길이를 , 이웃 교차로에 쓰여 있는 거리를 라고 할 때, 이면 이웃 교차로에 최단 거리는 이며 이 값은 로부터 계산되었다라고 쓴다. 이 과정을 완화라고 한다.
데이크스트라 알고리즘 설명
현재 위치에서 연결된 모든 이웃 교차로에 대해 완화가 끝나면 현재 위치에 방문함이라고 적고 현재 위치에서 가장 가까운, 방문하지 않은 교차로로 이동한다. 방문표시가 된 교차로에는 항상 최단거리가 적혀있을 것이다. 만약 방문하지 않은 이웃 교차로가 없는 경우에는 현재 위치의 거리가 계산된 교차로로 돌아가서 가까운 방문하지 않은 교차로로 이동한다.
현재 위치가 목적지라면 탐색을 종료한 뒤 최단 거리를 바탕으로 최단 경로를 찾는다.
출발지를 제외한 모든 교차로에는 자신이 계산되어온 교차로가 쓰여 있을 것이다. 이 교차로를 부모 노드라고 한다. 목적지에서 부모 노드를 계속 따라가면 최단경로를 따라서 출발지에 도착하게 된다.
이 알고리즘은 목적지를 향해서 조사하지 않고, 목적지까지의 최단거리보다 짧은 교차로들을 모두 고려하기 때문에 최단 거리를 찾을 수 있게 된다. 하지만 모든 교차로를 고려한다는 특징으로 인해 데이크스트라 알고리즘은 특정한 지도에서 상대적으로 느리게 작동할 수 있다.
데이크스트라 알고리즘 의사 코드
다음 알고리즘에서, 코드 u ← vertex in Q with min dist[u]는 꼭짓점 집합 Q에서 가장 작은 dist[u] 값을 가지는 꼭짓점 u를 찾는다. length(u, v)는 두 인접한 꼭짓점인 u와 v를 연결하는 변의 길이 (둘 간의 거리)를 반환한다. 18번째 줄의 변수 alt는 루트 꼭짓점에서 u를 통해서 인접 꼭짓점 v까지 가는 경로의 길이이다. 이 경로가 현재 v에 대해서 기록된 최단 경로보다 짧다면, 현재 경로를 이 alt 경로로 대체한다. prev 배열은 소스까지 최단 경로를 찾기 위한 소스 그래프의 "다음" 꼭짓점을 나타내는 배열이다.
만약 source에서 target까지의 최단 경로만을 구하고 싶다면, 15번째 줄에 u = target을 추가해서 종료시킬 수 있다.
그리고 나서는 source에서 target까지의 최단 경로를 역방향 반복을 통해서 읽을 수 있다:
그러면 수열 S는 source에서 target으로 가는 경로에 있는 꼭짓점의 목록이거나 경로가 존재하지 않다면 빈 수열이다.
데이크스트라 알고리즘 의사 코드
더 일반적인 문제는 source에서 target까지 가는 모든 최단 경로를 찾는 것이다(같은 길이를 가지는 다른 경로가 있을 수 있다). 그러면, 각각의 prev[]에 꼭짓점 하나만을 저장하는 것이 아니라, 경감 조건을 만족하는 모든 꼭짓점을 모두 저장할 수 있다. 예를 들어, r과 source가 둘 다 target으로 연결되어 있고 (변의 비용이 두 경우 모두 다 같아서) 둘 다 target으로 가는 다른 최단 경로에 있다면, prev[target]에 r과 source 모두 추가해야 한다. 알고리즘이 끝나면, prev[]의 자료구조는 원래 그래프의 일부 변이 제거된 부분 집합을 나타낼 것이다. 이 자료구조의 가장 중요한 특성은 알고리즘의 시작점이 여러 개였을 때, 새 그래프에서 그 꼭짓점에서 다른 꼭짓점으로 가는 모든 경로가 원래 그래프의 그 꼭짓점에서도 최단 경로라는 점과, 원본 그래프에서 그 길이를 가지는 모든 경로가 새로운 그래프에도 나타난다는 점이다. 실제로 주어진 두 꼭짓점 간의 최단 거리를 모두 찾기 위해서는 새로운 그래프에서 깊이 우선 탐색 같은 경로 찾기 알고리즘이 필요하다.