유혁스쿨

너비 우선 탐색 - 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 위치..

구간 합 합 배열 을 이용하여 시간 복잡도를 더 줄이기 위한 특수 목적 알고리즘 합 배열 배열에서 특정 범위에 존재하는 요소의 합 합 배열 정의 S [ i ] = A [ 0 ] + A [ 1 ] + ...... + A [ i - 1 ] + A [ i ] ex) i가 4일 때 합 배열 = A [ 0 ] ~ A [ 4 ] 까지의 합 쉽게말해 누적합을 말한다. 합 배열 공식 S [ i ] = S [ i - 1 ] + A [ i ] 구간합 공식 배열 인덱스 i 부터 인덱스 j 까지의 합 S [ j ] - S [ i - 1 ] ex) 2 ~ 5까지의 합 = S [ 5 ] - S [ 1 ] 배열 A 의 0 ~ 1까지의 합은 3 + 9 = 12 이다. 배열 A 의 2 ~ 5까지의 합은 5 + 10 + 4 + 8 = ..

배열 연속적인 메모리 공간에 값이 채워져 있는 자료구조이다. 인덱스를 통해 값 참조가능 새로운 값 삽입/특정 인덱스값 삭제 어려움 삽입/삭제시 해당 인덱스 주변 값 이동과정 필요 배열 선언시 크기 지정 가능 (최초 길이 수정 불가) 배열 요소 초기화시 길이는 필수이다 int[ ] a = new int[ ] { }; 와 같이 배열 선언시 빈 배열로 길이를 지정하지 않는다면 배열 초기화 (삽입) 시 길이가 지정된 새 배열 인스턴스로 a 배열을 초기화 해야한다. → a = new int [n]; 간단한 구조 이므로 코딩테스트에서 주로 사용된다. 배열 삽입 배열 삭제 배열에서 요소를 삭제하더라도 배열의 길이는 줄어들지 않는다. (삽입과 삭제한 요소의 갯수만큼 줄어든 길이만큼의 배열을 새로 생성해서 삭제된 이후 ..

디버깅이란? 코드의 논리 오류를 잡을때 사용하는 방법중 하나로 가장 뛰어난 오류 탐색법이라고 할 수 있다. 디버깅이 중요한 이유 log로 찍어보는것보다 훨씬 빠르고 간편하다. 코딩테스트 오답 예 index 범위 1차이로 인한 오답 int -> long 변환 - 정수 타입의 범위로 인한 오답 ★ 디버깅 하는 법 1. 코드에서 디버깅 하고자 하는 줄에 중단점(break point)을 설정한다. 2. IDE 디버깅 기능을 실행한다. (이때 여러개의 중단점 설정이 가능하다.) 디버그 기능 Step Over : 해당 Point에서 다음 라인으로 한줄 씩 이동 Step Into : 해당 Point에서 메소드 호출 시 해당 메소드 내부를 1줄씩 탐색 Resume : 다음 Point로 건너 뛴다 (예를들어 point가..