비망노트

✅ 삽입정렬 ( Insertion Sort ) 삽입정렬은 버블 정렬의 비효율성을 개선하기위한 방법으로 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 정렬방식이다. 한 데이터씩 비교해 적절한 위치에 들어가기 이전에, 해당 데이터의 앞에 있는 데이터들은 이미 정렬되었다고 가정하며 그렇게 정렬되어있는 데이터리스트에서 적절한 위치를 찾고 해당위치에 삽입된다. 마찬가지로 데이터외의 추가공간을 필요로 하지않기때문에 '제자리정렬' 이기도 하다. 📌 정렬과정 1. 초기데이터배열이 주어진다. 2. 현재 타겟의 값과 이전위치들의 원소들을 비교한다 ( 첫 타겟은 두번째 원소부터 시작한다 ) 3. 타겟의 값이 이전위치의 원소보다 작다면 위치를 교환한다. 4. 이전위치의 원소가 타겟보다 작을때까지 혹은 더이상 ..

✅ 선택정렬 ( Selection Sort ) 선택정렬은 거품정렬과 마찬가지로 O(n^2)의 시간복잡도는 가지고 구현이 간단하다. 하지만 제일큰 원소를 뒤로보내며 끝인덱스부터 정렬하는 방식인 거품정렬과 다르게 제일 앞인덱스부터 정렬한다. 데이터를 '비교'하고 그중 가장 최소값을 가진 원소와 위치를 '교환'하기 때문에 교환횟수가 적다. 마찬가지로 데이터외의 추가공간을 필요로 하지않기때문에 '제자리정렬' 이기도 하다. 📌 정렬과정 1. 초기데이터배열이 주어진다. 2. 제일 첫 인덱스부터 배열의 끝까지 돌며 최소값을 가진 인덱스를 찾는다. 3. 최소값을 가진 인덱스와 첫인덱스의 위치를 교환한다. 4. 제일첫 인덱스는 정렬된 상태이므로 다음인덱스를 최소값과 교환하며 반복해나간다. 초기 데이터배열이 주어진다. 1..

✅ 거품정렬 ( Bubble Sort ) 알고리즘의 실행시간이 입력크기의 제곱에 비례하는 O(n^2)의 시간복잡도는 가지는 거품정렬은 구현이 간단한 정렬알고리즘이지만 속도가 느린편이며 선택정렬과 시간복잡도를 가지지만 데이터 교환횟수가 상대적으로 많다. 거품정렬은 데이터를 '비교' 하며 찾기때문에 '비교정렬'이며 정렬대상인 데이터외에 추가적인 공간을 필요로하지 않기때문에 '제자리정렬'이기도 하다. 데이터를 교환하는 과정에서 temp(임시변수)가 필요하긴하지만 적은양이기에 제자리정렬로 볼 수 있다. 📌 정렬과정 1. 초기데이터배열이 주어진다. 2. 제일 앞부터 해당원소와 다음원소를 비교한다. 3. 두 원소 중 현재원소가 다음원소의 값보다 더 크다면 두원소의 자리를 바꾼다. 4. 다음원소로 이동해 현재원소와 ..

✅ 정렬 알고리즘 버블정렬 ( Bubble Sort ) 선택정렬 ( Selection Sort ) 삽입정렬 ( Insertion Sort ) 합병정렬 ( Merge Sort ) 퀵정렬 ( Quick Sort ) 힙정렬 ( Heap Sort ) 셸정렬 ( Shell Sort ) 계수정렬 ( Counting Sort ) 정렬 알고리즘은 시간복잡도에 따라 분류 할 수 있으며 가장 기본적인 정렬이 O(n^2)의 시간복잡도를 가지는 버블정렬, 선택정렬, 삽입정렬이다. 이 정렬방식들은 모두 중첩반복문을 통해 정렬된다는 공통점이 있고, 반복도중 정렬이 완성된다 하더라도 주어진 반복문을 끝까지 실행해야 종료되는 정렬방법이다. 다음은 위의 반복문보다 좀 더 빠르고 효율적인 O(n log n)의 시간복잡도는 가지는 알고리..

