JavaScript를 사용해 알고리즘을 학습하고 코딩 테스트를 준비하는 공간입니다.
모의고사괄호 회전하기두 개의 수로 특정 값 만들기베스트앨범다단계 칫솔 판매미로 탈출 (방식은 맞았는데 한 번더)양과 늑대 (생전 처음 보는 BFS 문제 뇌의 확장!)길 찾기 게임 (잘 풀었음. 근데 구현 방식만, 배열 or 포인터 좀 더 다듬자)간단한 유니온-파인드 알고리즘 구현하기 (경로 압축만)주식 가격섬 연결하기벨만-포드 알고리즘네트워크 (풀긴 했는데 DFS 로 풀지 않음)1부터 N까지 숫자 중 합이 10이 되는 조합 구하기 (좀만 더 숙달)카펫땅따먹기 (풀었지만 다시!)구명보트 (.......... 점점점점점) 문제를 잘 읽읍시다..우선 순위 큐 구현 (복습)- [다시]
표 편집 - [다시]
메뉴 리뉴얼 - [다시]
다익스트라 알고리즘 - [이거는 BFS랑 dp 섞은 문제임]
경주로 건설 (마지막 아이디어만 ... 생각할 수 있다면 ...) - [새로운 풀이 복습]
피로도 (너무 좋아서 다시 풀기) - [문제를 잘 읽자, 찐막]
양궁 대회 (후.. 저번에도 풀었었지만) - [다시, 구현만 제대로하면 됨, 아이디어는 굳]
외벽 점검 (반복해야됨) - [다시, DFS로 풀어보셈]
달팽이 수열 만들기 - [다시, 그냥 외워버려]
가장 큰 수 (오호) - [다시]
가장 큰 정사작형 찾기 (생각 확장) - [다시]
LCS 길이 계산하기 - [다시]
LIS 길이 계산하기 (풀었지만 다시) 우선 순위 큐 구현 (복습)- [다시]
스도쿠 퍼즐 (호오) (내일 더 개선, 어떻게 백트래킹 구현할지 감이 안왔음) - [백트래킹은 모아서 다시 풀어보자]
N-퀸 (호오,,,) - [다시]
사라지는 발판 (완벽하게 이해못함... 어렵) - [다시]
지형 이동 (막혀도 몰입해서 끝까지 풀기) - [다시]
배열 회전하기 (공식) - [다시]
롤케이크 자르기 (호오..) - [다시]
도둑질 (어려움) - [다시]
기지국 설치 (음.. 나한텐 어려웠음)
일반적인 CPU 기반의 PC는 1초에 실행할 수 있는 최대 연산 횟수는 약 100,000,000번
| 시간 복잡도 | 최대 연산 횟수 |
|---|---|
| O(n) | 약 1억번 |
| O(n^2) | 약 1만번 |
| O(n^3) | 약 500번 |
| O(2^n) | 약 20번 |
| O(n!) | 10번 |
- 의사 코드 작성(동작 위주)
- 동작을 작게 쪼기는 연습(바텀업)
- 나만의 테스트 케이스 추가(구체적인 예시 찾기 단계)
- 기록하기(문제를 풀면서 생각했던 것들)
- 핵심 키워드 파악 및 정리
서로 다른 n개의 요소에서 순서와 상관없이 r개를 택한다. nCr
입력: [1,2,3,4], 3
출력: [ [1,2,3], [1,2,4], [1,3,4], [2,3,4] ]
/**
* 조합(flatMap 버전)
*
* @param {*} arr
* @param {*} selectNumber
* @returns 조합
*/
const getCombinationsV2 = (arr, selectNumber) => {
if (selectNumber === 1) return arr.map((value) => [value]);
return arr.flatMap((fixed, index) => {
const rest = arr.slice(index + 1);
return getCombinationsV2(rest, selectNumber - 1).map((comb) => [
fixed,
...comb,
]);
});
};
console.log(getCombinationsV2([1, 2, 3, 4], 3));
/**
* 중복 조합
*
* @param {*} arr
* @param {*} selectNumber
* @returns 조합 + [1,1], [2,2], [3,3]
*/
const getCombinationsWithRepetition = (arr, selectNumber) => {
if (selectNumber === 1) return arr.map((value) => [value]);
return arr.flatMap((fixed, index) => {
// 전체 배열 중 fixed 미만 요소들을 제외한 나머지
const rest = arr.slice(index);
return getCombinationsWithRepetition(rest, selectNumber - 1).map((comb) => [
fixed,
...comb,
]);
});
};
console.log(getCombinationsWithRepetition([1, 2, 3, 4], 3));서로 다른 n개의 요소에서 순서를 고려하면서 r개를 택한다. nPr
[1,2] !== [2,1]
입력: [1,2,3], 2
출력: [ [1,2], [1,3], [2,1], [2,3], [3,1], [3,2] ]
/**
* 순열(flatMap 버전)
*
* flatMap은 arr.map(...args).flat()과 동일
* @param {*} arr
* @param {*} selectNumber
* @returns 순열
*/
const getPermutationsV2 = (arr, selectNumber) => {
if (selectNumber === 1) return arr.map((value) => [value]);
return arr.flatMap((fixed, index) => {
// 현재 요소를 제외한 나머지
const rest = [...arr.slice(0, index), ...arr.slice(index + 1)];
// 나머지 요소들로 순열을 만들고 현재 요소를 앞에 붙임
return getPermutationsV2(rest, selectNumber - 1).map((perm) => [
fixed,
...perm,
]);
});
};
console.log(getPermutationsV2([1, 2, 3, 4], 2));
/**
* 중복 순열
*
* @param {*} arr
* @param {*} selectNumber
* @returns 순열 + [1,1], [2,2], [3,3]
*/
const getPermutationsWithRepetition = (arr, selectNumber) => {
if (selectNumber === 1) return arr.map((value) => [value]);
return arr.flatMap((fixed) => {
return getPermutationsWithRepetition(arr, selectNumber - 1).map((perm) => [
fixed,
...perm,
]);
});
};
console.log(getPermutationsWithRepetition([1, 2, 3, 4], 3));- 인접 노드(1을 기준으로 [2,3])를 언제 방문할지 모르니 진입 시 방문 처리. 즉, 스택에 푸시할 노드는 방문 '예정'인 노드이므로 팝해서 방문 처리를 해야 함.
- 한 방향으로 깊이 들어가서 목표에 도달하거나 막히면 다시 돌아오는 방식을 사용하기 때문에 최단 경로를 보장할 수 없음. 최단 경로를 구할 수는 있지만 비효율적이라 사용하지 않음.
입력: { 1: [2,3], 2: [1,4,5], 3: [1], 4: [2], 5: [2] }, 1
출력: [ 1, 3, 2, 5, 4 ]
/**
* DFS(while)
*
* @param {*} graph
* @param {*} start
* @returns LIFO 특성 때문에 같은 레벨이면 마지막에 들어간 놈이 먼저 표시됨
*/
const dfsV1 = (graph, start) => {
const visited = new Set();
const stack = [start];
const result = [];
while (stack.length) {
const node = stack.pop();
if (!visited.has(node)) {
visited.add(node);
result.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
return result;
};
console.log(dfsV1(graph, start));입력: { 1: [2,3], 2: [1,4,5], 3: [1], 4: [2], 5: [2] }, 1
출력: [ 1, 2, 4, 5, 3 ]
/**
* DFS(재귀)
*
* @param {*} graph
* @param {*} start
* @returns 재귀 특성 때문에 먼저 진입한 놈이 먼저 표시됨
*/
const dfsV2 = (graph, start) => {
const result = [];
const visited = new Set();
const dfsHelper = (node) => {
if (visited.size === graph.length) return;
if (!visited.has(node)) {
visited.add(node);
result.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfsHelper(neighbor);
}
}
}
};
dfsHelper(start);
return result;
};
console.log(dfsV2(graph, start));- 큐에 푸시할 노드는 다음 방문할 노드이므로 바로 방문 처리, 스택과 다름.
- 레벨별 탐색을 통해 목표 지점에 처음 도달했을 때가 항상 최단 경로임을 보장되어 효율적임. 만약 가중치가 있다면 BFS는 더 이상 최소 비용을 보장하지 않음. 이럴 때는 다익스트라 같은 알고리즘을 사용해야 함.
입력: { 1: [2,3], 2: [1,4,5], 3: [1], 4: [2], 5: [2] }, 1
출력: [ 1, 2, 3, 4, 5 ]
/**
* BFS(while)
*
* @param {*} graph
* @param {*} start
* @returns
*/
const bfs = (graph, start) => {
const queue = [start];
const result = [];
const visited = new Set([start]);
while (queue.length) {
const node = queue.shift();
result.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
};
console.log(bfs(graph, start));배열 활용, O(1)
/**
* 배열을 활용한 스택
*
* 시간 복잡도 O(1)
*/
const stack = [];
stack.push(1);
stack.pop();
/**
* 단일 연결 리스트를 활용한 스택
*
* 시간 복잡도 O(1)
*/
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Stack {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
push(value) {
const node = new Node(value);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head = node;
}
this.size++;
}
// tail에서 pop하려면 양방향 연결 리스트로 구현해야 돼서 복잡해짐
pop() {
if (!this.head) return null;
const removed = this.head;
if (this.size === 1) this.head = this.tail = null;
else {
this.head = removed.next;
removed.next = null;
}
this.size--;
return removed.value;
}
}
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());배열 활용, O(n)
/**
* 배열을 활용한 큐
*
* 시간 복잡도 O(n)
*/
const queueV1 = [];
queueV1.push(1); // enqueue
queueV1.shift(); // dequeue배열 활용, O(1)
/**
* 배열을 활용한 큐
*
* 시간 복잡도 O(1)
*/
class QueueV2 {
constructor() {
this.item = [];
this.front = -1;
this.rear = -1;
}
enqueue(value) {
this.item.push(value);
this.rear++;
}
dequeue() {
if (this.isEmpty()) return null;
return this.item[++this.front];
}
isEmpty() {
return this.front === this.rear;
}
}
const queueV2 = new QueueV2();
queueV2.enqueue(1);
queueV2.enqueue(2);
queueV2.enqueue(3);
queueV2.enqueue(4);
console.log(queueV2.dequeue());
console.log(queueV2.dequeue());
console.log(queueV2.dequeue());
console.log(queueV2.dequeue());
console.log(queueV2.dequeue());단일 연결 리스트 활용, O(1)
/**
* 단일 연결 리스트를 활용한 큐
*
* 시간 복잡도 O(1)
*/
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class QueueV3 {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
enqueue(value) {
const node = new Node(value);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node; // 현재 tail의 next
this.tail = node; // 앞으로의 tail
}
return ++this.size;
}
dequeue() {
if (!this.head) return null;
const removed = this.head;
if (this.size === 1) this.head = this.tail = null;
else {
this.head = removed.next;
removed.next = null;
}
this.size--;
return removed.value;
}
}
const queueV3 = new QueueV3();
queueV3.enqueue(1);
queueV3.enqueue(2);
queueV3.enqueue(3);
queueV3.enqueue(4);
console.log(queueV3.dequeue());
console.log(queueV3.dequeue());
console.log(queueV3.dequeue());
console.log(queueV3.dequeue());
console.log(queueV3.dequeue());인접한 요소 쌍끼리 비교해 조건에 맞게 정렬하는 방법
- Inner Loop: 배열의 첫 번째 인덱스부터 차례대로 인접한 요소끼리 비교해 swap
- Outer Loop: 정렬된 요소를 제외하고 반복
const swap = (arr, i, j) => {
return ([arr[i], arr[j]] = [arr[j], arr[i]]);
};
/**
* 버블 정렬
*
* 최적화 x, 최악 O(n^2)
* @param {*} arr
* @returns
*/
const bubbleSortV1 = (arr) => {
// Outer Loop : 배열의 크기 - 1 만큼
for (let i = arr.length - 1; i > 0; i--) {
// Inner Loop : 인접한 요소끼리 비교 후 swap
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr;
};
console.log(bubbleSortV1([8, 3, 1, 5, 6, 7]));
/**
* 버블 정렬
*
* 최적화 o, 특정 조건에서 O(n)
* @param {*} arr
*/
const bubbleSortV2 = (arr) => {
for (let i = arr.length - 1; i > 0; i--) {
let noSwap = true;
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
noSwap = false;
}
}
// swap이 한 번도 이뤄지지 않았다면 종료
if (noSwap) break;
}
return arr;
};
console.log(bubbleSortV2([8, 3, 1, 5, 6, 7]));오름차순일 경우 가작 작은 요소를 찾아 배열의 처음부터 순서대로 쌓아가며 정렬하는 방법
- Inner Loop: 배열에서 가장 작은 값의 Index를 찾음
- Outer Loop: 정렬되지 않은 배열에서 가장 처음 요소와 minIdx값을 swap, 이 과정을 반복
const swap = (arr, i, j) => {
return ([arr[i], arr[j]] = [arr[j], arr[i]]);
};
/**
* 선택 정렬
*
* 최악 O(n^2)
* @param {*} arr
* @returns
*/
const selectionSort = (arr) => {
// Outer Loop : 배열의 크기 - 1 만큼
for (let i = 0; i < arr.length - 1; i++) {
let minIdx = i;
// Inner Loop: 가장 작은 값의 인덱스를 찾는다.
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx !== i) swap(arr, i, minIdx);
}
return arr;
};
console.log(selectionSort([8, 3, 1, 5, 6, 7]));배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 하나씩 적절한 위치에 삽입하면서 정렬하는 방법
- Inner Loop: 특정 요소를 정렬된 부분의 적절한 위치에 삽입
- Outer Loop: 이 과정을 반복
const swap = (arr, i, j) => {
return ([arr[i], arr[j]] = [arr[j], arr[i]]);
};
/**
* 삽입 정렬
*
* 최악 O(n^2)
* @param {*} arr
* @returns
*/
const insertionSortV1 = (arr) => {
// Outer Loop : 배열의 크기 - 1 만큼
for (let i = 1; i < arr.length; i++) {
// Inner loop : 2번째 요소부터 시작해 left side에 적절한 위치를 찾는다.
for (let j = i; j >= 0; j--) {
if (arr[j] < arr[j - 1]) swap(arr, j, j - 1);
else break;
}
}
return arr;
};
console.log(insertionSortV1([8, 3, 1, 5, 6, 7]));