hceaan

그래프의 정의 : 그래프는 정점(노드)와 간선(엣지)로 이루어진 자료구조를 의미한다. 또한 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프로 나뉜다. 그래프의 표현 그래프를 표현하는 방식에는 크게 연결선 리스트, 인접 행렬 , 인접 리스트 세가지로 나눌 수 있다. 연결선 리스트 [ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5], [3,8], [4,5], [4,9], [7,8], [7,9] ] 인접 행렬 [ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0, 1], [0, 0, 0, 0, 1, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0, 1..

DP 알고리즘이란? 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다. Dynamic은 별 의미 없고 단지 멋있어서 붙인 이름이라고 한다. DP 방법 모든 작은 문제들은 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해 놓는다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. DP 조건 - 작은 문제가 반복 일어나는 경우 - 같은 문제는 구할 때 마다 정답이 같은 경우 Memoization? 메모이제이션은 한번 계산한 작은 문제를 저장해놓고 다시 사용하는 것을 말한다. 예를 들어 피보나치를 재귀함수로 풀게 될 경우 위의 그림처럼 했던 작업을 또 하게 되는데 예를 들어 F(3)의 경우 또 구하게 된다. 이 때 DP 조건..

DFS(Depth First Search) : 원하는 해를 찾기 위해서 전진할 수 있을때 까지 전진하고, 만약 전진하다가 나아갈 길이 보이지 않는다면 바로 전에 선택한 갈림길에서 다른길을 선택하여 또 전진하는 방식 BFS(Breadth First Search) : 원하는 해를 찾기 위해서 자식노드들을 전부 검사해 나가면서 전진하는 방식 깊이우선탐색은 자식노드에 또 자식노드를 참가하는 방식으로 진행되기 때문에 LIFO(Last in Firt out)의 구조이다. 따라서 스택(Stact)을 저장구조로 사용한다. 너비우선탐색은 처음에 들어온 노드를 우선적으로 검사하기 때문에 FIFO(First in First out) 구조로 큐(Queue)를 사용한다. 위와 같은 트리가 있을 경우 탐색과정은 이렇다. DFS ..

버블정렬 : 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 과정 1. 첫번째 요소와 두번째 요소를, 두번째 요소와 세번째 요소를, ... , 마지막-1 요소와 마지막 요소를 비교하며 교환한다. 2. 1회전을 수행하고 나면 맨 끝에 가장 큰 요소가 가게되므로 맨 끝은 제외하고 정렬을 다시 반복한다. 선택정렬 : 제자리 정렬 알고리즘 중 하나이다. 과정 1. 주어진 리스트 중에 최소값을 찾는다. 2. 그 값을 맨 앞에 위치한 값과 교체한다(패스) 3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 삽입정렬 : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써..

완전탐색이란 : '모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘' 을 뜻한다. 영어로는 Exhaustive Search 라고 한다. 가능한 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀때 가장 강력하고 확실한 방법이지만 그만큼 시간이 가장 오래 걸리는 탐색 기법이다 완전탐색을 풀기 위한 방법 4가지 1. for 문 2. 순열, 조합 3. 재귀함수 4. 비트마스크 예시 문제 function solution(answers) { const answer = []; const solver_01 = [1,2,3,4,5]; const solver_02 = [2,1,2,3,2,4,2,5]; const solver_03 = [3,3,1,1,2,2,4,4,5,5]; const score = [0,0,0]; //맞..

조합함수 function combination(n,r){ if(n===r || r===0){ return 1; } else{ return combination(n-1,r-1)+combination(n-1,r); } } 오브젝트 길이 구하기 Object.keys(objectName).length 배열 정렬 array.sort() 배열 순서바꾸기 array.reverse(); 배열 자르기 var a = [1, 2, 3, 4, 5]; a.slice(0, 3); // [1, 2, 3]을 반환한다. a.slice(3); // [4, 5]를 반환한다. a.slice(1, -1); // [2, 3, 4]를 반환한다. a.slice(-3, -2) // [3]을 반환한다. 인덱스 찾아서 배열 요소 제거하기 let a =..