요새 개발자를 채용할 때 알고리즘 테스트를 하는 기업이 늘고 있습니다.
알고리즘 테스트를 하는 이유는 '문제해결' 능력을 보려고 하는 것입니다.
그렇다면 알고리즘이란? 무엇인가?
알고리즘이란?
컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정이다
사전적으로는 컴퓨터가 문제를 해결할 수 있도록 하는 절차나 방법이라고 설명하고 있습니다.
산에 정상을 찍는 게 목표라고 생각했을 때
정상을 가기 위해서는 빨리 가는 길, 돌아가는 길, 그 밖에 여러 갈래의 길이 있을 수 있습니다.
여기에서 산을 쉽게 빨리 가는 방법을 찾는다면 그게 빠른 길로 가는 알고리즘이라고 이해하시면 될 거 같습니다.
여러 알고리즘이 있지만, 만약에 본인이 더 좋은 알고리즘을 찾는다면 그 찾은 사람의 알고리즘이 될 수 도 있겠네요.
반응형
알고리즘 종류와 예시
이진 탐색(Binary Search):
- 정렬된 배열에서 특정 요소를 찾는 알고리즘입니다.
- 배열의 중간 요소와 찾고자 하는 값 비교 후 탐색 범위를 절반으로 줄여가며 반복합니다.
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 찾고자 하는 값이 배열에 없을 경우
}
const array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(binarySearch(array, 6)); // 출력: 5 (요소 6의 인덱스)
퀵 정렬(Quick Sort):
- 분할 정복(Divide and Conquer) 기법을 사용하여 배열을 정렬하는 알고리즘입니다.
- 배열을 피벗(pivot)을 기준으로 두 개의 부분 배열로 분할하고, 재귀적으로 각 부분 배열을 정렬합니다.
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const array = [5, 2, 9, 1, 8, 6];
console.log(quickSort(array)); // 출력: [1, 2, 5, 6, 8, 9]
깊이 우선 탐색(DFS, Depth-First Search):
- 그래프 탐색 알고리즘 중 하나로, 한 정점에서 시작하여 해당 정점과 인접한 정점을 재귀적으로 탐색합니다.
- 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있습니다.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
dfsRecursive(startVertex) {
const visited = {};
const result = [];
const adjacencyList = this.adjacencyList;
function dfs(vertex) {
if (!vertex) {
return null;
}
visited[vertex] = true;
result.push(vertex);
adjacencyList[vertex].forEach(neighbor => {
if (!visited[neighbor]) {
return dfs(neighbor);
}
});
}
dfs(startVertex);
return result;
}
}
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'D');
console.log(graph.dfsRecursive('A')); // 출력: ['A', 'B', 'C', 'D']
너비 우선 탐색(BFS, Breadth-First Search):
- 그래프 탐색 알고리즘으로, 한 정점에서 시작하여 해당 정점과 인접한 모든 정점을 탐색한 후, 다음 단계의 인접한 정점들을 탐색합니다.
- 큐(Queue)를 사용하여 구현할 수 있습니다.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
bfs(startVertex) {
const visited = {};
const result = [];
const queue = [startVertex];
visited[startVertex] = true;
while (queue.length > 0) {
const currentVertex = queue.shift();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return result;
}
}
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'D');
console.log(graph.bfs('A')); // 출력: ['A', 'B', 'C', 'D']
선택 정렬(Selection Sort):
- 배열에서 최솟값을 선택하여 정렬되지 않은 부분 배열의 첫 번째 요소와 교환하는 정렬 알고리즘입니다.
- 정렬되지 않은 부분 배열을 반복하면서 가장 작은 요소를 선택하고, 해당 요소를 정렬된 부분 배열의 마지막 요소와 교환합니다.
function selectionSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
const array = [5, 2, 9, 1, 8, 6];
console.log(selectionSort(array)); // 출력: [1, 2, 5, 6, 8, 9]
최단 경로 탐색(Dijkstra's Algorithm):
- 가중치 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘입니다.
- 시작 정점에서부터 다른 모든 정점까지의 최단 거리를 계산합니다.
- 우선순위 큐(Priority Queue)를 사용하여 구현할 수 있습니다.
class Graph {
constructor() {
this.vertices = [];
this.edges = {};
}
addVertex(vertex) {
this.vertices.push(vertex);
this.edges[vertex] = {};
}
addEdge(vertex1, vertex2, weight) {
this.edges[vertex1][vertex2] = weight;
this.edges[vertex2][vertex1] = weight;
}
dijkstra(startVertex) {
const distances = {};
const visited = {};
const previous = {};
const queue = new PriorityQueue();
this.vertices.forEach(vertex => {
distances[vertex] = Infinity;
previous[vertex] = null;
});
distances[startVertex] = 0;
queue.enqueue(startVertex, 0);
while (!queue.isEmpty()) {
const currentVertex = queue.dequeue().element;
visited[currentVertex] = true;
for (let neighbor in this.edges[currentVertex]) {
const weight = this.edges[currentVertex][neighbor];
const totalDistance = distances[currentVertex] + weight;
if (totalDistance < distances[neighbor]) {
distances[neighbor] = totalDistance;
previous[neighbor] = currentVertex;
if (!visited[neighbor]) {
queue.enqueue(neighbor, totalDistance);
}
}
}
}
return {
distances,
previous
};
}
}
class PriorityQueue {
constructor() {
this.items = [];
}
enqueue(element, priority) {
const queueElement = {
element,
priority
};
let added = false;
for (let i = 0; i < this.items.length; i++) {
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}
if (!added) {
this.items.push(queueElement);
}
}
dequeue() {
return this.items.shift();
}
isEmpty() {
return this.items.length === 0;
}
}
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'E', 1);
graph.addEdge('D', 'E', 3);
console.log(graph.dijkstra('A')); // 출력: { distances: { A: 0, B: 4, C: 2, D: 4, E: 3 }, previous: { A: null, B: 'A', C: 'A', D: 'C', E: 'C' } }
요즘에는 큰 기업에서 채용할 때 알고리즘 테스트를 하기 때문에 이해를 하기보단 수능 예상 문제집처럼 외우고 가는 경우도 많다고 합니다. 그래서 신입이 경력자 보다 알고리즘을 더 잘 알 수도 있지만, 그렇다고 알고리즘을 모르는 경력자들이 업무 대처 능력과 개발 능력이 떨어진다고 생각하진 않습니다.
이미 경력자들은 본인만의 알고리즘을 가지고 있을 수 있으니깐요. 그리고 알고리즘과 연봉이 정비례하진 않습니다.
물론 다양한 알고리즘을 아는 것이 이점이 많고, 기본기와 장기적으로 봤을 때는 유리하다고는 생각합니다.
외운다기보다 이해를 하는게 포인트라고 봅니다.
아래는 코딩 테스트를 할 수 있는 사이트입니다.
난이도 별로 문제가 주어지는데 참 어렵네요 ㅎㅎ
https://school.programmers.co.kr/learn/challenges?order=recent&page=1&languages=javascript
코딩테스트 연습 | 프로그래머스 스쿨
개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!
school.programmers.co.kr
알고리즘은 여러 개발 언어에서 사용되고 비슷하다고 하니, 참고하시면 될듯합니다.
728x90
