자료구조와 알고리즘
-
[JS] 트라이자료구조와 알고리즘 2022. 8. 31. 11:16
검색의 자동완성 기능을 구현할 때 적합한 자료구조 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 특징 - 찾는 문자열의 길이만큼만 시간 복잡도가 걸린다. - 저장공간을 좀 더 많이 사용한다. 구조 루트는 비어있다. 각 간선은 추가될 문자를 키로 가진다. 각 정점은 이전 간선의 키를 값으로 가진다. 해시 테이블과 연결 리스트를 사용한다. 트리 생성하기 function makeTrie(words) { const root = {}; // 먼저 루트 노드를 설정할 변수를 만든다. for (const word of words) { // Trie를 구성하기 위한 루프를 돌린다. let current = root; // 루프부터 시작 for (const letter of word) { // 단어의 ..
-
[프로그래머스 JS] 베스트앨범자료구조와 알고리즘 2022. 8. 15. 17:55
문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.장르 내에서 많이 재생된 노래를 먼저 수록합니다.장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 제한 사항 genres[i]는 고유번호가 i인 노래의 장르입니다.plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다...
-
[프로그래머스 JS] 폰켓몬자료구조와 알고리즘 2022. 8. 12. 00:13
문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택첫 번째(3번), 세 번째(2번) 폰켓몬을 선택첫 번째..
-
[프로그래머스 JS] 같은 숫자는 싫어자료구조와 알고리즘 2022. 8. 10. 18:01
문제 설명 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면, arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다. 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요. 제한 사항 배열 arr의 크기 : 1,000,000 이하의 자연수 배열 arr의 원소의 크기 : 0보다 크거나 ..
-
[JS] 연결 리스트자료구조와 알고리즘 2022. 8. 9. 21:43
추가와 삭제가 반복된다면 연결 리스트를 사용하자 연결 리스트란? 각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다. 데이터 필드 = 데이터 영역 = 데이터 저장 링크 필드 = 포인터 영역 = 다른 노드의 주소 값을 저장 특징 메모리가 허용하는 한 요소를 제한 없이 추가할 수 있다. 배열과 차이점 1. 메모리 차이 배열은 순차적인 데이터, 즉 메모리 영역이 연속적으로 사용된다. 연결 리스트는 각 데이터가 퍼져있다. 즉, 포인터를 사용하여 각 영역을 참조한다. 2. 요소 삭제 / 추가 배열 배열은 O(n) 시간 소요 연결 리스트 삭제 1. 삭제하려고 하는 요소를 지정 2. 삭제하려고 하는 요소의 전 요소의 포인터를 삭제하려고 하는 요소..
-
[프로그래머스 JS] H-Index자료구조와 알고리즘 2022. 6. 17. 18:02
[프로그래머스 JS] 문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한 사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.논문별 인용 횟수는 0회 이상 10,000회 이하입니다. 내가 작성한 ..
-
[프로그래머스 JS] 가장 큰 수자료구조와 알고리즘 2022. 6. 17. 17:06
문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 numbers = [6, 10, 2] re..
-
[프로그래머스 JS] K번째수자료구조와 알고리즘 2022. 6. 17. 15:10
문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1 이상 100 이하입니다. a..