유혁스쿨

그래프 노드와 엣지로 구성된 집합. 예) 트리 노드 데이터 표현 단위 엣지 노드를 연결할 때 사용 그래프 알고리즘 종류 유니온 파인드 위상 정렬 다익스트라 벨만-포드 플로이드-워셜 최소 신장 트리 유니온 파인드 그래프의 `사이클 생성 유무`를 판단하는 알고리즘 그래프에서만 쓰이는 알고리즘은 아님 사용 예) `집합에서 대표 노드 탐색` 혹은 `각 원소들을 유니온 하여 하나의 집합으로 통합` ex) 3개의 노드와 2개의 엣지로 구성되었다고 가정했을 때 엣지를 추가할 경우 현재 그래프에 사이클이 생성되는가 → 유니온 파인드로 사이클 생성 여부를 도출한다. 위상 정렬 그래프의 각 노드들을 선형으로 정렬하는 알고리즘 알고리즘 사용 선 조건 사이클이 없어야 한다. 방향(간선)이 있는 그래프이다. ⓐ → ⓑ → ⓒ ..

유클리드 호제법 두 수의 최대 공약수를 구하는 알고리즘 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현 할 수 있지만 유클리드 호제법은 조금 더 간단한 방법을 제시한다. 먼저 MOD 연산을 이해 → MOD 연산은 유클리드 호제법에서 최대 공약수를 구하는 핵심 이론 연산 기능 예제 MOD 두 값을 나눈 나머지를 구하는 연산 10 MOD 4 = 2 # 10 % 4 = 2 아래 3단계로 진행한다. 큰 수를 작은 수로 나누는 MOD 연산 수행 앞 단계에서의 작은 수와 MOD 연산 결괏값 (나머지)으로 MOD 연산을 수행 단계 2.를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택 GCD : Greatest Common Divisor로 최대 공약수의 줄..

서로소란? 공약수가 1외에 없는 수를 뜻함 공약수란? 둘 이상의 정수에서 공통된 약수를 뜻함 공약수와 연관지어 설명하자면 서로소란 둘 이상의 정수에서 공통된 약수중 공약수가 1 외에 없는 수를 말한다. ex) 28과 45은 서로소이다. => 공약수가 1밖에 없기 때문 (두 수는 공통분모, 연관성이 1외에는 없다) 오일러 피(phi) 오일러 피 함수 P[N]의 정의는 1부터 N 까지 범위에서 N과 서로소인 자연수의 갯수를 뜻한다. ex) P[6] = 1~6 범위에서 6과 서로소인 자연수의 갯수 {1, 2, 3, 4, 5, 6} => {1, 5} 2개 에라토스테네스 - 체 이론과 비슷하다. 구하고자 하는 오일러 피의 범위 만큼 배열을 자기 자신 인덱스값으로 초기화 2부터 시작해 현재 배열의 값과 인덱스가 같..

소수란? 자신보다 작은 2개의 자연수를 곱해서 만들수 없는 1보다 큰 자연수 즉, 1과 자기 자신 외에 약수가 존재하지 않는 수를 뜻함 에라토스테네스 체 기법 소수를 구하는 대표적인 판별법 원리 구하고자 하는 소수의 범위만큼 1차원 배열 생성 2번째 부터 시작하며, 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움 (처음 선택한 숫자는 지우지 않음) 배열 끝까지 2. 을 반복한 후 배열에 남아 있는 모든 수를 출력한다. ▼ 탐색과정 ▼ (1부터 30까지의 수 중 소수를 구한다.) ① 주어진 범위 까지 배열을 생성 (1은 소수가 아니므로 삭제하고 2부터 시작) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 10 ..

그리디 알고리즘 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 즉, 현재 상태에서 선택할 수 있는 방법 중에 최선의 선택을 계속 하다보면 전체 문제에 대한 최선의 선택지가 나올것이라고 가정한다. 예를들어 아래와 같이 1개의 문제에서 5가지의 시점이 존재한다고 가정해본다. ¹ best ² best ³ best ⁴ best ⁵ best 1 ~ 5 총 5가지 시점에서 각 시점의 최선의 해를 선택하여 전체를 풀어나간다. → 위와 같이 풀어 나가다 보면 전체를 푸는 가장 최선의 해가 나올것이라는것이다. 라고 가정하면서 푸는 알고리즘 그리디 알고리즘의 단점 전체 시점을 총 아울렀을 때 항상 최적의 해를 보장하지는 않는다. 코딩 테스트에서는 항상 최적의 해, ..

