전체 글

[자료 구조와 알고리즘] 정렬 - 퀵 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 정렬 - 퀵 정렬 📍 퀵 정렬(Quick Sort) 👉🏻 병합 정렬과 같이 분할 정복 알고리즘에 속함 👉🏻 즉, 재귀를 사용함 피벗 _ [5, 3, 7, 2, 6, 4, 9, 1, 8] // 배열 중 하나를 피벗으로 설정 // 이해하기 쉽게 여기서는 제일 왼쪽 값을 피벗으로 설정 _ leftStartIndex _ rightStartIndex [5, 3, 7, 2, 6, 4, 9, 1, 8] _ _ left right // leftStartIndex는 왼쪽에서 오른쪽으로 이동하다가 피벗보다 큰 수가 있으면 멈춤 // rightStartIndexs는 오른쪽에서 왼쪽으로 이동하는데 피벗보다 작은 수가 있으면 멈춤 // 둘 다 멈추면 값을 교환 피벗 _ _ _ [5..

[자료 구조와 알고리즘] 정렬 - 병합 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 정렬 - 병합 정렬 📍 병합 정렬(Merge Sort) 👉🏻 다른 정렬보다는 조금 복잡함 👉🏻 분할 정복(divide and conquer)을 이용할 것 [3, 5, 2, 4, 1, 7, 8, 6] // 한 번에 8개의 원소를 정렬하기 어려우니까 반으로 쪼개서 먼저 생각함! [3, 5, 2, 4] [1, 7, 8, 6] // 또 반으로 쪼개면 더 편하지 않을까? [3, 5] [2, 4] [1, 7] [8, 6] // 또 쪼개면? [3] [5] [2] [4] [1] [7] [8] [6] // 정렬이 필요 없을 정도로 단순해짐! // 이제 순서대로 병합! [3, 5] [2, 4] [1, 7] [6, 8] // 각 배열의 두 개의 원소는 모두 정렬됨! [2, 3,..

[자료 구조와 알고리즘] 정렬 - 삽입 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 정렬 - 삽입 정렬 📍 삽입 정렬(Insertion Sort) 👉🏻 배열을 두 영역으로 나누어 진행(정렬된/되지 않은 영역) [4, 1, 5, 3, 6, 2] // 정렬되지 않은 영역에서 데이터를 꺼내 정렬된 영역 사이에 삽입 [4, 1, 5, 3, 6, 2] // 첫 번째 숫자인 4만 정렬되어 있다고 가정 _ _ [4, 1, 5, 3, 6, 2] // 정렬되지 않은 영역 데이터 1을 정렬된 데이터 4와 비교한 뒤, 4보다 작으므로 삽입 [1, 4, 5, 3, 6, 2] [1, 4, 5, 3, 6, 2] // 정렬되지 않은 영역 데이터 5를 정렬된 데이터의 가장 오른쪽부터 비교 [1, 4, 5, 3, 6, 2] [1, 4, 5, 3, 6, 2] // 정렬되지..

[자료 구조와 알고리즘] 정렬 - 선택 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 정렬 - 선택 정렬 📍 선택 정렬(Selection Sort) 👉🏻 배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가지고 옴 [6, 3, 4, 1, 2, 5] // 정렬되지 않은 영역(전체)를 순회 후 가장 작은 값 찾음: 1 _ _ [1, 3, 4, 6, 2, 5] // 가장 작은 값을 첫 번째 원소로 가지고 옴 // 1은 정렬 완료 [1, 3, 4, 6, 2, 5] // 순회 후 가장 작은 값 찾음: 2 _ _ [1, 2, 4, 6, 3, 5] // 가장 작은 값을 첫 번째 원소로 가지고 옴 // 2까지 정렬 완료 [1, 2, 4, 6, 3, 5] // 순회 후 가장 작은 값 찾음: 3 _ ..

[자료 구조와 알고리즘] 정렬 - 버블 정렬

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 정렬 - 버블 정렬 📍 버블 정렬(Bubble Sort) 👉🏻 가장 쉽게 생각할 수 있는 정렬 중 하나로 구현이 쉬우나 성능이 좋지는 않음 [4, 2, 3, 1] // 앞에 있는 숫자와 그 뒤의 숫자를 비교해서 조건에 따라 자리를 바꿈 _ _ [2, 4, 3, 1] _ _ [2, 3, 4, 1] _ _ [2, 3, 1, 4] // 4(마지막 원소) 자리가 고정되었음(정렬 완료) _ _ [2, 3, 1] // 배열 유지 _ _ [2, 1, 3] // 3(마지막 원소) 자리가 고정되었음 _ _ [1, 2] // 남은 원소는 1 하나이므로 정렬 끝 📍 버블 정렬의 구현 [ bubble_sort.mjs ] function BubbleSort(arr) { // 배열이..

