유혁스쿨

소수란? 자신보다 작은 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에서만 사용하기 ..

기수정렬 (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 조건에 부합할 ..

스택과 큐 배열에서 발전된 형태의 자료구조로 두 자료구조의 구조는 서로 비슷하지만 처리방식이 다르다 스택 (Stack) 삽입 / 삭제 연산이 후입선출 LIFO (LastInFirstOut) 형태로 이루어지는 자료구조이다. LIFO : 마지막에 삽입된 값이 가장 먼저 삭제된다 FILO라고도 부른다 (최초 삽입 데이터가 가장 마지막에 삭제된다) 삽입 삭제가 한쪽에서만 발생한다. (입구와 출구가 하나) 스택에 새 값 삽입(PUSH)시 TOP은 새 값을 가리킨다. 스택에서 값 삭제(POP)시 TOP이 가리키는 값을 삭제한다. 결과적으로 스택에서 값을 삭제할경우 현재 시점에서 가장 마지막에 삽입된 값이 삭제된다. TOP : 삽입 / 삭제가 발생하는 위치 (스택에서는 최 상단에 위치한다.) PUSH : TOP 위치..