💻 컴퓨터공학
자바스크립트로 코딩 테스트 준비하기
자바스크립트로 코딩 테스트 준비하기
2022.02.22코딩 테스트 준비하기 이번 글은 나중에 코딩 테스트를 비롯한 문제 해결이 필요할 때 참고하려고 간단하게 작성했습니다. 개인적으로 정리한 글이지만, 프론트엔드 개발자에 지원하는 분들께 도움이 되었으면 좋겠습니다. 코드 설명이 필요한 분들은 댓글 달아주시면 최대한 빨리 답변드릴게요. 피드백도 환영합니다. 본문에 포함된 예제는 모두 자바스크립트 ES6 기준으로 작성했습니다. 탐욕 알고리즘 탐욕 알고리즘(Greedy)은 현재 상황에서 문제 해결을 위한 가장 좋아 보이는 것을 고르는 방법입니다. 이렇게 매순간 최적의 해라 생각되는 방법을 토대로 반복하여, 결과적으로 최적의 해에 도달하는 것입니다. 탐욕 알고리즘은 알고리즘에 대한 사전 지식을 많이 요구하지 않는 대신, 문제 해결에 대한 창의적인 접근이 필요합니다...
다익스트라 알고리즘으로 경로 나타내기
다익스트라 알고리즘으로 경로 나타내기
2022.02.20Dijkstra's Algorithm 특정한 두 노드 사이의 최단 거리를 구하는데 많이 사용되는 다익스트라 알고리즘은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)에 의해 만들어졌습니다. 다익스트라 알고리즘은 그래프 자료구조를 공부할 때 필수적으로 접하게 될만큼 중요도가 높은 알고리즘입니다. 그만큼 현실 세계의 많은 문제들을 해결하기 위해 사용되고 있는 것이지요. 그런데 이렇게 중요한 알고리즘이면서, 막상 공부할 때는 최단 거리를 구하는 코드를 제시합니다. 이런 아쉬움으로 인해 이번 기회에 다익스트라 알고리즘을 이용해 경로를 구하는 방법을 알아보려 합니다. 알고리즘의 전체적인 흐름은 다음과 같습니다. 알고리즘에 사용할 테이블(최단 거리, 부모, 방문 여부)을 만들고 초기..
자바스크립트스럽게 퀵 정렬 구현하기
자바스크립트스럽게 퀵 정렬 구현하기
2022.02.10JavaScriptonic 파이썬에는 파이썬스럽게 작성된 코드를 파이써닉(Pythonic)한 코드라고 말합니다. 또한 파이썬 특유의 문법을 활용해 가독성을 확보하면서, 효율적으로 프로그래밍하는 방식을 뜻하기도 합니다. 파이썬은 확실히 C나 Java 등과는 다른 유연한 문법을 가지고 있습니다. 그럼 자바스크립트에도 비슷한 용어가 있을까요? 그래서 한 번 구글에 찾아 봤지만, 원하는 내용은 딱히 없었습니다. 하지만 유행하는 신조어들은 누군가로부터 시작되어, 여러 사람들의 입을 타고 퍼진 것이기에 저도 한 번 해보겠습니다(?). 자바스크립토닉한 코드라 함은 어떤 것들이 포함될 수 있을까요? 지금 당장은 세 가지 정도가 떠오르네요. 호이스팅의 특성을 이용한 코드 ECMA Script 6 이상의 문법 활용하기 A..
스택을 이용한 계산기 만들기
스택을 이용한 계산기 만들기
2022.02.01수식의 다양한 표기법 🚀 살다 보면 계산이 필요한 상황을 자주 만나게 됩니다. 그럴 때마다 우리는 작은 수를 다루는 문제라면 단순 암산으로 해결하지만, 보다 큰 수를 다루는 경우에는 정확도를 위해 계산기의 도움을 받습니다. 그런데 우리가 이해하고 있는 계산식을 컴퓨터는 이해할 수 없다는 사실을 알고 계신가요? 1 + 3이라는 계산식을 우리는 직관적으로 이해할 수 있지만, 컴퓨터는 이를 연산자(+)와 피연산자(1, 3)로 분리한 후 일련의 로직으로 이해시켜야 합니다. 그리고 우리가 일상에서 사용하는 계산식을 중위 표현식(Infix Expression)이라 부르는데, 컴퓨터는 이를 바로 이해할 수 없기 때문에 전위 표기법(prefix) 또는 후위 표기법(postfix) 중 하나로 변환해 사용합니다. 위 그림..
그래프 (Graph)
그래프 (Graph)
2021.11.01Graph 그래프(Graph)는 노드와 간선으로 표현된 자료구조입니다. 그래프에서 노드는 정점이라 불리며, 각 정점은 간선으로 연결되어 있습니다. 정점은 도시로, 간선은 도시 간 이동을 위해 연결된 길로 생각하면 이해하기 쉽습니다. 그래프는 다른 자료구조와 달리 현실 세계를 표현하기 좋습니다. 정점과 간선을 도시와 길로 비유할 수 있듯, 이를 바탕으로 현실 세계를 모델링하면 대표적으로 네비게이션과 같은 시스템을 만들 수 있습니다. 만약 현실에서 마주하는 다양한 문제를 해결하고 싶다면, 그래프는 반드시 이해하고 넘어가야 하는 중요한 자료구조 중 하나입니다. 그래프에서는 다음 용어들을 사용합니다. 정점(Vertex): 하나의 노드 간선(Edge): 두 정점을 연결한 선 가중치(Weight): 간선이 가지는 ..
해시 테이블 (Hash Table)
해시 테이블 (Hash Table)
2021.11.01Hash Table 해시 테이블(Hash Table)은 데이터의 해시 값을 키로 사용한 데이터 집합을 말합니다. 해시는 데이터를 새로운 형태로 변환한다는 의미를 가지고 있으며, 주어진 키를 미리 구현한 해시 함수를 통해 변환합니다. 해시 테이블은 해싱 된 키를 통해 데이터에 바로 접근할 수 있으므로, 매우 빠른 탐색 속도를 갖고 있습니다. 해싱 함수에 일반적으로 사용되는 방법은 다음과 같습니다. 나눗셈법: 키 값을 테이블의 사이즈로 나눈 후의 나머지를 주소로 사용하는 방법 자릿수 접기: 문자열 키 값의 자리마다 정해진 아스키 코드를 합친 값을 주소로 사용하는 방법 해시 테이블을 사용할 때는 충돌(Collision)과 클러스터링(Clustering)을 방지해야 합니다. 충돌은 말 그대로 동일한 해시 값이 ..
우선순위 큐 (Priority Queue)
우선순위 큐 (Priority Queue)
2021.10.30Priority Queue 우선순위 큐(Priority Queue)는 요소들이 우선순위를 가지고 있으며, 높은 우선순위를 가진 요소들이 먼저 나올 수 있는 자료구조를 말합니다. 이전 포스트에 소개했던 힙을 그대로 사용하기 때문에, 사실 큐라고 하는 게 맞나 싶긴 하지만, 동작 자체가 큐와 동일하기 때문에 이런 명칭이 붙은 것 같기도 합니다. 힙과의 차이점은 노드에 우선순위를 할당 할 멤버 변수가 추가되었다는 것과 메소드의 이름이 큐에 맞게 변경된 것 말고는 없습니다. 그래도 힙이 선행되는 자료구조이기 때문에 꼭 이해해야 합니다. 그리고 우선순위 큐는 그래프 알고리즘 중 최소 신장 트리를 구성하는 프림 알고리즘과 최단 경로를 찾는 다익스트라 알고리즘 등에 활용할 수 있는 정말 유용한 자료구조입니다. 노드 ..
힙 (Heap)
힙 (Heap)
2021.10.29Heap 🙂 힙(Heap)은 트리 내에서 가장 크거나 작은 값을 루트로 가진 완전 이진 트리를 말합니다. 가장 작은 값이 루트로 오는 경우를 최소힙(Min-Heap)이라 말하며, 반대로 가장 큰 값이 오는 경우는 최대힙(Max-Heap)이라 합니다. 힙은 큐에서 나올 요소에 대해 우선순위를 적용하는 우선순위 큐를 만들 때와 힙을 통한 정렬인 힙 정렬에 활용할 수 있습니다. 루트가 가진 값이 기본적으로 최솟값 또는 최댓값이기 때문에 이런 활용들이 가능한 것입니다. 우선순위 큐는 이후의 포스트를 통해 소개하겠습니다. 힙은 새로운 요소를 추가하거나 제거할 때, 힙을 재구성해야 하므로 리스트보다는 배열로 만드는 편입니다. 노드 & 클래스 생성 function Node(data) { this.data = data..
이진 탐색 (Binary Search)
이진 탐색 (Binary Search)
2021.10.28Binary Search 이진 탐색(Binary Search)은 정렬된 데이터 집합 안에서 사용할 수 있는 매우 빠른 탐색 알고리즘입니다. 이진 탐색이라는 이름은 찾고자 하는 요소를 찾지 못했을 때, 탐색 범위를 1/2로 좁혀 나가기 때문에 지어진 이름입니다. 성능이 매우 뛰어나면서도 구현이 간단하기 때문에, 기본 알고리즘부터 소개합니다. const search = (arr, left, right, target) => { if (left >= right) { return -1; } const mid = Math.floor((left + right) / 2); if (arr[mid] === target) return mid; else if (arr[mid] < target) return search(arr..
정렬 알고리즘 (Sorting Algorithms)
정렬 알고리즘 (Sorting Algorithms)
2021.10.27Sorting Algorithms 정렬(Sorting)은 가장 기본적인 알고리즘이지만, 활용할 수 있는 영역이 무수히 많습니다. 대표적인 예로 내가 만든 블로그 서비스를 이용하는 사용자가 게시된 글을 최신순으로 보고 싶어 한다면, 날짜별로 정렬해서 제공하면 됩니다. 이처럼 데이터베이스에 저장된 데이터는 서비스와 함께 제공하는 경우가 많은데, 데이터에 대해 정렬을 하게 되면 탐색 시 간편하면서도 효율적인 접근이 가능해집니다. 본문에서는 버블 정렬부터 현대 프로그래밍 언어에서 채택해 사용하고 있는 팀 정렬까지 총 11가지 알고리즘에 대해 간단히 소개합니다. 알고리즘 동작에 대한 이해를 돕기 위해 동영상을 함께 첨부했습니다 🙂 01. 버블 정렬 (Bubble Sort) 버블 정렬은 데이터 집합을 순회할 때, ..
분리 집합 (Disjoint Set)
분리 집합 (Disjoint Set)
2021.10.26Disjoint Set 🙂 분리 집합(Disjoint Set)은 교집합을 갖지 않는 집합들을 의미합니다. 각 집합은 트리로도 표현이 가능한데, 다만 이 경우에는 자식 노드들이 부모를 가리키는 형태로 구현해야 합니다. 그렇게 하나의 트리를 집합과 같은 개념으로 보면 되고, 연결 관계가 없는 트리끼리 서로 분리 집합이라 보면 됩니다. 분리 집합은 합집합 말고는 연산이 따로 없기 때문에 구현은 쉽지만, 그래프 이론에서 많이 사용되므로 잘 알아 두고 넘어가야 합니다. 집합 생성 function Set(data) { this.data = data; this.parent = null; } const set1 = new Set(1); const set2 = new Set(2); 집합은 부모만 알면 되기 때문에, 트리..
수식 트리 (Expression Tree)
수식 트리 (Expression Tree)
2021.10.26Expression Tree 🙂 수식 트리(Expression Tree)는 이진 트리를 활용한 대표적인 케이스입니다. 수식 트리를 만들기 위해서는 몇 가지 조건을 충족해야 합니다. 하나의 연산자가 두 개의 피연산자를 취한다는 가정 하에 피연산자는 무조건 잎 노드여야 하며, 연산자는 가지 또는 루트 노드여야 합니다. 수식 트리는 후위 표현식을 사용하면 쉽게 만들 수 있는데, 후위 표현식을 뒤에서부터 분해하여 하나씩 노드로 만들어 연결하면 됩니다. 본문의 수식 트리는 하나의 연산자가 무조건 두 개의 피연산자를 취한다는 가정을 하고 구현했습니다. 노드 생성 function Node(data) { this.data = data; this.left = null; this.right = null; } 수식 트리는 ..