이진탐색 데이터가 정렬되어 있는 상태 에서 원하는 값을 찾아내는 알고리즘 간단한 구현에 비해 괜찮은 성능을 내는 탐색 알고리즘으로 실제 코딩테스트에서 종종 출제 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘으로 대상 데이터 중앙값과 찾고자 하는 값을 비교해 데이터 크기를 절반씩 줄이면서 대상을 탐색한다. 기능 특징 시간복잡도 타겟 데이터 탐색 중앙값 비교를 통한 대상 축소 방식 O(logN) 오름/내림 차순으로 정렬된 데이터에서 사용한다. 현재 데이터 셋의 중앙값을 선택 중앙값과 타겟데이터를 비교한다. 중앙값 > 타겟 데이터 중앙값 기준 왼쪽 데이터 셋을 선택한다. 중앙값 < 타겟 데이터 중앙값 기준 오른쪽 데이터 셋을 선택한다. 1 ~ 2번을 반복하여 중앙값과 타겟값이 동일..

너비 우선 탐색 - BFS(Breadth First Search) DFS와 같이 그래프 완전 탐색 기법 중 하나이다. 시작노드에서 출발하여 가장 가까운 노드를 먼저 방문하며 탐색하는 알고리즘이다. 기능 특징(구현 방법) 시간복잡도 (V: 노드 수 / E: 엣지 수) 그래프 완전 탐색 FIFO 탐색 O(V+E) Queue 자료구조를 이용 FIFO의 특성을 갖는 선입선출 방식의 Queue 자료구조를 사용 탐색 시작 노드와 가까운 노드를 우선하여 탐색 (목표노드에 도착하는 경로가 여러개 일 때 최단 경로를 보장함. 문제 유형 ? 핵심 이론 한번 방문한 노드는 재방문 하지 않음 - `방문배열` 이라고 부르는 방문 여부를 체크할 배열이 필요하다 FIFOO(선입선출)탐색 방식 - Queue 자료구조를 사용한다. 탐..

깊이 우선 탐색 - DFS(Depth First Search) 그래프 완전 탐색 기법 중 하나이다. 완전 탐색이란 그래프의 모든 노드를 탐색 하는것을 의미한다. 그래프의 시작 노드에서 출발, 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른쪽 분기로 이동하여 다시 탐색 수행한다. 기능 특징(구현 방법) 시간복잡도 (V: 노드 수 / E: 엣지 수) 그래프 완전 탐색 재귀함수로 구현 O(V+E) 스택 자료구조를 이용 FILO의 특성을 갖는 스택 자료구조와 재귀함수의 로직이 비슷하다. 따라서 실제 구현 시 재귀함수를 이용하므로 스택 오버 플로우에 유의해야 한다. class DfsSearch{ public recursive() { recursive(); // 재귀 함수 } } 위와 같은 재귀 함수..

기수정렬 (Radix Sort) 직접 값을 비교하지 않는 특이한 정렬로, 각 값에 비교할 자릿수를 정한 뒤 자릿수끼리 비교한다. O(kn)의 시간복잡도를 갖는다 (k는 자릿수) 핵심 이론 각 자릿수에는 0~9 10개의 데이터를 받을 수 있으므로 10개의 Queue를 이용한다. 각 Queue는 각 자릿수를 대표한다. 대상 데이터의 각 자릿수별로 해당하는 숫자의 큐에 저장한 뒤 POP 한다. 1의 자리 기수 Queue 보관 → POP 10의 자리 기수 Queue 보관 → POP [1의 자리 정렬] 16 80 18 77 03 24 88 23 데이터 16 80 18 77 03 24 88 23 1의 자리 1(6) 8(0) 1(8) 7(7) 0(3) 2(4) 8(8) 2(3) 기수 6 0 8 7 3 4 8 3 데이..

병합정렬 분할정복(divde and conqure) 방식을 사용하여 데이터를 분할한다. 분할된 데이터 집합을 정렬하며 합치는 알고리즘이다. O(NlogN)의 시간복잡도를 가진다. 핵심이론 분할정복방식을 통해 부분 그룹으로 데이터를 나눈다. 왜 NlogN인가? 정렬하려는 데이터 8개를 3번만에 병렬하여 정렬한다 분할시 logN이 되기 때문에 3회 분할은 log8(2³)로 정의할 수 있다. 8개의 데이터를 3회 분할후 정렬했으므로 8개 * log8 회 매 LOOP에서 데이터 그룹에 '8번 Access'하며, 비교하는 작업을 '3회 분할'후 정렬했으므로 8번 * log8 회 아래 병합+정렬을 보면 좌측 pointer를 4번 우측 pointer를 4번 이동시키며 비교한다. 이는 8log8 즉 NlogN이 된다...

퀵정렬 기준값(pivot)을 선정하여 해당 값보다 작은 데이터와 큰 데이터로 분류하는것을 반복하여 정렬한다. 기준 값이 어떻게 선정되는지에 따라 시간복잡도에 많은 영향을 미친다. 평균 시간복잡도 : O(NlogN) (ex: 병합정렬) 최악 시간복잡도: O(n²) (ex: 버블, 선택, 삽입 정렬) 핵심이론 pivot을 중심으로 데이터를 2개의 집합으로 나누며 정렬을 반복 퀵정렬 과정 ⓐ 데이터를 분할하는 pivot(기준데이터)을 설정 ⓑ pivot을 기준으로 아래의 과정을 거쳐 데이터를 2개의 집합으로 분리한다. (start pivot) end의 데이터가 pivot의 데이터 보다 ..

삽입 정렬 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식으로 O(n²)의 시간복잡도로 느린편이나 구현하기는 쉽다. 핵심 이론 선택된 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입한다. (첫번째 인덱스 선택된 데이터의 경우 정렬된 데이터 범위 그 자체 이므로 정렬할수가 없다. 따라서 LOOP는 돌지만 마치 정렬되지 않은것처럼 다음 LOOP로 넘어간다.) 최 우측의 5번째 데이터 삽입 시 선택된 데이터40은 인덱스 1번의 32보다 크다. 이때 앞의 데이터들은 모두 정렬된 데이터들 이므로 선택한 데이터 40은 인덱스 1번의 32보다 작지 않은 조건에 의해 더이상 앞의 데이터까지 비교연산을 수행하지 않는다. 삽입정렬 수행 과정 현재 index에 있는 데이터..

선택정렬 정렬되지 않은 대상 데이터의 최대 혹은 최소값을 데이터가 나열된 순으로 찾아가며 선택한다. 눈, 머리의 이해는 쉬우나 코드 구현이 복잡하다. O(n²)의 비효율적인 시간복잡도 때문에 코딩테스트에서 빈번하게 나오지는 않음 BUT 문제의 일부로 사용될 수 있거나 기술 면접에서 질문의 대상이 될 수 있으므로 원리를 이해해야함 핵심이론 오름차순 : 최솟값 부터 선택 내림차순 : 최대값 부터 선택 정렬 형태에 따라 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞의 데이터와 Swap한다. 선택정렬 과정 남은 정렬 부분에서 정렬형태(오름/내림)에 따라 최솟값, 최대값을 찾는다. 남은 정렬 부분에서 가장 앞의 데이터와 선택된(최대/최소)값을 swap한다. 가장 앞 데이터 위치를 변경함으로(index를 ..

버블정렬 데이터의 인접 요소 끼리 비교하고 Swap 연산을 수행하여 정렬한다. 장점 다른 정렬 알고리즘에 비해 정렬 시간은 다소 오래걸리지만, 상대적으로 로직이 단순하고 구현이 쉽다. 핵심이론 인접한 데이터 크기를 비교하여 정렬 간단하게 구현 가능 n²의 시간복잡도를 갖음 ( 다른 정렬 알고리즘 보다 느림) n² 시간복잡도 원리 loop 1회 도는데 n의 시간복잡도를 가진다 예를들어 n = 5 일때 5개의 데이터를 5회 동안 loop를 돌면서 비교하므로 5 * 5 는 5² 이 된다. (loop 1회당 정렬된 데이터 1개씩 추가 = 정렬할 데이터가 1개씩 감소) 버블정렬 과정 비교 연산이 필요한 루프 범위를 설정한다. (데이터의 갯수만큼 반복해야한다.) 인접한 데이터끼리 비교한다. Swap 조건에 부합할 ..