CS/알고리즘
[코테 대비] JavaScript로 코딩테스트 보기 - 심화
일 월
2025. 4. 30. 11:10
기본 문법에 관련된 글은 아래 링크에!
[코테 대비] JavaScript로 코딩테스트 보기 - 기본
보통 Python으로 알고리즘을 준비하는데, 사용 가능 언어에 Python이 없는 코테가 있다. JavaScript로 코딩 테스트를 보려고 할 때, 참고하면 좋을 내용을 적어보려고 한다.빠르게 익히는 것을 목표로
ilwol-developer.tistory.com
5. 주요 알고리즘
5-1. 정렬
// 배열 정렬 - sort 메소드 이용
// 오름차순 정렬 (sort 안의 인자 생략하면 유니코드 순서에 따라 정렬)
const months = ["March", "Jan", "Feb", "Dec"]
months.sort() // ["Dec", "Feb", "Jan", "March"]
const array1 = [1, 30, 4, 21, 100000]
array1.sort() // [1, 100000, 21, 30, 4]
// 정렬 기준 설정 - 오름차순
const numbers = [4, 2, 5, 1, 3]
numbers.sort(function (a, b) {
return a - b;
});
console.log(numbers) // [1, 2, 3, 4, 5]
// map 이용해 정렬 기준 설정
const list = ["Delta", "alpha", "CHARLIE", "bravo"];
const mapped = list.map(function (el, i) {
return { index: i, value: el.toLowerCase() };
});
mapped.sort(function (a, b) {
return +(a.value > b.value) || +(a.value === b.value) - 1;
});
const result = mapped.map(function (el) {
return list[el.index];
});
// 객체 특정 속성으로 정렬
const items = [
{ name: "Edward", value: 21 },
{ name: "Sharpe", value: 37 },
{ name: "And", value: 45 },
{ name: "The", value: -12 },
{ name: "Magnetic", value: 13 },
{ name: "Zeros", value: 37 },
];
// value 기준으로 정렬
items.sort(function (a, b) {
if (a.value > b.value) {
return 1;
}
if (a.value < b.value) {
return -1;
}
// a must be equal to b
return 0;
});
// name 기준으로 정렬
items.sort(function (a, b) {
const nameA = a.name.toUpperCase(); // ignore upper and lowercase
const nameB = b.name.toUpperCase(); // ignore upper and lowercase
if (nameA < nameB) {
return -1;
}
if (nameA > nameB) {
return 1;
}
// 이름이 같을 경우
return 0;
});5-2. 스택
- 직접 구현해야 함
- 구현하지 않고 배열 이용해도 무방
5-3. 큐
- 직접 구현해야 함
- 기본 배열을 사용할 때는 값을 삭제할 때 시간이 많이 걸림
// 객체를 이용한 큐 구현
class Queue {
constructor() {
this.storage = {}; // 값을 저장할 객체
this.front = 0; // 첫 원소를 가리킬 포인터
this.rear = 0; // 마지막 원소를 가리킬 포인터
}
// 크기 구하기
size() {
// rear가 가리키는 값이 없을 때가 아무 데이터가 없는 경우
if (this.storage[rear] === undefined) {
return 0;
} else {
// 그 외의 경우
return this.rear - this.front + 1;
}
}
add(value) {
// 큐에 데이터가 아무것도 없는 경우
if (this.size() === 0) {
this.storage['0'] = value;
} else {
// 그 외의 경우 - rear 위치를 1만큼 늘리고 해당 위치에 값 삽입
this.rear += 1;
this.storage[this.rear] = value;
}
}
popleft() {
let temp; // 첫 원소 값을 임시로 담을 변수
// 두 포인터의 값이 같은 경우 (데이터가 1개 남은 경우) - 호환성 높은 코드를 위해
if (this.front === this.rear) {
// 현재 front에 담긴 값을 가져오고 이 값을 delete
temp = this.storage[this.front];
delete this.storage[this.front];
// 데이터가 없는 경우 0으로 초기화
this.front = 0;
this.rear = 0;
} else {
// 현재 front에 담긴 값을 가져오고 이 값을 delete 해주어야 한다
temp = this.storage[this.front];
delete this.storage[this.front];
this.front += 1;
}
return temp;
}
}5-4. 우선순위 큐, 힙
- 직접 구현해야 함
// 최소힙
class PriorityQueue {
constructor() {
this.heap = [];
}
size() {
return this.heap.length
}
isEmpty() {
return this.heap.length === 0
}
heapifyUp() {
let i = this.size() - 1;
const lastNode = this.heap[i];
while(i > 0) {
const parentIndex = Math.floor((i - 1) / 2);
if (this.heap[parentIndex] > lastNode) {
this.heap[i] = this.heap[parentIndex];
i = parentIndex;
} else {
break;
}
}
this.heap[i] = lastNode
}
enqueue(value) {
this.heap.push(value);
this.heapifyUp();
}
dequeue() {
if (this.isEmpty()) return null;
const rootNode = this.heap[0];
const lastNode = this.heap.pop();
this.heap[0] = lastNode;
this.heapifyDown();
return rootNode;
}
heapifyDown() {
let i = 0;
const rootNode = this.heap[i];
const heapSize = this.size();
let swapIndex;
while(i > 0) {
let leftChildIndex = i * 2 + 1;
let rightChildIndex = (i * 2) + 2;
// 왼쪽 자식 인덱스가 범위 안에 있고,
if (leftChildIndex < heapSize) {
// 대상이 왼쪽 자식보다 크다면, 왼쪽 자식 인덱스를 바꿔야할 인덱스로 지정
if (this.heap[leftChildIndex] < this.heap[i]) {
swapIndex = leftChildIndex
}
}
// 오른쪽 자식 인덱스가 범위 안에 있고,
if (rightChildIndex < heapSize) {
if (
// 바꿔야할 인덱스가 지정된 값이 없고, 대상이 오른쪽 자식보다 크거나
(swapIndex === null && this.heap[rightChildIndex] < this.heap[i]) ||
// 바꿔야할 인덱스가 왼쪽으로 지정되어 있지만, 왼쪽 자식이 오른쪽 자식보다 크다면
(swapIndex !== null && this.heap[rightChildIndex] < this.heap[leftChildIndex])
) {
// 바꿔야할 인덱스로 오른쪽 자식 인덱스를 지정한다.
swapIndex = rightChildIndex;
}
}
// 바꿔야할 인덱스가 없다면 반복문 종료
if (swapIndex === null) break;
// 바꿔야할 인덱스와 대상의 위치를 바꿔준다.
[this.heap[i], this.heap[swapIndex]] = [this.heap[swapIndex], this.heap[i]];
i = swapIndex;
}
}
}
// 최대힙
class MaxHeap {
constructor() {
this.heap = [null];
}
heap_push(value) {
// 아래에서 위로
this.heap.push(value);
let currentIndex = this.heap.length - 1;
let parentIndex = Math.floor(currentIndex / 2);
while (parentIndex !== 0 && this.heap[parentIndex] < value) {
const temp = this.heap[parentIndex];
this.heap[parentIndex] = this.heap[currentIndex];
this.heap[currentIndex] = temp;
currentIndex = parentIndex;
parentIndex = Math.floor(currentIndex / 2);
}
}
heap_pop() {
if (this.heap.length === 2) return this.heap.pop(); // 루트 정점만 남은 경우
// 위에서 아래로
let returnValue = this.heap[1];
this.heap[1] = this.heap.pop();
let currentIndex = 1;
let leftIndex = 2;
let rightIndex = 3;
while (
this.heap[currentIndex] < this.heap[leftIndex] ||
this.heap[currentIndex] < this.heap[rightIndex]
) {
const temp = this.heap[currentIndex];
if (this.heap[leftIndex] < this.heap[rightIndex]) {
this.heap[currentIndex] = this.heap[rightIndex]
this.heap[rightIndex] = temp;
currentIndex = rightIndex;
} else {
this.heap[currentIndex] = this.heap[leftIndex]
this.heap[leftIndex] = temp;
currentIndex = leftIndex;
}
leftIndex = currentIndex * 2;
rightIndex = leftIndex + 1;
}
return returnValue;
}
heap_return() {
return this.heap;
}
}5-5. 트리
// 트리
class Tree {
constructor(value) {
// constructor로 만든 객체는 트리의 Node가 된다.
//tree의 자식 노드들을 children으로 할당하여 노드의 자식 노드들을 담을 수 있게 설정한다.
this.value = value;
this.children = [];
}
// 트리의 삽입 메서드.
//tree의 자식 노드를 생성 한 후에, 노드의 children에 push
insertNode(value) {
const childNode = new Tree(value);
this.children.push(childNode);
}
// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드.
// tree에서 value값을 탐색 -> 현재 노드의 value 값이 찾는 값과 일치한다면 return.
contains(value) {
if (this.value === value) {
return true;
}
// 노드가 가진 자식 노드를 순회하는 반복문으로 노드의 children 배열을 탐색
for (let i = 0; i < this.children.length; i++) {
const childNode = this.children[i];
if (childNode.contains(value)) {
return true;
}
}
// 전부 탐색했음에도 불구하고 찾지 못했다면 false return.
return false;
}
}
// 입출력
const rootNode = new Tree(null);
for(let i = 0; i <= 4; i++) {
if(rootNode.children[i]) {
rootNode.children[i].insertNode(i);
}
rootNode.insertNode(i);
}
rootNode; // {value: null, children: Array(5)}
rootNode.contains(5); // false
// BST
class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
}
class BST {
constructor() {
this.root = null;
}
add(data) {
const node = this.root;
if (node === null) {
this.root = new Node(data);
return;
} else {
const searchTree = function (node) {
if (data < node.data) {
if (node.left === null) {
node.left = new Node(data);
return;
} else if (node.left !== null) {
//left에 함수 있을 시 재귀 함수 적용
return searchTree(node.left);
}
} else if (data > node.data) {
if (node.right === null) {
node.right = new Node(data);
return;
} else if (node.right !== null) {
return searchTree(node.right);
}
} else {
return null;
}
};
return searchTree(node);
}
}
remove(data) {
//제거할 data의 파라미터를 두번째에 놓았다.
const removeNode = function (node, data) {
if (node == null) {
return null;
}
if (data == node.data) {
// node has no children ~ 밑에 뿌리가 없는 노드
if (node.left == null && node.right == null) {
return null;
}
// node has no left child ~ left는 없는 경우 node right가 해당 삭제 데이터에 들어간다.
if (node.left == null) {
return node.right;
}
// node has no right child
if (node.right == null) {
return node.left;
}
// node has two children
var tempNode = node.right;
//tempNode는 삭제할 node의 right가 되고
while (tempNode.left !== null) {
tempNode = tempNode.left; //다시 node right의 left가 된다.
}
node.data = tempNode.data; //그리고 삭제 node에는 위의 tempnode가 들어가게된다.
node.right = removeNode(node.right, tempNode.data);
return node;
} else if (data < node.data) {
node.left = removeNode(node.left, data);
return node;
} else {
node.right = removeNode(node.right, data);
return node;
}
}
this.root = removeNode(this.root, data);
}
}
const bst = new BST();
bst.add(9);5-6. dfs
// while문 이용 1
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'G', 'H', 'I'],
D: ['B', 'E', 'F'],
E: ['D'],
F: ['D'],
G: ['C'],
H: ['C'],
I: ['C', 'J'],
J: ['I']
};
const DFS = (graph, startNode) => {
const visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
visited.push(node);
needVisit = [...graph[node], ...needVisit];
}
}
return visited;
};
// while문 이용 2
function dfs(graph, start, visited) {
const stack = [];
stack.push(start);
while (stack.length) {
let v = stack.pop();
if (!visited[v]) {
console.log(v);
visited[v] = true;
for (let node of graph[v]) {
if (!visited[node]) {
stack.push(node);
}
}
}
}
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);
dfs(graph, 0, visited);
// 0 4 3 2 5 1
// 재귀 이용
const dfs = (graph, v, visited) => {
// 현재 노드를 방문 처리
visited[v] = true;
console.log(v);
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (let node of graph[v]) {
if (!visited[node]) {
dfs(graph, node, visited);
}
}
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);
dfs(graph, 0, visited);5-7. bfs
function BFS(graph, start, visited) {
const queue = new Queue();
queue.push(start);
visited[start] = true;
while (queue.size()) {
const v = queue.popleft();
console.log(v);
for (const node of graph[v]) {
if (!visited[node]) {
queue.push(node);
visited[node] = true;
}
}
}
}6. 문제 풀기
- 프로그래머스/백준 쉬운 문제부터 풀기 시작해서 변수 선언, 타입 등에 익숙해지면 구현, 빈출 알고리즘 문제를 푸는 방식으로 진행했다.
- 기업마다 코딩테스트를 담당하는 곳(프로그래머스, 구름, 잡다 등)이 다르고 문제 유형도 조금씩 다르니, 해당하는 곳에서 문제를 미리 풀어보는 것을 추천한다.
참고
최소 힙 - https://dr-dev.tistory.com/26
최대 힙 - https://velog.io/@qltkd5959/JS
정렬 - https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
BST - https://velog.io/@kimkevin90/Javascript%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-tree-%EA%B5%AC%ED%98%84
트리 - https://velog.io/@ko9612/JavaScript-Tree
dfs, bfs - https://velog.io/@lovesyung/Algorithm-DFS-BFS-Feat.-JS