트리의 개념 트리는 노드로 이루어진 자료 구조 트리는 하나의 루트 노드를 갖는다 루트 노드는 0개 이상의 자식 노드를 갖는다 그 자식 노드 또한 0개 이상의 자식 노드를 갖고, 이는 반복적으로 정의된다 노드들과 노드들을 연결하는 간선(edge)들로 구성되어있다 트리에는 사이클(cycle)이 존재할 수 없다 노드들은 특정 순서로 나열될 수도 있고 아닐수도 있다 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다 각 노드는 어떤 자료형으로도 표현 가능하다 let Node = function (value) { this.value = value; this.children = []; }; 루트 노드(root node) 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다 단말 노드(leaf node..

선택정렬 (Selection sort) 주어진 자료들 중에 현재 위치에 맞는 자료를 찾아 선택하여 위치를 교환하는 알고리즘. 한번 순회를 돌게 되면알고리즘 상 전체 자료 중 가장 작은 값의 자료가 0번째 인덱스에 위치하게 되므로, 그다음 순회부터는 1번 인덱스부터 순회를 돌며 반복하면 된다. 0번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 0번째 인덱스와 스왑 1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 1번째 인덱스와 스왑 ... n-1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 n번째 인덱스와 스왑 선택정렬은 현재 자료가 정렬이 되어있건 말건 무조건 전체 리스트를 순회, 검사하기 때문에 최선의 경우든 최악의 경우든 한결같이 O(n^2)의 시간복잡도를 가지고 있다. function..

시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 시간 복잡도 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 작성 방법에 따라 걸리는 시간이 달라지며, 시간이 적게 걸리는 것이 좋은 소스이다. 시간 복잡도에는 빅-오 표기법이라는 개념이 나온다. 예를 들어, 동전을 던져 뒷면이 나올 확률을 얘기 할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안 좋다면 n번 만큼 동전을 던져야 하는 경우가 발생한다. 이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부른다. O(1) Constant Time (상수) 입력 데이터 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘. ..

주어진 넓이를 주어진 타일로 채우는 문제인 타일링은 재귀적 사고방식으로 봐야 패턴을 확인 할 수 있다. f(1), f(2), f(3)... 같이 순차적으로 값을 파악하기보다 f(n), f(n-1), f(n-2) 같이 역순으로 파악하며 구조와 패턴을 찾아야 한다. 타일링의 패턴을 찾기위해 거쳐야 하는 과정은 다음과 같다. 맨 마지막에 들어갈 수 있는 타일의 경우의 수 찾기 => 넓이가 증가할 때마다 나타나는 특이 케이스 찾기 2xn 타일링 2 x 1 크기의 직사각형 타일로 2xn 넓이를 채우는 경우의 수의 개수 구하기 2xn을 채우는 경우의 수 개수 = f(n) f(n)에서 마지막에 오는 타일의 경우의 수는 두 가지 경우밖에 없다. 한 개가 세워져 있는 경우 두 개가 눕혀져 있는 경우 이런 패턴으로 보면 ..

버블 정렬(Bubble Sort)알고리즘의 개념 요약 오름차순을 기준으로 정렬 서로 인접한 두 원소를 검사하여 정렬 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환 선택 정렬과 기본 개념이 유사 버블 정렬(Bubble Sort)알고리즘의 구체적인 개념 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를,... 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로, 2회전 에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘..

스택 자료구조 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. 큐 자료구조 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다. 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있다. 재귀 함수 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다. 단순한 형태의 재귀 함수 예제 '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다. 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다. function recursiveFunction() { console.log("재귀 함수를 호출합니다."); recursiveFunction(); } 재귀 함수의 종..