반응형 Algorithm/알고리즘10 [알고리즘] 접두사합(prefix sum) 알고리즘 by javascript (ft. 부분합/구간합) Prefix Sum(접두사 합) 부분합, 누적합, 구간합 등으로 불리며 해당 합을 빠르게 구하는 알고리즘이다. 사실 알고리즘 치고는 매우 간단하다. 이 알고리즘의 원리는 다음과 같다. 각각의 숫자까지의 합을 미리 계산하여 저장해놓고 그 저장한 값을 활용하여 구간합을 구한다. 사실 접두사합, 구간합, 부분합 알고리즘을 검색하면 많은 블로그가 나올 텐데, 기본적으로 접두사 합 알고리즘의 공식을 다음과 같이 설명하고 있다. P[Right] - P[Left - 1] 크게 틀린 공식은 아니니 일단 이런 식으로 사용하는구나 정도는 알고 진행하면 좋다. 다른 알고리즘도 마찬가지겠지만 문제에 따라 정해진 공식을 사용할 수 없는 경우가 많다. 예를 들어 숫자 [100, 101, 102, 103, 104]가 주어졌다고 가.. 2022. 10. 12. [알고리즘] 유클리드 호제법(Uclidean algorithm) by javascript - 최대공약수 / 최소공배수 구하기 알고리즘 최대 공약수를 구하는 알고리즘인 유클리드 호제법에 대해 알아보자. 그리고 추가적으로 최소공배수까지 구하는 방법 역시 알아보자. 1. 최대공약수 구하기 우선 최대공약수란 두 수의 공통인 약수(공약수) 중에서 가장 큰 수를 최대공약수라고 부른다. 유클리드 호제법의 원리를 다음과 같이 설명한다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a> b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 무슨 소리인지 모르겠지만 일단 원리를 따라가보면 두 수(a, b)가 주어지고 이 둘을 나눈 나머지를 구하라는 의미 같다. 예를 들어 1071 과 1029 주어 졌다면 다음과 같은 원리를 따른다. (1071은 1029로 나누어 떨어지지 않기 때문에 둘을 나눈 나머지를 .. 2022. 4. 20. [알고리즘] 정렬 알고리즘(2) by javascript - Merge(병합/합병) * 정렬의 동작 원리는 아래 사이트를 통해 보면 이해하기 쉽다. https://visualgo.net/en/sorting Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook.. 2022. 4. 10. [알고리즘] 정렬 알고리즘(1) by javascript - Bubble(버블), Selection(선택), Insertion(삽입) 알고리즘을 배우게 되면 머리에 가장 오래 남아있던 그 정렬 알고리즘에 대해 알아보자. 사실 javascript에서는 Array.prototype.sort()라는 배열 메서드가 존재해서 굳이 정렬 알고리즘을 알아야 되나 싶기도 한데, 알아둬서 나쁠 건 없다고 생각된다. 정렬의 동작 원리는 아래 사이트를 통해 보면 이해하기 쉽다. (싱가폴 대학(?)에서 만든 학습용 사이트라는데 시각적으로 표현되어 있어서 보기 좋다.) https://visualgo.net/en/sorting Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo VisuAlgo is free of charge for Computer Science com.. 2022. 4. 10. [알고리즘] 그래프 탐색 알고리즘 by javascript - BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 코딩 테스트의 단골 문제인 그래프 탐색 알고리즘에 대해 알아보자. 그래프 탐색 알고리즘의 개념을 이해하기 위해서는 당연히 그래프 자료구조를 알고 있어야 한다. 이 글은 자료구조를 알고 있다는 가정하에 탐색 알고리즘인 BFS와 DFS만을 정리하고자 한다. (그래프에서는 인접행렬과 인접 리스트 방식이 존재하는데, 본 글은 인접 리스트를 사용한 BFS/DFS 알고리즘이다.) 1. BFS - 너비 우선 탐색 너비 우선 탐색 (Breadth-first search)은 정점들과 같은 레벨에 있는 즉, 인접한 노드들을 먼저 탐색하는 방식이다. 이미지를 통해 쉽게 접해보고 너비 우선 탐색의 특징에 대해 알아보자. 너비 우선 탐색은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법으로 두 개의.. 2022. 4. 6. [알고리즘] 약수 구하기 알고리즘 by javascript 약수 구하는 알고리즘에 대해 알아보자. 기본적으로 약수란 인수를 나누어 떨어지게 하는 수를 의미하는데, 약수를 구하는 여러 가지 방법에 대해 하나씩 알아보자. (아래 예제 코드는 약수들을 구하는 알고리즘이기 때문에 약수의 합을 구하거나 등의 상황에 맞춰 바꿔 사용하면 된다.) 1. 단순하게 모든 수를 나눠서 약수 구하기 const getDivisors = (num) => { const divisors = []; for(let i = 1 ; i { const divisors = []; for(let i = 1 ; i { const divisors = []; for(let i = 1 ; i a - b); return divisors; } 제곱근을 이용하는 방식은 좀 이해가 필요하다. num 을 100이라고 .. 2022. 4. 1. [알고리즘] 이진 검색/탐색(Binary Search) 알고리즘 by javascript (ft. lower / upper bound) 이진 검색/탐색 알고리즘 (binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 절차를 지닌다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 이러한 검색 원리로 원하는 값이 나올 때까지 반복하는 알고리즘이다. 이진 탐색 알고리즘 원리는 아래 그림을 살펴보면 좀 더 이해가 쉬울것이다. 검색 원리상 위에서 설명했지만 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목푯값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 그렇다 보니 아무래도 선형 탐색.. 2022. 3. 26. [알고리즘] 소수 판별하기 - 여러가지 방법의 소수 판별법 by javascript 앞서 "[알고리즘] 소수 찾기 - 에라토스테네스의 체 by javascript" 라는 제목의 소수 찾기 알고리즘을 정리하였는데, 지금 까지 소수 찾기 및 소수 판별에 있어 전부 에라토스테네스의 체 코드를 사용하여 리스트를 뽑고 그 안에 포함되어있는 지를 체크해왔다. 하지만 역시 자바스크립트는 자바스크립트... RangeError: invalid array length 에러가 발생하면 그 방식을 사용할 수 없었다. (당연하게도 소수 찾는 방식으로 사용한걸 단순히 하나의 숫자에 대한 소수 판별에, 사용하는 데에는 제약사항이 있을 수 있다는 걸 간과했다.) 그래서 이제 소수 판별하는 여러가지 방법에 대해 알아보고자 한다. 1. 단순하게 모든 수를 판별하기 const isPrime = (num) => { if(.. 2022. 3. 8. [알고리즘] 조합, 순열, 중복순열 - 경우의 수 찾기 by javascript (ft. 모든 경우의 수) (이 글로 이해가 안된다면 정말 자세한 내용과 설명은 본문 하단에 링크를 달아뒀으니 해당 블로그 가서 보면 된다. 정말 정리를 잘해놨다.) 완전 탐색 알고리즘의 방식인 조합, 순열, 중복순열 알고리즘에 대해 알아보자. 왜 이 3가지 알고리즘을 동시에 다루냐면 알고리즘 구조가 비슷하기 때문이다. 전체적으로 아래와 같은 형식을 지닌다. 1. 선택하려는 개수를 확인한다. (ex 배열에서 2개의 값으로 이루어진 조합 혹은 순열) 2. 배열의 길이만큼 반복한다. 3. 배열에서 하나의 수를 선택한다. (기준 값) 4. 기준 값을 제외한 나머지 배열을 가지고 다시 1번부터 시작한다. (재귀) 위 방식을 통해 계속해서 재귀를 통해 반복하다보면 순열, 중복순열, 조합을 구할 수 있다. 각 조합, 순열, 중복순열 별 달라.. 2022. 3. 5. 이전 1 2 다음 반응형
