본문 바로가기

All

 (73)
[인프런 코딩테스트] 이진트리(깊이 우선 탐색)로 부분집합 구하기, 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 함수 내에서 스스로를 호출한 것을 확인할 수 있다. ..
[Javascript] 배열 추가, 삭제, 수정 메서드 splice 코딩테스트를 준비하다 보니 메서드에 대해서 제대로 알고 있지 못하다는 생각이 들었다. 해당 메서드가 기존 배열을 수정하는지 안 하는지, 어떤 것을 리턴하는지 등을 정확하게 알고 있어야 코드를 클린 하게 짤 수 있을 거 같다. 따라서 앞으로 코테 문제에 사용했던 메서드들을 정리하려 한다. 첫 스타트는 splice! 1. splice array.splice(start[, deleteCount[, item1[, item2[, ...]]]]) splice는 배열의 기존 요소를 삭제 또는 교체 하거나 새 요소를 추가해서 배열의 내용을 변경하는 메서드이다. splice를 통해 배열을 수정하면, 기존 배열도 같이 변경된다. 1) start 배열 변경의 시작 인덱스를 입력한다. 입력된 인덱스부터 배열이 변경된다. 음수..
[인프런 코딩테스트] 뮤직비디오, 결정 알고리즘 (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
[Web] SSG, ISR의 개념과 차이점 1. SSG SSG는 Static Site Generation의 약자로, 정적인 웹사이트를 만들 때 사용한다. SSR과 똑같이 서버에서 렌더링 하지만 렌더링 되는 시기가 SSR과 다르다. SSG는 서버에 배포한 후, 빌드할 때 렌더링(html 코드로 변환됨)된다. 실제 html 파일들은 빌드할 때 미리 만들어 둔다고 생각하면 된다. 1) SSG Rendering 방식 서버에 배포 한 후 빌드시 렌더링이 일어나면서 html 파일이 생성된다. 이후 사용자가 홈페이지에 접속하면, 클라이언트가 서버에 요청을 보내고 서버는 만들어준 html 파일을 보내준다. 클라이언트는 받은 데이터를 통해 html을 표기해 준다. 2) 장점 ① 페이지 로딩 시간(Time To View)이 짧다 ② 자바스크립트 필요 없음 ③ SE..

티스토리툴바