일단해

기수정렬(Radix Sort) 기수정렬 개념, 기수정렬이란?숫자의 각 자릿수(기수)를 기준으로 정렬하는 알고리즘으로 낮은자리(1의자리)부터 시작해 높은 자리 순으로 버킷에 분류하여 넣고 다시 합치는 방식으로 정렬한다.실제로 숫자들간의 비교를 통해 정렬을 하는것이 아닌, 자리를 의미하는 0~9까지의 버킷이 있고 이 버킷에 자릿수를 넣어가며 분류한다. 기존의 정렬 순서가 유지되는 안정정렬이다. 그림으로 이해하기 시간 복잡도최선/최악O(r*n) r : 숫자의 자릿수n : 정렬될 수의 갯수 장단점 (사용하면 좋은/나쁜 상황)장점시간복잡도에서 엄청난 이점을 갖는다. 즉 속도가 빠르다이는 인자들을 비교하지않고 자릴수를 기준으로 정렬하기 때문이다.이론상 O(n log n)을 넘을 수 없는 알고리즘이다.안정..

병합정렬(Merge Sort) 병합정렬 개념, 병합정렬이란? 병합정렬은 안정정렬에 속하며 분할 정복 알고리즘 중 하나이다. (분할정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략으로 순환 호출을 이용하여 구현한다) 하나의 문제를 두 개의 균등한 크기로 분할하고 분할된 작은문제들을 정렬한다. 그렇게 정렬된 부분리스트를 최종적으로 병합하여 전체가 정렬된 리스트가 되게하는 방법이다. 각 문제는 크기가 1이 될때까지 재분할하여 정렬을 시도한다. 보통 재귀함수로 구현된다. 그림으로 이해하기 시간 복잡도참고 https://rosweet-ai.tistory.com/52최고/최악O(nlog₂n) 장단점 (사용하면 좋은/나쁜 상황)장점안정 정렬방법으로..

퀵정렬(Quick Sort)https://youtu.be/8hEyhs3OV1w?si=sVFYYhCKw2J13kHx 퀵정렬 개념, 퀵정렬이란?퀵정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다. 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 보이는 정렬방법이다. 퀵정렬은 주어진 배열에서 하나의 원소(pivot)를 선택한다. 그 다음 배열의 모든 원소를 검사하면서 pivot 보다 작은 값을 pivot의 왼쪽에 , 큰값을 pivot의 오른쪽에 배치한다. 이렇게하면 배열이 두개로 나뉘는데, 두개로 나뉜 배열에서 각각 새로운 pivot을 선택해 동일한 작업을 반복한다. 배열을 더이상 쪼갤 수 없을 때, 즉 크기가 0이나 1이 될 때까지 반복한다. pivot에..

삽입정렬(Insertion Sort) 삽입정렬 개념, 삽입정렬이란? 배열의 모든 원소를 앞에서부터 차례대로 이미 정렬된 배열 원소들과 비교하여, 자신의 위치를 찾아 삽입하는 정렬알고리즘이다.즉 2번째 원소부터 시작하여 앞 쪽의 원소와 비교해 해당 원소가 삽입될 위치를 찾는다. 좀 더 쉽게 설명하면, 삽입정렬은 배열하나를 두개의 부분집합으로 나눈다. 하나는 '정렬된 앞 쪽 집합'(S), 나머지 하나는 '정렬되지 않은 뒷 쪽 집합'(U)이다. 차례가 한번씩 지날 때마다 S의 원소는 하나씩 늘어나고, U의 원소는 하나씩 줄어든다. 그러다 U가 공집합이 되면 삽입 정렬이 끝난다. Stable sorting, in-place 알고리즘이다. 그림으로 이해하기시간 복잡도최악O(n^2)입력 자료가 역순인 경우최선O..

선택정렬(Selection Sorting) 선택정렬 개념, 선택정렬이란?제자리 정렬(in-place sorting) 알고리즘 중 하나로, 입력된 원소들 외에 다른 메모리를 추가로 요구하지 않는다. 매 순서마다 원소를 넣을 위치는 정해져있고, 그 위치에 어떤 원소를 넣을것인지 찾아서 선택하는 알고리즘이다. 즉 오름차순일 경우, 이미 정해진 위치인 '배열의 0번째 방'에 가장 작은 원소를 넣기로한다. 정렬되지 않은 원소들을 탐색하여 0번째 방에 들어갈 가장 작은 수를 선택한 다음, 가장 앞쪽에 있는 원소와 0번째 방에 있는 원소를 교환한다. 그림으로 이해하기 시간 복잡도O(n^2)최악, 최선, 평균 모두 동일함. 장단점 (사용하면 좋은/나쁜 상황)장점동일한 시간복잡도를 가진 버블정렬보다 교환횟수가 ..

