코딩 헬스장

알고리즘 풀이에 도움이 되는 수학을 정리하고자 글을 작성합니다! 새로운 사실을 알 때마다 정리할 생각입니다 ! - update : 220527, 220531 [ 정리 목록 ] 소수판별 좌표의 거리 구하기 소인수 분해 최대공약수(GCD)와 최소공배수(LCM) - feat. 유클리드 호제법 피보나치 수열 에라토스테네스의 체 골드바흐의 추측 🤔 소수 판별 소수란 1과 자기 자산 외의 약수를 가지지 않는 1보다 큰 자연수입니다. 4 이상의 짝수는 무조건 소수가 아닙니다. (2의 배수이기 때문에) N이 소수가 아니라면 [ 2 ~ √N (루트 N) ] 범위에 약수가 무조건 존재합니다. 따라서 해당 범위에 약수가 없다면 N은 소수입니다. function isPrime(num) { // 2,3 은 소수 if (num ..

( 누적합 알고리즘 간단 예제 ) [ 1, 2, 3, 4, 5 ] 로 이루어준 숫자 배열에서 각 구간까지의 합을 구하는 배열 [ 1, 3, 6, 10, 15] 을 구한다고 가정해보면 아래와 같이 2가지로 구할 수 있습니다. [ 첫번째 방법 ] 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5 식으로 각 인덱스까지의 값을 반복하며 구하기. [ 두번째 방법 ] 1 1+2 3+3 6+4 10+5 식으로 이전 인덱스까지의 누적합에 현재 인덱스의 값을 더하여 구하기. 2가지 방법을 비교해보면 두 번째 방법이 훨씬 효율적이라는 것을 알 수 있습니다. 누적 합 이란 수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적 합이라고 합니다. 시작점은 항상 첫번째 원소이며, R번째 원소까지의 합을 앞에서부터..

1. 슬라이딩 윈도우 알고리즘 (Sliding Window) ( 슬라이딩 윈도우 알고리즘 간단 예제 ) 1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 구한다고 가정해보면 아래 5가지의 경우의 수가 나옵니다. [1, 2, 3], 4, 5, 6, 7 1, [2, 3, 4], 5, 6, 7 1, 2, [3, 4, 5], 6, 7 1, 2, 3, [4, 5, 6], 7 1, 2, 3, 4, [5, 6, 7] 다음으로 합을 계산하는 고정된 크기의 배열의 변화를 보면 [1,2,3] => [2,3,4] => [3,4,5] ... => [5,6,7]입니다. 그렇다면 어떻게 최소한의 계산으로 다음 배열의 합을 구할 수..

1. 스택(Stack) 스택은 후입 선출(Last In First Out -가장 마지막에 삽입된 자료가 가정 먼저 삭제된다는 의미) 개념이다. 즉, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 예를들어 바닥이 막힌 상자에 물건을 쌓는다고 생각하면 쉽다. 나중에 넣은 물건이 제일 위에 있으므로 먼저 꺼내게 된다. 정해진 방향으로만 쌓을 수 있다. 저장소의 끝 부분(가장 최근에 들어온 자료). 즉, 가장 먼저 빠져나갈 데어터의 위치를 top이라고 한다. top으로 정한 곳을 통해서만 접근가능하며, 새로 사입되는 데이터는 top이 가리키는 맨 위에 쌓이고, 자료를 삭제할 때도 top의 위치의 데이터를 삭제한다. 삽입은 push, 삭제는 pop 한다고 한다. 스택의 시간 복잡도 삽입(Insertion..

해시 함수 (짦게는 그냥 해시)는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 말한다. Key - Value 쌍으로 가지는 자료구조의 형태이며, 해쉬 함수는 Hash(k) = V 로 표현할 수 있다. Hash Function을 통해 K를 입력하면, 값 V가 출력된다. 이때 K가 같으면 항상 같은 V가 출력된다. 1. 해시 테이블 (Hash Table) key와 value를 가지는 자료구조의 종류 중 하나 (ex. 대표적으로 JS에서 Object, Map, Set 등) Hash Function을 통해 빠른 탐색이 가능하다.(키 값을 통해 바로 접근 가능하므로) 따라서 시간복잡도는 O(1) 2. 문제 유형 ex) https://programmers.co.kr/learn/..