👀알고리즘 개념

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수의 최대공약수를 구하는 알고리즘이다.호제법이란 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는다는 알고리즘을 말한다.자연수 2개 a,b에 대해서 a를 b로 나눈 나머지를 r이라 한다면(단, a > b), a

1보다 큰 자연수 중 1과 자기 자신만을 인수로 갖는 자연수.반댓말은 '합성수'이다.소수를 판별하는 알고리즘.빠르고 대량으로 소수를 구할때 유리하다.어떤 N이 두 개이상의 곱으로 나타낼 수 있을 때, 인수 중 하나 이상은 반드시 √N보다 작거나 같다.

이는 규칙을 찾아내면, 쉽게 표현할 수 있다.뒷자리가 0이 나오는 경우는 2와 5가 곱해질 때이다.즉, 소인수분해 한 뒤 2와 5가 존재할 경우 뒷자리는 0으로 끝난다는 의미이다.실제 팩토리얼 값을 나열하면 다음과 같다.이를 보면, 5의 배수마다 0의 카운트 값이 증가

0과 1로 구성된 2진수를 8진법 변환하기 위해서는 8 = 2³ 이기 때문에, 3자리마다 끊어서 변환해주면 된다.위의 계산을 보면, 중요한 규칙이 있다.왼쪽을 첫번째로 보면 0인 경우 0으로 취급하고 1인 경우 '4' 로 취급하여 더해준다.두번째는 1인 경우 '2'로

구간 합 알고리즘 활용을 위해서는 합 배열을 구하는 것이 선행되어야 합니다. 배열 A가 있을 때, 합 배열 S는 다음과 같이 정의합니다.합배열 정의Si = A0 + A1 + A2 + ... + An-1 + An위처럼 합배열을 미리 구해놓으면 기존 배열의 일정 범위의

"버블 정렬 알고리즘" 은 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식입니다.시간 복잡도 : O(n^2)다른 정렬 알고리즘에 비해서 속도가 많이 느린 편입니다.버블 정렬 과정1\. 비교 연산이 필요한 루프 범위를 설정.2\. 인접한 데이터

선택 정렬은 정렬할 데이터에서 최대 또는 최소 값을 데이터가 나열된 순서로 찾아가며 선택하는 방법입니다. 구현방법이 복잡하고, 시간 복잡도도 높아 비효율적인 정렬방법입니다.(많이 사용 X)시간 복잡도 : O(n^2)핵심이론은 최솟값 또는 최댓값을 찾고, 남은 정렬 부분

삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식입니다. 평균 시간 복잡도는 느린 편이지만 상대적으로 구현이 쉽습니다. 시간 복잡도 : O(n^2) 핵심이론은 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한

퀵정렬은 기준값을 선정하여 큰 데이터와 작은 데이터를 분류하는 것을 반복하여 정렬하는 알고리즘입니다.기준값을 선정하는 것이 핵심이며, 이에 따라 시간 복잡도에 많은 영향을 미칩니다.평균적인 시간 복잡도 : O(nlogn)핵심 이론은 기준값을 중심으로 계속 데이터를 2개

병합정렬은 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 입니다.시간 복잡도 : O(nlogn)핵심이론은 처음 가장 작은 데이터 집합으로 분할합니다. 그 다음 병합하면서 정렬을 하며, 마지막에는 큰 집합 2개를 병합하여 정렬을 하게 됩니다. 이 때, 2개의

오늘은 기수 정렬에 대한 개념을 익혀보도록 하겠습니다.기수 정렬은 값을 비교하지 않는 특이한 정렬입니다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교합니다.시간 복잡도 : O(kn) - k : 데이터의 자릿수기수 정렬의 핵심이론은 10개의 큐

참고 포스팅자바\[JAVA] - 카운팅 정렬카운팅 정렬이라... 여러 포스팅 글을 검색하여 읽어봤지만 처음 들어보는 정렬 방식이었습니다.카운팅 정렬은 수많은 정렬 알고리즘 중 시간복잡도가 O(n)으로 가장 좋은 성능을 보여주는 알고리즘 입니다.카운팅 정렬의 기본 메커니

깊이 우선 탐색(DFS)에 대해 설명하기 전 그래프 관련 간단한 용어부터 정리하겠습니다.'그래프' 는 '노드' 와 '에지' 로 구성된 집합입니다.노드 : 데이터를 표현하는 단위에지 : 노드를 연결깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나로, 보통 'DFS' 라고

참고 유튭 영상입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계주어진 식을 값이 가장 큰 대표향만 남겨서 나타내는 방법.O(N) : 5N + 3, 2N + 10lgN, 10NO(N^2) : N^2 + 2N + 4, 6N^2 + 20N + 10lgNO(NlgN) :

: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘.위의 그림에 '그래프' 라는 자료구조의 완전 탐색을 위한 알고리즘.DFS와 마찬가지로 방문배열과 인접 리스트로 표현하지만, 선입선출 구조를 사용해야하기 때문에, Queue 자료구조를 사용합니다.그

참고 포스팅https://st-lab.tistory.com/267직역하면 lower bound 는 하한, upper bound는 상한을 의미합니다.그림으로 나타내면 아래와 같습니다.처음으로 마주하는 key 값 이상을 갖는 인덱스는 3입니다.즉, lower bo

참고 포스팅https://blog.encrypted.gg/975매번 선택에서 지금 가장 최적의 답을 근시안적으로 택하는 알고리즘입니다.비슷한 말로, 관찰을 통해 탐색 범위를 줄이는 알고리즘을 말합니다.해당 유형은 많은 문제 유형을 풀어봐야 하는 것으로, 비슷한

오일러 피 함수 PN의 정의는 1부터 N까지 범위에서 서로소인 자연수의 갯수를 뜻합니다. 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있지만 해당 블로그에서는 실제 코딩 테스트에 사용하기 위한 구현 부분만 알아보겠습니다.여기서 '서로소' 란,1 이외에 공약수

기존의 유클리드 호제법의 목적은 두 수의 최대 공약수를 구하는 것이었습니다. 이와 다르게 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것입니다.해를 구하고자 하는 방정식ax + by = c (a,b,c,x,y는 정수)이 때 위 방정식은 c % gcd(a,b)

트리(Tree) 는 노드와 에지로 연결된 그래프의 특수한 형태입니다.트리의 특징순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖음.트리의 부분 트리 역시 트리의 특징과 동일함.트리 내에 또 다른 트리가 재귀적

이진 트리(Binary Tree)는 각 노드의 자식 노의 갯수가 2 이하로 구성되어 있는 트리를 말합니다.이진트리의 종류편향 이진 트리 : 노드들이 한쪽으로 편향돼 생성된 형태.포화 이진 트리 : 트리의 높이가 모두 일정하며, 리프 노드가 꽉 차있는 이진 트리.완전 이

DFS란? BFS란?!\[출처 : https://iq.opengenus.org/dfs-vs-bfs/현재 노드에서 최대한 들어갈 수 있는 깊이까지 들어가서 탐색하는 방식.스택 또는 재귀함수로 구현현재 노드에 연결된 가까운 인접 노드부터 탐색하는 방식.큐로 구현두

🖥️ 참고 포스팅https://st-lab.tistory.com/114어떤 노드의 '유망성'을 판단한 뒤, 해당 노드가 유망하지 않은 경우, 부모 노드로 돌아가 다른 자식 노드를 찾는 방법입니다.즉, 모든 경우의 수를 찾아보지만, 그 중에서도 가능성이 있는