버블정렬(Bubble sort) 버블정렬의 개념, 버블정렬이란?정렬시, 원소가 이동하는 모습이 거품이 수면위로 올라오는 듯한 모습과 같다고해서 붙여진 이름으로인접한 두 개의 원소를 비교하여 자리를 교환하는 방법으로 교환정렬의 일부에 속한다. 버블정렬로 정렬을 할 때는 원소의 갯수만큼 순회를 하게된다. 오름차순일 경우 1회차때는 가장 큰수, 2회차때는 두번채로 큰수. 이런식으로 가장 큰수부터 자기 자리를 찾아간다. 따라서 회차를 거듭할수록 1회씩 정렬의 횟수가 적어진다. 자기자리를 찾은 원소는 정렬할 필요가 없기때문이다. 그림으로 이해하기 시간 복잡도O(n^2)최악, 최선, 평균일 경우 모두 동일한 시간복잡도를 가진다.중간에 정렬이 완성되었어도 마지막까지 모든 비교가 수행되기 때문이다. 장단점 (사용..

정렬 알고리즘(Sorting Algoritm) 정렬 알고리즘을 소리로 표현한 유튜브 영상https://www.youtube.com/watch?v=kPRA0W1kECg https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 정렬 알고리즘정렬 알고리즘을 소리로 표현한 영상이다. 최신판인 0.6.5버전 을 다운로드 받으면 위키 정렬등이 포함된 총 30namu.wiki* 나무위키에 정렬알고리즘에 대한 정리가 잘되어있다. 정렬 알고리즘이란? '데이터 목록을 특정한 순서대로 재배치하는 알고리즘'주어진 데이터들을 요청하는 순서대로 정렬하는 알고리즘으로 '5 3 2 1 6 7' 이라는 각 숫자를 오름차순으로 정렬하라는 요청이 들..

https://yoongrammer.tistory.com/81#%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90_(Priority_Queue)_%EA%B0%9C%EB%85%90_%EB%B0%8F_%EA%B5%AC%ED%98%84

좌표데이터를 정렬할 때 편리하게 사용되는 클래스 Comparable과 Comparable의 메서드 compareTo가 있다. 먼저 간단한 좌표정렬 문제와 풀이를 확인하자. 문제 : 백준 11651 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 예제 입력 5 0 4 1 2 1 -1 2 2 3 3 예제출력 1 -1 1 2 2 2 3 3 0 4 문제는 x, y 데이터가 주어지면 1. 먼저 y값이 증가하는순으로 데이터를 정렬하고 2. y값이 동일한 경우에는 x값이 증가하는 순으로 데이터를정렬 하는 것이다. 아래는 Comparable 클래스와 compareTo(Object o)메서드를 사용한 풀이다. ..

재귀함수가 진행되는 과정은 별로 어렵지 않다. 원리자체는 쉽지만 조건이 추가되면 어려워진다. 복잡해진다는말이 더 맞겠다. Algorithm 문제풀이는 어렵다. DFS, BFS공부를 시작하고나서부터 과연 내가 이해하고 적용하며 적응 할 수있을지 걱정이 된다. 하지만, 언제나 그랬듯이 결국엔 잘하게 될 나를 믿는다. 무언가를 처음시작할 때마다, 걱정이 무색하게도 처음과 끝의 나는 달라져있었고, 꽤나 만족스러운 끝을 경험할 수 있었던 것은 시작의 무게를 버텨냈기 때문이다. 그러니까 쫄지말고 끝까지 하면된다. 공부든, 취업이든, 운동이든, 일이든, 뭐든. 쫄지말고, 그냥, 할일을 하자. 그날 그날, 순간 순간을 버티자. 재귀함수 : 재귀함수는 끝 날때까지, 자기 자신을 반복하여 호출한다. 반복문의 역할을 하는 ..