비망노트

✅ 선택정렬 ( 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로 어버버 하며 어찌저찌 풀어오던 정렬파트를 다시 만나게되었다. 정렬 알고리즘은 알고리즘을 이해하고 구현함에 있어 반드시 알아야하는 파트이기때문에 이전처럼 답만맞으면 되지 하고 넘어갈게아니고 필수개념이므로 정리 할 필요를 느껴 차근차근 이해해나가보려고 한다. 우선 그 전에 수포자인 나는 정렬알고리즘을 검색하고 찾아볼때마다 함께 따라나오는 시간복잡도를 볼때마다 갑자기 할마음이 식었다.. 그래도 뭐 별수 있겠는가 해야지 그럼 정렬 알고리즘을 하나하나 이해해보기전에 시간복잡도부터 이해하고 넘어가자. ✅ 시간복잡도 🚩시간복잡도 : 알고리즘이 결과를 도출하는데 얼마나의 시간이 걸리는 지에 대한 값으로 좋은 프로..

문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2..

문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8..