분류 전체보기
-
트라이Data Structure & Algorithm 2022. 4. 4. 20:51
정의 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 특징 검색어 자동완성, 사천 찾기 등에 응용 가능 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 탐색 가능 L 이 문자열의 길이일 때 탐색, 삽입 시 O(L) 만큼 시간 소요 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용 규칙 루트는 비어 있음(공백) 각 간선(링크)은 추가될 문자를 키로 가짐 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가짐 해시 테이블과 연결 리스트를 이용하여 구현 가능
-
BFS, DFSData Structure & Algorithm 2022. 3. 29. 21:02
BFS 정의 Breadth-First Search 의 약자로 너비 우선 탐색 알고리즘을 뜻함 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 특징 Queue 를 이용하여 구현 가능 시작 지점에서 가까운 정점부터 탐색 V 가 정점의 수, E 가 간선의 수일 때 BFS 의 시간복잡도는 O(V + E) DFS 정의 Depth-First Search 의 약자로 깊이 우선 탐색 알고리즘을 뜻함 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘 특징 Stack 을 이용하여 구현 시작 정점에서 깊은 것부터 탐색 V 가 정점의 수, E 가 간선의 수일 때 DFS 의 시간복잡도는 O(V + E)
-
이중우선순위큐Coding Test/Programmers Level 3 2022. 3. 29. 20:49
문제 https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 코드 function solution(operations) { const answer = []; for(let i = 0; i Number(b) - Number(a)); } if(command === 'D'){ if(num === '1') answer.shift(); else a..
-
기능개발Coding Test/Programmers Level 2 2022. 3. 29. 00:58
문제 https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 코드 function solution(progresses, speeds) { var answer = []; while(progresses.length !== 0){ progresses.forEach((v, i, arr) => arr[i] = v + speeds[i]); let hasCompleted = true; let count = 0; while..
-
힙Data Structure & Algorithm 2022. 3. 27. 22:06
정의 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있음 특징 우선순위가 높은 요소가 먼저 나가는 특징을 가짐 => 우선순위가 높은 요소를 루트로 배치하고 루트가 가장 먼저 나감 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있음 => 오름차순/내림차순 차이 자바스크립트에선 직접 구현해서 사용해야 함 힙은 추가/삭제가 핵심 로 우선순위 큐와 비슷하지만 우선순위 큐는 큐를 활용한 개념이기 때문에 같은 것은 아니며 힙이 우선순위 큐보다 효율성이 높은 편 힙 요소 추가 알고리즘 요소가 추가될 때는 트리의 가장 마지막에 추가 추가된 요소가 부모 정점보다 우선순위가 높다면 부모 정점..
-
트리Data Structure & Algorithm 2022. 3. 27. 21:44
정의 방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 자료 구조 용어 Root: 가장 상위의 정점 Node: 각 정점 Leaf Node: 자식이 없는 노드 Level: Root 부터 몇 번째 깊이(단계)에 위치해 있는 지 표시 Degree: 한 정점에서 뻗어 나가는 간선의 수 특징 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가짐 정점이 N 개인 트리는 반드시 N-1 개의 간선을 가짐 루트에서 특정 정점으로 가는 경로는 유일함 실생활 예: 조직도, 디렉토리 구조 이진 트리 각 정점이 최대 2개의 자식을 갖는 트리 완전 이진 트리: 마지막 레벨을 제외하고 모든 정점이 채워져 있는 트리 포화 이진 트리: 마지막 레벨까지 모두 채워져 있는 트리 편향 트리: 한 방향으로만 정점이 이어..
-
그래프Data Structure & Algorithm 2022. 3. 27. 21:31
정의 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조 특징 정점 집합과 간선 집합으로 표현 가능 정점은 Node, 간선은 Edge 라고도 함 정점은 여러 개의 간선을 가질 수 있음 선형 구조는 앞 뒤로 하나의 요소만 가질 수 있음 방향 그래프와 무방향 그래프로 나눌 수 있음 간선은 가중치를 가질 수 있음 사이클이 발생할 수 있음 탐색 시 무한 루프에 빠지지 않도록 하는 것에 주의 인물 관계도로 비유 가능하며 지하철 노선도, 페이지랭크 등에 사용 간선 방향성에 따른 분류 무방향 그래프 간선으로 이어진 정점끼리 양방향으로 이동 가능 (A, B) 와 (B, A) 는 같은 간선으로 취급 ex) 양방향 통행 도로 방향 그래프 간선에 방향성이 존재하는 그래프 와 간선을 통해 양방향으로 갈 수 있더라도..
-
베스트 앨범Coding Test/Programmers Level 3 2022. 3. 27. 17:25
문제 https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 코드 function solution(genres, plays) { const bestAlbum = []; const nominated = genres.reduce((result, genre, index) => { if(!result[genre]) result[genre] = {}; const beforeGenreCount = result[genre]["..