유혁스쿨

그래프의 표현 그래프를 표현할때는 대표적으로 엣지리스트, 인접행렬, 인접리스트 3가지 방법으로 표현한다. 그래프 예 ① → ② → ⑤ ↓ ↓ ↗ ③ → ④ 엣지리스트 엣지를 중심으로 그래프를 표현한다. 배열에 출발,도착 노드를 각각 저장하여 엣지를 표현한다. 가중치가 있는 노드의 경우 배열에 가중치를 추가 행으로 함께 저장한다. 가중치 없는 그래프 표현 출발, 도착 2개의 노드만 2개의 배열행을 구성하여 표현한다. ex) 첫번째 행을 [1, 2]로 표현하며 1에서 2로 뻗어가는 엣지를 뜻한다. ⓢ ⓔ 1 2 1 3 3 4 2 4 2 5 4 5 이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현한다. 노드를 배열에 저장하여 엣지를 표현하므로 엣지리스트 라고 한다. 방향이 없는 그..

그래프 노드와 엣지로 구성된 집합. 예) 트리 노드 데이터 표현 단위 엣지 노드를 연결할 때 사용 그래프 알고리즘 종류 유니온 파인드 위상 정렬 다익스트라 벨만-포드 플로이드-워셜 최소 신장 트리 유니온 파인드 그래프의 `사이클 생성 유무`를 판단하는 알고리즘 그래프에서만 쓰이는 알고리즘은 아님 사용 예) `집합에서 대표 노드 탐색` 혹은 `각 원소들을 유니온 하여 하나의 집합으로 통합` 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(); // 재귀 함수 } } 위와 같은 재귀 함수..

Node.js (노드) 크롬 V8 자바스크립트 엔진으로 빌드된 자바스크립트 런타임 환경(플랫폼) 2008년 크롬 웹브라우저가 출시되면서 자바스크립트의 속도가 점차 빨리지게 되었고, 이에 자바스크립트를 웹 브라우저가 아닌 곳에서 쓸 수 있게 만들자는 의견에 의해 CommnJS표준이 작성되었고, Node.js는 CommonJS표준에 맞춰 크롬 V8엔진을 기반으로 개발된 플랫폼 환경이다 주로 서버측 프로그래밍에서 사용되며 비동기 이벤트 기반의 단일 스레드 모델을 사용하여 효율적으로 네트워크 애플리케이션을 개발할 수 있도록 지원한다. Node.js를 사용하면 웹 브라우저가 아닌 곳에서 자바스크립트로 프로그램을 개발할 수 있다. JAVA Spring 진영에서의 Tomcat(내/외장) 서버와 비슷한 역할을 해준다...

public class LinkedList /* extends 생략 */ { /* 기타 멤버 생략 */ private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } } 위와 같이 자바 컬렉션 LinkedList의 내부를 보면 Node 중첩 클래스를 확인할 수 있다. Node 클래스 설계 궁금증 중첩(내부) 클래스 Node 클래스는 LinkedList에서만 사용하기 위해 LinkedList의 중첩 (내부)클래스로 구현함으로써 LinkedList의 순기능으로 높은 응집도를 갖게 된다. s..

기수정렬 (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의 데이터 보다 ..