조각모음

패스트캠퍼스 코딩테스트 인터넷 강의, 잔재미코딩 님의 수업을 참고하였습니다. BFS와 DFS란? 대표적인 그래프 탐색 알고리즘 너비 우선 탐색(Breadth First Search): 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식 두 개의 큐를 사용한다. root와 가까운 node들부터 찾기 때문에 최단거리를 탐색할 때 유용하다. queue에 각 노드의 정보를 기록해야 하기 때문에 메모리를 많이 잡아 먹는다. 찾고자 하는 target node가 root node와 가까이 있다고 예상될 경우 BFS를 사용한다. 지도 어플에서 특정 위치까지의 최단거리 안내, 혹은 소셜미디어에서 친구 추천 등에 이용된다. 깊이 우선 탐색(Depth First Search): 정점의 자식들을 먼저 탐색하..

패스트캠퍼스 코딩 테스트 강좌, 잔재미코딩 님의 수업을 참고했습니다. 이진 탐색(Binary Search) 탐색할 자료를 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법 무작위 정수가 담긴 배열에서 특정 정수를 찾아야 할 때, 해당 배열을 오름차순으로 정렬하고, 가운데 인덱스의 요소를 확인한다. 값이 찾고자 하는 값보다 크면 가운데 인덱스에서 끝 인덱스의 가운데 인덱스를 또 확인하고, 작으면 반대로 진행한다. [저작자] by penjee.com 이미지 출처 분할정복 알고리즘과 이진 탐색 분할 정복 Divide: 문제를 하나 혹은 둘 이상으로 나눈다. Conquer: 나눠진 문제가 충분히 작고 해결할 수 있다면 해결하고, 그렇지 않다면 다시 나눈다. 재귀 함수를 많이 사용한다. 이진 탐색 Divi..

패스트 캠퍼스 코딩테스느 강좌, 잔재미코딩 님의 수업을 참고했습니다. 순차 탐색 탐색: 여러 데이터 중에서 원하는 데이터를 찾아내는 것 순차 탐색: 데이터가 담겨 있는 배열을 앞에서부터 하나씩 비교하여 원하는 데이터를 찾는 방법 구현 const data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; // arr속에서 target을 찾는다. const sequencialSearch = (arr, target) => { for (let i = 0; i < arr.length; i++) { // 해당 값의 인덱스 return if (arr[i] == target) { return i; } } // arr 안에 target이 없다면 return -1; }; console.log(sequencia..

그리디 알고리즘 패스트 캠퍼스 코딩 테스트 강좌 내 잔재미코딩 님의 부분을 참고했습니다. 정의 Greedy algorithm 혹은 탐욕 알고리즘 최적의 해에 가까운 값을 구하기 위해 사용된다. 여러 경우 중 하나를 결정해야 할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구한다. 예제 1 지불해야하는 값이 4720원일 때, 1원, 50원, 100원, 500원 동전을 이용하여 지불하되, 가장 적은 수의 동전을 사용하시오. 접근 가장 가치가 큰 동전부터 사용해야 가장 적은 수의 동전을 사용하게 된다. // 사용 가능한 동전을 담은 배열 const coins = [1, 50, 100, 500]; // @params : cost - 지불해야할 금액 // @params : ..