근 2달동안 java언어의 기초와 더불어 백준 알고리즘문제를 풀어오고있었는데 결국 1년전에 node.js로 어버버 하며 어찌저찌 풀어오던 정렬파트를 다시 만나게되었다. 정렬 알고리즘은 알고리즘을 이해하고 구현함에 있어 반드시 알아야하는 파트이기때문에 이전처럼 답만맞으면 되지 하고 넘어갈게아니고 필수개념이므로 정리 할 필요를 느껴 차근차근 이해해나가보려고 한다. 우선 그 전에 수포자인 나는 정렬알고리즘을 검색하고 찾아볼때마다 함께 따라나오는 시간복잡도를 볼때마다 갑자기 할마음이 식었다.. 그래도 뭐 별수 있겠는가 해야지 그럼 정렬 알고리즘을 하나하나 이해해보기전에 시간복잡도부터 이해하고 넘어가자. ✅ 시간복잡도 🚩시간복잡도 : 알고리즘이 결과를 도출하는데 얼마나의 시간이 걸리는 지에 대한 값으로 좋은 프로..

- 재귀 ( Recursion ) 재귀함수란? 자기자신을 다시 호출해 작업을 수행하는 것 이라고 할 수 있다. 주의해야할점은 자기자신을 계속 반복해서 호출하기때문에 해당 함수안에 기반조건을 구현해두어야한다. public int factorial(int x){ factorial(x); } 이런식으로 작성하게 된다면 무한반복이 불가피한 상황이 된다. 그래서 기저조건이 필요하다. 기저조건( Base case ) 위의 경우 계속 자기자신을 호출하게되므로 if문을 활용해 기저조건을 판별해내야한다. 간단하게 입력값에대한 factorial을 구하는 코드를 보자. public int factorial(int x){ if(x==0){ return 1; }else{ return x * factorial(--x); } } ..

- 자바 반복문 ( while ) 반복문이란? 특정 작업을 반복해서 수행해야할 경우 해당작업 실행코드를 여러번 작성하는게 아닌 반복문을 사용해 해결할 수 있으며 반복문의 종류로는 for문, while문이 대표적이며 whlie문을 알아보도록하자. while int i = 0; // 반복문을 제어할 변수 초기화 while(i

- 자바 반복문 ( for ) 반복문이란? 특정 작업을 반복해서 수행해야할 경우 해당작업 실행코드를 여러번 작성하는게 아닌 반복문을 사용해 해결할 수 있으며 반복문의 종류로는 for문, while문이 대표적이며 for문부터 알아보도록하자. for for(초기화; 조건식; 증감식){ 실행문; } ✅ 우선 for문을 반복횟수를 알고있을때 더 적합한 반복문이다. 초기화 : for문이 실행될 때 처음 한번만 실행되며 같은타입이라면 둘이상의 변수를 가질 수 있다. 조건식 : 해당 조건이 참이라면, 참인동안 반복해서 실행한다. 증감식 : 조건식의 조건이 false가 될때까지 초기화된 변수를 증가하거나 감소시킨다. for(int i=0;i

- 자바 조건문 ( switch - case ) 조건문이란? 조건에 따라 코드의 실행 흐름을 다르게 동작하도록 제어하는 기능을 함 조건문의 종류로는 if문과 switch문 두가지가 있다. 우선 이번포스팅에서는 switch문을 다뤄보자. switch - case switch (조건식) { case 1 : 실행문; break; case 2 : 실행문; break; case 3 : 실행문; break; default : 실행문; } ✅ default 는 if문의 else와 같은느낌으로 '그 밖의 다른경우' 에 실행된다 ❗ switch문은 if문과 다르게 제약조건이 있는데 switch문의 조건식은 반드시 결과값이 정수 또는 문자열 이어야하며 case문의 값 역시 정수,상수 이어야하고 변수,실수,문자열은 불가능하..

- 자바 조건문 ( if, else if, else ) 조건문이란? 조건에 따라 코드의 실행 흐름을 다르게 동작하도록 제어하는 기능을 함 조건문의 종류로는 if문과 switch문 두가지가 있다. 우선 이번포스팅에서는 if문을 다뤄보자. if, else if, else if (조건식) { 실행문; } else if (조건식) { 실행문; } else { 실행문; // if도 else if도 아닌 그밖의 다른 경우 } ✅ 조건식의 내용이 true일때 실행문을 작동시킨다. - 조건식 : 관계연산자(>,, (+)8 즉 +8 양수가되는것이고 양수값을 넣었다면 0보다 작..