Algorithm/Data Structure, Algorithm
[알고리즘][파이썬] 소수 판별 알고리즘(에라토스테네스의 체)
소수란? 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수를 말한다. 기본적인 소수 판별 방법 def is_prime(num): # 2부터 (num - 1)까지의 모든 수 확인. for i in range(2, num): # 하나라도 i로 나눠진다면 False를 반환. if num % i == 0: return False return True 이 때 시간복잡도는 O(n)이므로 n의 크기가 크면 비효율적이다. 이보다 좀 더 효율적인 방법은 n - 1까지가 아닌 n의 제곱근까지만 확인하는 것이다. 이렇게 해도 되는 이유는 무엇일까? 예를 들어 16의 약수 [1, 2, 4, 8, 16]이 있다고 해보자. 잘 살펴보면 가운데에 있는 수를 기준으로 대칭적으로 곱해 16을 만들..
[자료구조][JS] 삽입 정렬(Insertion Sort)
삽입 정렬(Insertion Sort)이란? 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료와 비교해 삽입할 위치를 결정하는 알고리즘 즉, 두 번째 자료는 첫 번째 자료와, 세 번째 자료는 두 번째와 첫 번째 자료와 비교를 해 삽입될 위치를 찾는다. 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 처음 Key값은 두 번째 자료부터 시작한다. 예시 배열에 3, 7, 2, 5, 1, 4가 있다고 가정하고 자료를 오름차순으로 정렬해보자. 1. key: 7(두 번째 자료). 첫 번째 값인 3과 비교한다. 2. key: 2(세 번째 자료). 두 번째 값인 7과 비교해 7을 한 칸 뒤로 이동한다. 첫 번째 값인 3과 비교하고 3을 한 칸 뒤로 이동한다. 2를 첫 번째 자리에 넣는다..
[자료구조][JS] 선택 정렬(Selection Sort)
선택 정렬(Selection Sort) 시간 복잡도 최선: O(n^2) 최악: O(n^2) 평균: O(n^2) 장점 실행 전에 자료의 이동 횟수를 알 수 있음 보조 메모리가 제한되는 경우 복잡한 알고리즘에 비해 성능적인 이점을 낼 수 있음 단점 보통의 경우 O(n^2)의 시간 복잡도로, 비효율적인 정렬 방식 배열 내에 동일한 값이 중복되어 있다면 상대적인 위치가 변경될 수 있음 - 코드 예시 function solution(arr) { let answer = arr; for (let i = 0; i = arr[j]) idx = j; } [arr..
[자료구조][JS] 스택, 큐 - push(), pop(), shift()
기본적인 자료구조인 스택, 큐에 대해서 JS로 정리해보려 한다. push() push() 메서드는 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환한다. arr.push(element1[, ...[, elementN]]) elementN: 배열의 끝에 추가할 요소. const animals = ['pigs', 'goats', 'sheep']; const count=animals.push('cows'); console.log(count); // expected output: 4 console.log(animals); // expected output: Array ["pigs", "goats", "sheep", "cows"] animals.push('cats', 'dogs'); conso..
[알고리즘][JS] 해쉬 알고리즘 - JS ES6 Map()
해쉬 알고리즘이란? 해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다. 이를 이용해 특정한 배열의 인덱스나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존의 자료 구조들을 탐색이나 삽입을 할 때 선형시간이 걸리기도 했던 것에 비해 해쉬를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더 빠른 속도로 처리할 수 있다. 1. 직접 주소 테이블(Direct Addressing Table) Direct Addressing Table은 key-value 쌍의 데이터를 배열에 저장할 때 key값을 직접적으로 배열의 인덱스로 사용하는 방법이다. 예를 들어 키 값이 400인 데이터가 있다면 이는 배열의 인덱스가 400인 위치에 키 값을 저장..
투포인터 알고리즘, 슬라이딩 윈도우
투포인터 알고리즘(Two Pointers Algorithm) 투포인터 알고리즘은 1차원 배열에서 각자 다른 원소를 가르키는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 알고리즘 문제를 풀다가 완전 탐색으로 해결하다가 시간 초과가 발생하는 경우에 사용할 수 있다. 문제는 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립할 경우 사용할 수 있는 알고리즘은 다음과 같다. 포인터 2개를 준비. 이를 left, right라고 함. 처음에는 left = right = 0. 항상 left
[알고리즘] 완전탐색(Brute-Force)
완전탐색이란 가능한 모든 경우의 수를 일일히 나열하면서 계산하는 방법이다. 이는 100%의 확률로 문제의 답을 찾아낼 수 있는 방법이다. 하지만 완전 탐색은 답으로 가능한 경우의 수가 많은 경우에는 이용하기가 어려우므로 이를 활용할 수 있는 문제인지 잘 생각해보고 쓰는 것이 좋다. 아래는 완전 탐색을 이용할 수 있는 예제들 정리 (풀어볼 것!) https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net https://www.acmicpc.net/problem/22..