1. 강한 결합 요소(SCC, Stongly Connected Component) 강한 결합 요소란 유향 그래프 안에서 강하게 결합된 정점 집합을 의미한다. 서로 긴밀하게 연결되어있기 때문에 강한 결합 요소라고 하며, SCC 알고리즘이라고 불린다. 좀 더 쉽게 설명하자면, 싸이클(원형 그래프)를 생각하면 되는데, 두 가지 조건을 만족해야 한다. 1. 임의의 유향 그래프 내 정점 A, B 사이에 경로가 항상 존재해야한다. 2. A에서 B로 가는 경로, B에서 A로 가는 경로가 동시에 존재할 수 없다. [그림 1]을 보면 충분히 SCC인지 아닌지 판별할 수 있다. 왼쪽 섹션에 있는 그림은 조건 1, 2를 둘 다 만족하고 있으므로 강한 결합 요소다. 하지만 오른쪽 두 그림은 두 점을 지나는 경로가 존재하기 때..

1. 위상 정렬 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. [그림 1]을 보자. [그림 1]은 임의로 만든 마법사로 전직을 한후 배워야하는 스킬의 관계도다. 각 스킬에 대한 관계도를 정리하면 다음과 같다. 에너지 볼트는 맨 처음에 배우는 기본 마법이다. 매직클로를 배우려면 에너지볼트를 먼저 배워야한다. 메테오를 배우려면 먼저 매직클로, 텔레포트를 배워야한다. 마력 흡수를 배우려면 먼저 에너지 볼트를 배워야한다. 텔레포트를 배우려면 먼저 마력흡수, 매직클로를 배워야한다. 이러한 흐름은 조건을 걸어줘서 해석할 수 있다. 먼저 마법사로 전직하면 에너지 볼트를 찍고, 그 다음엔 마력 흡수 또는 매직클로를 찍는다. 그리고 텔레포트를 찍고 최종적으..

1. Expression 자바스크립트에서 표현식(Expression)은 값을 리턴하는 것을 말한다. 다음 코드를 보면 알 수 있다. const add = function(a, b){ return a + b; } const result = add(1,3); // add(1,3)은 값을 리턴하므로 add(1,3)은 표현식이다. console.log(2+2); // 2 + 2 => 값 리턴 => 표현식 console.log(Math.random() + 10); // 값 리턴 -=> 표현식 2. Statement 자바스크립트에서 Statement는 명령, 지시를 말한다. 위 예제를 그대로 가져와보면, const add = function(a, b){ return a + b; } const result = add..

1. 플로이드 와샬 알고리즘 지난 번에 포스팅했던 다익스트라 알고리즘은 하나의 정점을 출발점으로해서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 그런데 이번에 포스팅할 플로이드 와샬 알고리즘은 모든 각각의 정점을 출발점으로해서 모든 정점까지의 최단경로를 구하는 알고리즘이다. 하나의 정점을 출발하는 것이 아니라, 그래프에 있는 모든 각각의 경로에 대한 최단경로를 구하기 때문에 시간복잡도는 O(N³)이다. 또한 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 이게 무슨 말인지 감이 안오더라도, 지금부터 하는 설명을 들으면 어떤 순서로 알고리즘이 수행되는지 알 수 있을 것이다. [그림 1]은 그래프의 각 정점에 대한 가중치를 순차자료구조로 변환한 것이다. 먼저 출발 정점을 A로 설..

스코프(Scope) 자바스크립트에서 스코프는 어떤 변수에 접근할 수 있는지 없는지를 정의한다. 스코프는 크게 전역 스코프, 지역 스코프로 나뉜다. 전역 스코프(Global Scope) 전역 스코프는 모든 함수에 속하지 않고, 블록({})안에도 속하지 않은 가장 바깥에 있는 범위를 말한다. 그리고 전역 스코프에 있는 변수를 우리는 전역 변수라고 한다. 전역 변수를 선언하면 어느 블록이든지 간에 선언된 전역변수를 사용할 수 있다. const greeting = "Hello!"; function sayHello(){ console.log(greeting); } sayHello(); // "Hello!" 지역 스코프(Local Scope) 지역 스코프는 함수, 블록({})과 같이 특정 범위를 가리킨다. 지역 스..

1. 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단거리 알고리즘이다. 최단거리 알고리즘의 사용 예시로 도시의 지도에서 출발지에서 목적지 사이의 거리 중 가장 짧은 거리를 찾는 네비게이션이나, 인공위성 GPS 소프트웨어 등이 있다. 다익스트라 알고리즘은 음의 간선을 포함할 수 없기 때문에 모든 가중치가 양수여야만 한다 다익스트라 알고리즘의 실행 순서는 다음과 같이 동작한다. 모든 꼭지점을 미방문 상태로 만든다. 시작 정점을 정한다(정점 A에서 탐색을 시작할 건지, 정점 B에서 시작할 건지 결정). 시작정점 A를 방문상태로 처리한다(시작 정점을 A라고 가정). 정점 A에 인접한 정점으로 가는 모든 거리 값을 기록한다. 정점 A에 각각의 인접 정점과 연결된 거리 중에서, ..