반응형 2017/0564 [알고리즘] 최소비용신장트리(Minimum Spanning Tree) - 1 최소비용신장트리(Minimum Spanning Tree) - 1 최소 신장트리는 다양한 분야에서 응용되는 가장 기본적인 그래프 문제이다.보통 네트워크(통신, 도로, 가스배관 등) 디자인과 같이 뭉뚱그려서 말하는데연결되어 있으면서 비용이 최소화 된다는 것은 모든 종류의 네트워크에서 요구되어지는 것이기 때문이다.또한 이미지 프로세싱과 같은 분야에서도 이와 같은 알고리즘을 많이 사용된다. 구체적인 예를 들자면, N개의 도시가 있고 도시와 도시를 연결하는 도로의 비용 W가 있다.위의 그래프에서 정점들이 도시들이고 엣지의 weight가 비용이라고 가정한다. 엣지가 없는 경우에는 어떠한 이유로 두 도시를 직접 연결하는 도로를 만드는것이 불가능하거나그 비용이 무한대라고 가정한다. 예산이 충분하다면 모든 도시간의 도로.. 2017. 5. 24. [Javascript] 자바스크립트의 실행 문맥(Context) 자바스크립트의 실행 문맥(Context) 123456789101112console.log("global context"); function context1(){ console.log("first context");}; function context2(){ context1(); console.log("second context"); }; context2(); cs 자바스크립트는 하나의 콜 스택을 가지며 이 콜 스택에 함수의 호출 정보 등이 쌓인다.콜 스택에 쌓이는 함수의 정보를 실행 문맥(Context)이라고 한다. 자바스크립트의 변수는 함수 단위의 Scope를 가지며, 때문에, 콜 스택에 쌓인 실행 문맥을 기준으로 변수의 스코프가 결정된다. JS파일이 실행되면 가장 먼저 main context가 스택에 .. 2017. 5. 24. [알고리즘] DAG와 위상 순서 DAG와 위상 순서 DAG(대그)란 Directed Acyclic Graph를 뜻한다.직역하면 '방향성 비 사이클' 그래프이며 방향을 가지되, 루프를 생성하지 않는 그래프를 말한다.여기서 루프, 또는 사이클이란 자기 자신에서 출발해서 다시 자신에게 돌아오는 경로를 말하며비 사이클이므로 이러한 경로가 없어야 한다. 위의 그래프에서 엣지들을 따라 가면 어느 경로에서도 자기 자신으로 돌아올 수 없다. DAG는 중요한 용도를 가지는데,일반적으로 작업의 우선순위를 표현할 때 DAG의 구조를 가지게 된다. 예를 들면, 집을 지을 때 기초공사나 기둥세우기, 인테리어 등을 해야한다.이 때, 기둥을 세우기 전에 인테리어를 할 수 없듯이다른 것 보다 선행 되어야 하는 것들 표현 하기 위해 DAG가 유용하게 사용된다. 만약.. 2017. 5. 24. [Javascript] Scope와 변수 Scope와 변수 Scope는 '범위'를 나타낸다.좀 더 자세히 말하자면 변수가 적용되는 '유효 범위'의 개념이다. 유효 범위에 따라서 변수는 지역 변수(Local variable)와 전역 변수(global variable)로 나뉜다.예를 들어 지역 변수는 해당 스코프, 즉 자신이 영향을 미칠수 있는 범위에서만 호출, 변경 될 수 있고전역 변수는 전 영역에서 사용될 수 있다.이는 프로그래밍에서 상당히 중요한 개념이며 각 언어마다 스코프의 개념이 조금 다를 수 있다. 자바스크립트가 대표적으로 Scope의 개념이 전통적인 방식과 다른 예인데,C나 Java 등의 언어는 블록 단위로 스코프가 매겨지만, 자바 스크립트는 함수 단위 스코프이다. 그 말인즉, C나 Java 등이 if나 while 등의 블록 내에서 변.. 2017. 5. 24. 이전 1 ··· 3 4 5 6 7 8 9 ··· 16 다음 반응형
