00. 알고가기: 자료구조의 분류 01. 선형리스트(연결리스트) - 가장 단순한 구조, 데이터를 순서대로 나열해 놓은 자료구조 - 이야기 전달방식 : 한 사람을 건너뛰어 전달 할 수 없다. ▶︎ 노드(요소) : 머리, 꼬리/ 앞쪽, 다음 - 데이터 - 포인터 : 다음 노드를 가리킨다 - [그림 9-2]에서 노드 C의 앞쪽 노드는 B, 다음 노트는 D이고 노드 C가 갖는 포인터는 다음 노드 D를 가리킨다. ▶︎ 배열로 선형 리스트 만들기 - 다음 노드 꺼내기 : 1만큼 큰 인덱스를 갖는 요소에 접근 - 노드의 삽입과 삭제 : 회원번호 55인 회원을 12,33 사이에 삽입하기 위해 삽입요소 다음의 모든 요소를 하나씩 뒤로 밀어야 한다. 배열로 구현한 선형리스트의 문제 1. 쌓이는 데이터의 크기를 미리 알아야..
병합정렬(merge sort) 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘 퀵정렬과 유사하지만 퀵정렬은 내부정렬, 병합정렬은 외부정렬(외부에 추가적인 배열를 선언하여 정렬)으로 차이가 있다. 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다 배열을 앞부분과 뒷부분으로 나눈다 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있다. 이때 앞뒤에 놓인 배열을 정렬할 때는 그냥 정렬하는 것이 아니라 다시 병합 정렬을 이용한다. ▶︎ 가장 먼저 정렬을 마친 배열의 병합을 보면, 각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬을 마치는 것을 ..
퀵 정렬 가장 빠른 정렬 알고리즘 중의 하나로, 퀵 이라는 이름 역시 정렬 속도가 매우 빠르다는 점에서 착안 아래 이미지처럼, 피벗을 기준으로 그룹을 나눠 각각의 그룹에 값이 1개씩만 들어가면 정렬이 종료된다. * 피벗: 그룹을 나누는 기준 ✔️ 배열을 두 그룹으로 나누기 피벗이 될 요소를 선택한다. 피벗보다 작은 요소와 큰 요소로 나눠 그룹으로 묶는다. 배열의 수가 홀수개인 경우에, 동일한 요소(피벗)을 교환하는 시도가 생긴다. → 이 의미 없어보이는 시도가 매번 이뤄져야하는 양 끝에서 움직이는 인덱스의 위치가 서로 동일한 위치인지에 대한 검사를 없애준다. ✔️ 스택의 용량 요소의 개수가 적은 배열일수록 적은 횟수로 분할을 종료 스택에 넣고 꺼내는 횟수는 같지만, 스택에 쌓이는 데이터의 최대 개수는 다..
셸정렬 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘. 안정적인 알고리즘은 아니며 퀵 전까지는 가장 빠른 알고리즘 이었다. 시간복잡도 = O(n^(1.3,1.5)) 1. 개념 ✔️ 퀵 정렬이 고안되기 전까지는 가장 빠른 알고리즘으로 알려져 있었다. ✔️ 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행한다. ✔️ 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄인다. 1. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류 2. 연속적이지 않은 여러 개의 부분 리스트를 생성 3. 각 부분 리스트를 삽입 정렬을 이용하여 정렬 4. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복 5. 위의 ..
for문, while문을 이용할 수 있는데 왜 재귀함수를 사용하는가? 1. 재귀함수를 쓰는 이유 1. 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때 (가독성) 2. 변수 사용을 줄여 프로그램 오류 가능성을 줄여준다. 1번은 말 그대로 재귀적으로 표현하는 코드가 알맞은 경우를 의미한다. 2번의 경우, 변수 사용을 줄여준다는 건 변수가 잡는 메모리에 대한 이야기가 아니라(재귀함수는 메모리를 많이 차지하며 반복문에 비해 성능이 느리다.) mutable state(변경가능한 상태)를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄인다는 이야기다. 그렇다면 앞서 말한 재귀함수의 "메모리를 많이 차지하며 반복문에 비해 성능이 느리다"는 문제점을 해결하기 위해서는 어떻게 해야 할까. 2. 재귀함수의 문제점 ..
1. 단순 선택 정렬 straight selection sort 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 ▶︎ 단순 선택 정렬의 교환 과정 아직 정렬하지 않은 부분에서 가장 작은 키의 값을 선택한다. 선택한 값과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다. 1-2번의 과정을 n - 1회 반복한다. package com.study.Algorithm; import java.util.Scanner; // 단순 선택 정렬 class SelectionSort { // 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다. static void swap(int[] arr, int idx1, int idx2) { int temp = arr[idx1]; arr[idx1] ..
