Algorithm (25) 썸네일형 리스트형 [인프런 코딩테스트] 이진트리(깊이 우선 탐색)로 부분집합 구하기, DFS 1. 문제 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 단, 공집합은 출력하지 않습니다. 1) 부분집합과 공집합 우선 문제를 풀기 전에, 부분집합에 대해서 알아보자. 부분집합은 한 집합의 일부를 나타내는 것으로, 집합 A의 모든 원소가 집합 B에 포함될 때 A를 B의 부분 집합이라고 한다. 공집합은 원소를 하나도 가지고 있지 않은 집합으로, 부분집합에 포함된다. 만일 { 1, 2, 3 }이라는 집합이 있다고 해보자. 이때 부분집합을 구하기 위해서는 각 원소들이 집합에 포함되는지 확인해야 한다. 1이 포함되는 경우와 그렇지 않은 경우, 2가 포함되는 경우와 그렇지 않은 경우, 3이 포함되는 경우와 그렇지 않은 경우. 이를 트리로 표현하면 위와 같.. [Algorithm] 깊이우선탐색 알고리즘 (DFS, Depth First Search Algorithm) 1. 깊이우선탐색(DFS, Depth First Search) 깊이 우선 탐색은 트리나 그래프를 탐색하는 방법 중 하나로, 깊이를 우선으로 하여 시작노드에서 자식노드까지 순서대로 탐색하는 알고리즘을 말한다. 부분집합, 미로 풀기, 그래프에서 연결된 구성 요소 찾기, 퍼즐 풀기 등에서 사용된다. 재귀함수와 스택으로 비교적 쉽게 구현할 수 있으며, 후에 배울 BFS에 비해 메모리를 덜 사용한다. 그러나 재귀함수와 스택 자료구조를 사용하기 때문에 스택을 적절하게 관리하지 않으면, stack overflow로 이어질 수 있다. 또한 항상 최적의 솔루션을 찾는 것은 아니다. * 트리구조 동그란 부분을 노드(node)라고 한다. * 스택 오버플로우(stack overflow) 지정한 스택 메모리 사이즈보다 더 많은.. [프로그래머스] 0v, 최빈값 구하기 1. 문제 최빈값은 주어진 값 중에서 가장 자주 나오는 값을 의미합니다. 정수 배열 array가 매개변수로 주어질 때, 최빈값을 return 하도록 solution 함수를 완성해 보세요. 최빈값이 여러 개면 -1을 return 합니다. 1) 내 코드 function solution(array) { let obj = {}; //겹치는 숫자 count array.forEach(num => { if(obj[num] === undefined) obj[num] = 1 else obj[num] = obj[num]+1 }) let max = Math.max.apply(null, Object.values(obj)); let maxAll = Object.keys(obj).filter(key => obj[key] === .. [Algorithm] 재귀함수 개념과 동작방식 1. 재귀함수 재귀함수는 자기 자신을 호출하는 함수를 말한다. 반복문을 조금 더 간결한 코드로 풀어낼 때 사용한다. 스스로를 호출하는 함수이기 때문에 반드시 종료조건을 써줘야 하며, 무한루프 되지 않도록 주의해야 한다. 1) 재귀함수 구현(자바스크립트) 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지 출력하는 프로그램을 작성하세요. function solution(n){ function DFS(L){ if(L === 0) return; else { DFS(L-1); conosle.log(L); } } } //1, 2, 3 자바스크립트에서 재귀함수를 구현하는 방법은 간단하다. 자기 자신을 호출하는 함수를 사용하면 된다. 위 예시를 살펴보면 DFS 함수 내에서 스스로를 호출한 것을 확인할 수 있다. .. [인프런 코딩테스트] 뮤직비디오, 결정 알고리즘 (feat. 이분탐색 응용, javascript) 1. 문제 지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필 씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안 된다. 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그.. [인프런 코딩테스트] 마구간 정하기, 결정 알고리즘 (feat. 이분탐색 응용, javascript) 1. 문제 N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마 구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요. 첫 줄에 자연수 N(3 [Algorithm] 이진탐색 알고리즘 (Binary Search Algorithm) 1. 이진탐색(Binary Search) 이분탐색이라고도 불리는 이진탐색 알고리즘은, 정렬된 배열 내에서 대상 값의 위치를 찾는 검색 알고리즘이다. 대상 값을 배열의 중간 요소와 비교한 후, 동일하지 않으면 절반을 제거하고 이를 성공할 때까지 반복한다. 정렬된 배열을 앞에서부터 하나하나 순차적으로 탐색하는 것을 순차탐색이라 하는데, 이러한 순차탐색보다 좀 더 빠르게 위치를 찾을 수 있다. 이진탐색의 시간복잡도는 O(log(n))이다. (순차탐색의 시간복잡도는 O(n)) 2. 이진탐색 구현 function solution(target, arr) { let answer; arr.sort((a, b) => a - b); //인덱스번호 let lt = 0, rt = arr.length - 1; while (lt.. [Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 1. 탐욕 알고리즘(Greedy Algorithm) 탐욕 알고리즘은 선택의 순간마다 그 이후를 고려하지 않고, 현 시점에서 가장 최적인 방법을 선택하는 알고리즘을 말한다. 순간마다 최적인 방법을 선택하기 때문에 항상 최적의 결과값을 배출하진 않는다. 그러나 다른 알고리즘보다 평균적으로 속도가 빠르고, 어느 정도 최적에 근사한 답을 알려준다. 2. 문제 : 회의실 배정 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작.. 이전 1 2 3 4 다음
