프로그래머스 코딩테스트 고득점 Kit H-Index​

문제 설명​

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

프로그래머스 코딩테스트 고득점 Kit 정렬 가장 큰 수​

문제 설명​

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

정렬을 배우면 쉬워지는 문제들​

• 배열 A에서 특정 값 v를 검색
• (정적) 배열 A 에서 최소/최대 또는 k번째 최소/최대 값 찾기
• 배열 A에서 고유성 테스트 및 중복 삭제
• 특정 값 v가 배열 A에 나타나는 횟수 세기
• 배열 A와 다른 정렬된 배열 B 사이에 교집합/합집합을 설정
• $x+y$가 목표 $z$와 같 도록 목표 쌍 $x ∈ A$ 및 $y �∈ A$ 찾기

프로그래머스 코딩테스트 고득점 Kit 이분탐색 입국심사​

문제 설명​

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

BFS(Bread-First Search) 너비 우선 탐색​

• 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
• Queue를 이용하여 구현
• 시작 지점에서 가까운 정점부터 탐색
• $V$가 정점의 수, $E$가 간선의 수 일 떄 BFS의 시간복잡도는 $O(V + E)$다.

그리디​

• 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘
• 최적해를 보장해주지 않는다.
• 보통 최적해를 구하는 알고리즘 보다 빠른 경우가 많다.
• 크루스칼, 다익스트라 알고리즘 등에 사용
• 직관적인 문제 풀이에 적합
• 예) 동전(거스름돈) 반환 문제

선형 탐색​

• 순서대로 하나씩 찾는 탐색 알고리즘
• $O(N)$ 시간 복잡도가 걸린다.

이진 탐색​

• 정렬이 되어있는 요소들을 반씩 제외하며 찾는 알고리즘
• $O(logN)$ 시간 복잡도가 걸린다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.

트라이​

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 검색어 자동완성, 사전 찾기 등에 응용될 수 있다.
• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
• $L$이 문자열의 길이일 때 탐색, 삽입은 $O(L)$만큼 걸린다.
• 각 정점이 자식에 대한 링크를 전부 가지고 있어 저장 공간을 더 많이 사용

우선순위 큐​

• FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐
• 우선순위 큐는 자료구조가 아닌 개념
• 힙은 우선순위를 구현하기 위한 가장 적합한 방법

트리​

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 $N$개인 트리는 반드시 $N-1$개의 간선을 가진다.
• 루트에서 특정 정점으로 가는 경로는 유일하다.

1. 인접 배열​

// 5 X 5 false 배열 생성
const graph = Array.from(Array(5), () => Array(5).fill(false));
console.log(graph);
// graph[출발지][목적지] 해당 부분을 true로 설정
graph[0][1] = true;
graph[0][3] = true;
graph[1][2] = true;
graph[2][0] = true;
graph[2][4] = true;
graph[3][2] = true;
graph[4][0] = true;
console.log(graph);

Hashing(해싱)​

• 임의의 길이를 가진 값을 해시 함수를 사용해 고정된 크기의 값으로 변환하는 작업

해시 테이블​

• 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
• 삽입은 $O(1)$이며 키를 알고 있다면 삭제, 탐색도 $O(1)$로 수행

1. Array로 큐를 구현​

• 단점
  • DeQueue를 하면 배열 앞부분이 공백이 된다.
  • 배열에서 리얼 인덱스 값이 무한정 커질 수 있다.

1. Array를 스택처럼 사용​

const stack = [];

// Push
stack.push(x);

// Pop
stack.pop();

1. Array 특징​

• 동적이라 const로 선언해도 줄었다가 늘었다가 가능하다.

2. Array 생성​

A. 선언​

const array = [];
const array = [1, 2, 3, 4, 5];

방명록​

방명록 또는 게스트북(guestbook)은 방문객이 어느 지역에 방문한 것을 인지시키고 자신의 이름, 주소, 의견 등을 남기기 위한 종이 또는 전자 수단이다. (중략) 웹상에서 방명록은 웹사이트의 방문객들이 공개 댓글을 남길 수 있게 하는 기록 시스템이다. 일부 방명록의 경우 방문객들은 웹사이트나 웹사이트 주제에 관하여 자신의 생각을 표현하는 것이 가능하다.