YunaNote

🔷 유클리드 호제법( euclidean - algorithm ): 두 수의 최대 공약수를 구하는 알고리즘이다. 유클리드 호제법을 사용하기 위해선 MOD 연산을 알고있어야한다.  MOD ?최대 공약수를 구하는 연산으로 Modulo 나머지 연산으로도 불린다. 🔷 유클리드 호제법의 원리🔻 큰 수에서 작은 수로 나누는 MOD 연산 🔻 앞에서 진행한 작은 수와 MOD 연산 결과값과 MOD 연산 수행🔻 반복하다가 나머지가 0이 되는 순간 작은 수를 최대 공약수로 선택

🔷 오일러 피( Eluer's phi )?해당 기호를 사용하며 phi라고 읽으며 대표적으로 서로소 관련 문제에서 사용된다. 🔷P[N] ?1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 💡 서로소란?두 수 사이의 관계에서 공통되는 약수가 최대 1이며 1 밖에 없는 수를 뜻한다. 서로소의 예시로는 아래와 같이 확인 할 수 있다. ◾ 5의 약수 : 1 , 5◾ 6의 약수 : 1 , 2 , 3 , 6◻ 5와 6의 최대 공약수는 1이며 두 수가 일치하는 수는 1이므로 서로소라고 할 수 있다.  🔷  오일러 피의 원리🔻 구하고자 하는 오일러 피의 범위만큼 배열 초기화🔻 2부터 시작해서 인덱스가 같을 때(소수일 때) 현재 선택된 숫자의 배수에 해당되는 수(K)의 배열 끝까지 탐색 후  P[i..

🔷 소수(Prime number)?1과 자기 자신 외의 약수가 존재하지 않는 수를 의미한다. 🔷 소수를 구하는 판별법에라토스테네스의 체 ( Sieve of Eratosthenes ) : 소수들을 대량으로 빠르고 정확하게 구하는 방법 🔷 에라토스테네스의 체의 원리🔻 구하고자하는 소수의 범위만큼 1차원 배열 생성한 뒤 초기화한다.🔻 2부터 시작해서 현재 선택된 숫자의 배수의 해당되는 수를 모두 지운다. (이때 자기자신은 지우지않으며, 이미 지워진 수는 건너뛴다.)🔻 배열이 끝날 때까지 반복한 뒤 2부터 시작하여 남아 있는 수를 모두 출력한다  🔷 에라토스테네스의 체의 시간 복잡도이중 for문을 이용하여 O(N^2) 으로 판단될 수 있지만 배수를 삭제하여 생략하는 경우도 있기 때문에 O(n * l..

[ Algorithm ] 그리디 알고리즘그리디 (Greedy) / 탐욕 알고리즘 : 현재 상황에서 최적이라고 생각하는 해를 선택하는 방법이다. 하지만 앞으로 남은 단계의 선택을 고려하지않고 현재 단계의 가장 최선의 선택만 고려하기 때문o-joyuna.tistory.com 이전에 그리디 알고리즘을 공부하면서 정리한 내용이다. 또 코딩테스트 때 자주나오는 알고리즘의 하나이다. 🔷 그리디(Greedy) ?: 탐욕법이라고도 불리며, 현재 상태에서 보는 선택지 중 제일 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 즉 눈 앞의 가장 큰 이익을 추구하는 기법이다.  대부분의 그리디 문제에는 일반적으로 "최대한 적은, 최대한 많은" 이라는 문구가 문제에 들어가는 경우가 많다. 즉 최대/최..

퀵 정렬(Quick Sort)? 기준 값(Pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하여 반복해서 정렬하는 알고리즘 분할과정과 정복과정으로 나누어짐 Pivot을 정한 뒤 왼쪽 퀵 소트, 오른쪽 퀵소트를 진행 시간복잡도 평균 O(n log n) 최악의 경우 O(n^2) 참고 자료

삽입 정렬(Insertion Sort)이란? 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입해 정렬하는 방식 시간 복잡도는 O(n^2)로 느린 편 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입 삽입 정렬 수행과정 🔹현재 Index에 있는 데이터 값을 선택 🔹현재 선택한 데이터가 정렬된 데이터 범위에 삽입된 위치를 탐색 🔹삽입 위치부터 index에 있는 위치까지 shift 연산 수행 🔹삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산 수행 🔹전체 데이터의 크기만큼 index가 커질 때까지 수행 ( 선택할 데이터가 없을 때까지 반복 수행 ) 탐색하는 부분에서 이진 탐색과 같은 탐색 알고리즘을 통해 시간 복잡도를 줄일 수 있다. 관련 문제 [ 백준 ]..

선택 정렬 : 대상 데이터에서 최대나 최소 데이터를 나열된 순으로 찾아가며 선택하는 방법 구현 방법이 복잡하고, 시간복잡도는 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 사용하지 않음 1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다. 2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 Swap한다. 3. 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소 4, 남은 정렬 부분이 없을 때까지 정렬

정렬 알고리즘 정의 버블 선택 삽입 퀵 병합 기수 버블 정렬 : 두 인접한 데이터의 크기를 비교하여 Swap 연산으로 정렬하는 방법 시간복잡도 O(n^2) 으로 다른 정렬 알고리즘에 비해 속도가 느린 편 버블 정렬 과정 1. 비교 연산이 필요한 루프 범위 설정 2. 인접한 데이터 값을 비교 3. swap 조건에 부합하면 swap 연산을 수행 4. 루프 범위가 끝날 때까지 반복 5. 정렬된 영역을 설정한다. 다음 루프를 실행할 때는 이 영영을 제외 6, 비교 대상이 없을 때까지 반복 문제 [ 백준 ] 2750번 버블 정렬 - 수 정렬하기 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N..

스택 : 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조 스택 용어 top : 삽입과 삭제가 일어나는 위치를 말함 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 top : top 위치에 현재 있는 데이터를 단순 확인하는 연산 코딩테스트 사용 문제 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적 후입선출의 개념은 재귀 함수 알고리즘 원리와 일맥상통 큐 : 삽입과 삭제 연산이 선입선출로 이뤄지는 자료 구조, 스택과 다르게 먼저 들어온 데이터가 먼저 빠져나감 큐 용어 back : 큐에서 가장 끝 데이터를 가리키는 영역 front : 큐에서 가장 앞의 데이터를 가리키는 영역 push : back 부분에 새로운 데이터를..

슬라이딩 윈도우(Sliding Window) : 투 포인터와 유사하게 2개의 포인터로 범위를 지정, 범위(Window)를 유지한 채로 이동하며 문제를 해결하는게 특징 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법 슬라이딩 윈도우와 투 포인터 차이 투 포인터 슬라이딩 윈도우 구간의 넓이가 조건에 따라 유동적으로 변경 항상 구간의 넓이가 고정 관련 문제