💻 컴퓨터공학/알고리즘
자바스크립트로 코딩 테스트 준비하기
자바스크립트로 코딩 테스트 준비하기
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) 중 하나로 변환해 사용합니다. 위 그림..
이진 탐색 (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) 버블 정렬은 데이터 집합을 순회할 때, ..
알고리즘의 성능을 평가하는 복잡도
알고리즘의 성능을 평가하는 복잡도
2021.10.23알고리즘 성능 평가 척도 📐 알고리즘 성능을 나타내는 척도는 일반적으로 복잡도(Complexity)라는 것을 사용합니다. 복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있으며, 각각 프로그램 실행 시간이 얼마나 걸리는지와 메모리 공간을 얼마나 사용하는지에 연관이 있습니다. 동일한 기능을 수행하는 알고리즘은 복잡도가 낮은 것이 더 좋습니다만, 일반적으로 시간 복잡도와 공간 복잡도는 서로 트레이드오프(Trade-off) 관계를 가집니다. 그래서 코딩 테스트와 같은 환경에서는 메모리를 좀 더 사용하면서 수행 시간을 줄이는 식으로 문제를 해결하곤 합니다. 시간 복잡도 문제를 해결할 때 복잡도가 몇인지 물어보면 대개 시간 복잡도를 의미합니다. 시간 복..