알고리즘

Dynamic Programming란? (동적 계획법) 하나의 큰 문제를 여러 개의 작은 문제로 나눠서 그 결과를 저장해 다시 큰 문제를 해결할 때 사용 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 특정 알고리즘이 아닌 하나의 문제해결 패러다임 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 함 "기억하며 풀기...

Greedy(그리디) 란? 매 선택에서 현재 당장 최적인 답 을 선택해 전체 적합한 결과를 도출하는 기법 BackTracking을 통해 추가 점검을 하지 않고 현재 조건에서 선택했다면, 더이상 다른 선택 가능 경우는 검증하지 않는다. 지역적으로 최적이면서 전역적으로 최적인 문제들에 적용한다. 한계점 순간마다 하는 선택은 그 순간에 대해 지역적...

완전탐색 이란? 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법 무식하게 가능한 것을 다 해보는 것 (= Exhaustive search, Brute force) 직관적이어서 이해하기 쉽고, 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하고 기초적인 방법 상대적으로 구현이 간단하고, 해가 존재하면 항상 찾게 됨 경우의 수에 따라 실행 시...

그래프 탐색 알고리즘 그래프 탐색 알고리즘은 DFS (깊이 우선 탐색) BFS (너비 우선 탐색) 두가지 종류로 나눌 수 있다. 두가지 알고리즘에 대해 알아보고 해당 알고리즘을 javascript 언어로 구현해보도록 하겠다. DFS란? 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 특정한 경로로 쭉 타고 밑바닥까지 내려간 후, 막다른 길에...

순열 (Permutation) [nPm] 서로 다른 n개의 물건 중에서 m개를 택하여 한 줄로 배열하는 것 순서가 있는 정렬을 만드는 경우의 수 > 예시) [a,b,c] 배열 내의 요소 모두를 줄 세우는 방법 [a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a] 총 3! (=6개의) 경우의 수가 있음 구현하기 어...

힙(Heap) 기본개념 Binary Tree (이진 트리) 한 노드가 최대 두개의 노드를 자식으로 가질 수 있는 트리 구조 마지막 레벨을 제외한 모든 레벨에는 노드들이 가득 차있고, 마지막 레벨의 노드들고 좌측부터 순서대로 들어가 있음 노드 개수를 알면, 트리의 구조를 특정할 수 있다. > 현재 노드 번호 i 현재 노드 parent node의 번호 = (...

유클리드 호제법 > 유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 유클리드 호제법에 의하면 A와 B 두 수의 최대공약수를 구할 때, A = Bq+r 의 식으로 만든 뒤 B와 r의 최대공약수를 구하는 문제로 바꿀 수 있다. 연속되는 B, r의 최대공약수에 대해서도 B = rq+r2 와 같이 재귀가 가능하다. 최대공약수는 A,B 모두...

투 포인터 & 슬라이딩 윈도우는 언제 사용하는지 > 배열의 특정 연속된 구간을 처리하기 원하는 경우 투 포인터와 슬라이딩 윈도우는 구간을 훑으면서 지나간다는 공통점이 있다. 하지만 슬라이딩 윈도우는 구간의 넓이가 동일하다는 점이 차이점이다. 투 포인터 > 1차원 배열에서 배열을 가리키고 있는 2개의 포인터 를 조작하여, 원하는 값을 얻는 알고리즘 예시...

소수란? 소수는 1보다 큰 자연수 중, 1과 자기 자신만을 약수로 가지는 수이다. 소수 판별법 소수를 판별하는데에 있어서 여러가지 방법이 있다. > 1. 직접 나눠서 계산 n / 2 까지 나눠서 계산 n의 제곱근 까지 나눠서 계산 위 3가지의 방법에 대해서 정리해보려 한다. 1. 직접 나눠서 계산 > 시간 복잡도 O(N) 2부터 소수를 판별할 수...

약수란 ? 인수를 나누어 떨어지게 하는 수 어떤 정수를 나머지 없이 나눌 수 있는 정수 ex) 8의 약수 : 1, 2, 4, 8 약수 구하기 알고리즘 > 1. 단순하게 모든 수를 나눠서 약수 구하기 주어진 수의 절반을 대상으로 확인하기 제곱근을 사용하기 3가지 방법에 대해 정리해볼 예정이다. 1. 단순하게 모든 수를 나눠서 약수 구하기 가장 ...

LCS? LIS? LCS(Longest Common Subsequence) 는 가장 긴 공통 부분 수열으로, 공통적으로 일치하는 수열 중 가장 긴 부분을 의미한다. LIS(Longest Increasing Subsequence)는 가장 긴 증가(또는 감소) 하는 수열을 의미한다. 두 가지 모두 DP 알고리즘에 속한다.두 가지의 개념과 구현코드를 정리할 예...