[자료 구조와 알고리즘] 재귀 - 하노이 탑

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 재귀 - 하노이 탑 📍 하노이 탑 👉🏻 세 개의 기둥과 서로 다른 크기의 원반들이 있음 👉🏻 가장 큰 원반이 아래 있고, 위로 갈수록 작은 원반으로 이루어짐 👉🏻 다른 기둥으로 원반을 옮겨야 하는데 규칙 1) 한 번에 하나의 원반만 움직일 수 있음규칙 2) 가장 위에 있는 원반만 움직일 수 있음규칙 3) 아래에 작은 원반이 올 수 없음 👉🏻 즉, 기둥 B는 기둥 A의 원반을 기둥 C로 옮기기 위해 임시로 거쳐가는 곳 📍 하노이 탑을 하향식 재귀 방식으로 생각하면? 👉🏻 가장 큰 크기의 원반 3을 가장 아래에 옮겨야 하기 때문에 첫 번째 목표는 원반 3을 기둥 C로 이동시켜야 함 👉🏻 즉 원반 1, 2를 기둥 B로 옮기는 것을 하위 문제로 생각함 👉🏻 👉🏻 원..

[java] ArrayList 0번째 인덱스에 새로운 값 넣고 한 칸씩 미는 법

이미 존재하는 ArrayList가 있을 때 해당 list의 0번째 인덱스에 새로운 값을 넣고 기존 값들은 1칸씩 뒤로 밀고 싶을 때 사용하면 좋은 방법 가장 중요한 포인트는 기존 리스트를 clear 후에 addAll을 해 줘야 새로운 리스트 값으로 제대로 복사된다는 점이다 1) 기존 ArrayList 구조 2) 원하는 ArrayList 구조 '통합검색'을 기존 기스트의 0번째 인덱스에 넣고 싶음 3) 방법 확인 1) 기존 리스트와 동일한 구조의 리스트를 새로 만든다 2) 새로운 리스트에 원하는 데이터를 add 한다 3) 새로운 리스트에 기존 데이터를 addAll 한다 4) 기존 리스트를 clear 한다 5) 기존 리스트에 새로운 리스트를 addAll 한다 // 기존 리스트 ArrayList list = ..

[자료 구조와 알고리즘] 재귀적으로 생각하기

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 재귀적으로 생각하기 📍 재귀 함수를 만들 때는 해당 함수가 이미 구현되었다고 생각하면 좋음! ex) 5! = 5 * factorial(4); 1~5까지 배열의 합 = 5 + 1~4까지의 배열 합 📍 패턴 1: 단순 반복 실행 👉🏻 반복문으로 구현했을 때보다 큰 이점이 되는 부분이 없음 👉🏻 오히려 콜 스택 공간을 많이 차지해 성능이 for문보다 좋지 않음 📍 패턴 2: 하위 문제의 결과를 기반으로 현재 문제 계산 👉🏻 ex: facorial //상위 문제 // 하위 문제 return number * factorial(number - 1); 👉🏻 for문을 이용해 계산하는 방식을 상향식 계산, 재귀를 이용하여 하위 문제 기반으로 현재 문제 계산하는 방식을 하향..

[자료 구조와 알고리즘] 재귀(recursion)

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 재귀(recursion) 📍 재귀(recursion) 👉🏻 어떠한 것을 정의할 때 자기 자신을 참조하는 것 👉🏻 주로 함수를 정의할 때 사용하며, 재귀적으로 정의된 함수를 "재귀 함수"라고 함 [ recursion.mjs ] //function myFunction(number) { // console.log(number); // myFunction(number + 1); // } // myFunction(1); // 기저 조건(탈출 조건)이 없으므로 프로그램 자동 종료 = 언제 끝날지 예측 안 됨 // 숫자가 1~11111까지 출력됨(컴퓨터마다 메모리 공간이 달라 다르게 출력될 수 있음) // 메모리 공간이 가득 차면 콜스택으로 자동 중단됨 function ..

[자료 구조와 알고리즘] 셋(Set)

🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘 셋(Set) 📍 셋(Set) 👉🏻 데이터의 중복을 허용하지 않는 자료 구조 👉🏻 해시 테이블을 이용한 자료 구조로 해시 셋이라고도 불림 👉🏻 Value를 사용하지 않고 Key만 사용하여 구현 📍 셋(Set)의 추상 자료형 [ HashSet.mjs ] ximport { HashTable } from './HashTable.mjs'; class HashSet { constructor() { this.hashTable = new HashTable(); } add(data) { if(this.hashTable.get(data) == null) { this.hashTable.set(data, -1); // 아무 값이나 넣어도 상관은 없으나 예시로 -1 넣음 } } i..