유혁스쿨

삽입 정렬 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식으로 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가..

시간복잡도란? 알고리즘 선택의 기준 주어진 문제를 해결하기 위한 '연산 횟수' 일반적으로 수행시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측 ex) 시간제한 2초라고 가정한다면 2억 번의 연산 안에 도출 시간 복잡도 유형 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅-세타(Θ(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 public class timeComplexityEx01 { public static void main(String[] args) { int findNumber = (int)(Math.random() * 100); for(int ..

문제 설명 정수 n과 정수 배열 numlist가 매개변수로 주어질 때, numlist에서 n의 배수가 아닌 수들을 제거한 배열을 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ n ≤ 10,000 1 ≤ numlist의 크기 ≤ 100 1 ≤ numlist의 원소 ≤ 100,000 입출력 예 n numlist result 3 [4, 5, 6, 7, 8 ,9, 10, 11, 12] [6, 9, 12] 5 [1, 9, 3, 10, 13, 5] [10, 5] 12 [2, 100, 120, 600, 12, 12] [120, 600, 12, 12] 입출력 예 #1 numlist에서 3의 배수만을 남긴 [6, 9, 12]를 return합니다. 입출력 예 #2 numlist에서 5의 배수만을 ..

문제 설명 정수 n이 매개변수로 주어질 때, n 이하의 홀수가 오름차순으로 담긴 배열을 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ n ≤ 100 입출력 예 n result 10 [1, 3, 5, 7, 9] 15 [1, 3, 5, 7, 9, 11, 13, 15] 입출력 #1 10 이하의 홀수가 담긴 배열 [1, 3, 5, 7, 9]를 return합니다. 입출력 #1 15 이하의 홀수가 담긴 배열 [1, 3, 5, 7, 9, 11, 13, 15]를 return합니다. [나의 풀이] import java.util.stream.IntStream; class Solution { public int[] solution(int n) { return IntStream.rangeClosed(..

문제 설명 순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ n ≤ 1,000,000 입출력 예 n result 20 6 100 9 입출력 예 #1 n이 20 이므로 곱이 20인 순서쌍은 (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1) 이므로 6을 return합니다. 입출력 예 #2 n이 100 이므로 곱이 100인 순서쌍은 (1, 100), (2, 50), (4, 25), (5, 20), (10, 10), (20, 5), (25, 4), (50, 2), (100, 1) 이므..

문제 설명 어떤 자연수를 제곱했을 때 나오는 정수를 제곱수라고 합니다. 정수 n이 매개변수로 주어질 때, n이 제곱수라면 1을 아니라면 2를 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ n ≤ 1,000,000 입출력 예 n result 144 1 976 2 입출력 예 #1 144는 12의 제곱이므로 제곱수입니다. 따라서 1을 return합니다. 입출력 예 #2 976은 제곱수가 아닙니다. 따라서 2를 return합니다. [나의 풀이] class Solution { public int solution(int n) { return Math.sqrt(n) % 1 == 0.0 ? 1 : 2; } } Math 라이브러리에서 제곱근을 구하는 sqrt를 활용하였다. sqrt의 반환타입은 ..

문제 설명 정수 리스트 num_list와 정수 n이 주어질 때, num_list의 첫 번째 원소부터 n 번째 원소까지의 모든 원소를 담은 리스트를 return하도록 solution 함수를 완성해주세요. 제한사항 2 ≤ num_list의 길이 ≤ 30 1 ≤ num_list의 원소 ≤ 9 1 ≤ n ≤ num_list의 길이 ___ 입출력 예 num_list n result [2, 1, 6] 1 [2] [5, 2, 1, 7, 5] 3 [5, 2, 1] 입출력 예 #1 [2, 1, 6]의 첫 번째 원소부터 첫 번째 원소까지의 모든 원소는 [2]입니다. 입출력 예 #2 [5, 2, 1, 7, 5]의 첫 번째 원소부터 세 번째 원소까지의 모든 원소는 [5, 2, 1]입니다. [나의 풀이] import java...

호이스팅 function sayHello () { console.log("Hello!") } sayHello(); sayHello(); sayHello(); sayHello(); function sayHello (name) { console.log("Hello my name is " + name) } sayHello("YooHyeokSchool"); sayHello("DoubleDoorStone"); sayHello("YooHyeokChoi"); sayHello("UrekMazino"); 위와 같은 함수선언식 방식의 재정의 코드가 있다고 가정했을때 해당 함수를 호출한다면 기대하는 출력의 예는 아래와 같다. 하지만 실제 출력은 아래와 같이 출력된다. 이는 자바스크립트 엔진에 의해 선언된 변수와 함수를 최상..