kotlin43 [Kotlin] 버블 정렬 - Bubble Sort 🔷 버블 정렬 (Bubble Sort)이란? 거품이 터지면서 위로 올라오듯이 값을 하나씩 비교하며 올라오는 정렬이다. 인접한 두 값을 비교하며 값을 정렬한다. 값을 비교하면서 정렬하기 때문에 '비교 정렬'이라고도 부른다. 데이터를 정렬하기 위하여 추가적인 데이터가 필요하지 않기에 '제자리 정렬(in-place sort)'로 분류되기도 한다. 🔷 버블 정렬의 장점 🔹쉬운 난이도 구현이 간단하다. 🔹적은 메모리 정렬을 위하여 추가적인 메모리를 사용하지 않는다. 🔷 버블 정렬의 단점 🔹교환 낭비 가장 큰 값이 가장 왼쪽에 있을 때 맨 끝으로 이동하기 위해서는 모든 값과 비교되어 올라가야한다. 혹은, 가장 큰 값이 이미 맨 끝으로 정렬되어 있어도 교환을 확인하는 상황이 생길 수 있다. 🔷 시간 복잡도 🔹최악의 .. 2023. 8. 28. [Kotlin] 꼬리 재귀 함수 - tailrec 🔷 꼬리 재귀 함수 (tailrec)이란? 재귀 함수를 구현할 때 마지막(Tail)에 자기 자신을 호출(Recursion)하는 형태의 함수이다. 반환 값 : 호출 당한 함수의 결과 → 호출한 함수의 결과 🔹재귀 함수 재귀 함수는 '자기 자신을 호출하는 함수'이다. 구조는 비슷하지만 더 작은 문제로 쪼갤 수 있는 문제를 풀 때 유용한 접근 방법이다. 함수는 호출될 때마다 함수의 입력값(매개변수), 결과값(리턴값), 리턴 후 돌아갈 위치 등이 스택(Stack)에 보관된다. 재귀 함수는 '자기 자신을 호출'을 여러번 반복하여 콜 스택이 깊어질 수록 메모리 오버헤드 (스택 오버 플로우 stack overflow) 현상을 일으킬 수 있다. 🔹재귀의 특징 - 무한 루프에 빠지지 않기 위해 일정한 탈출 조건이 있어야.. 2023. 8. 21. [Kotlin] 선형 검색 - Linear Search 🔷 선형 검색 (Linear Search)란? 선형 검색(Linear Search) 혹은 순차 검색(Sequential Search)이라고 불린다. 이름과 같이 데이터의 집합을 처음부터 끝까지 순서대로 비교하여 값을 검색한다. 🔷 선형 검색의 장점 🔹비정렬 선형 검색은 값을 하나하나 비교하는 방식이므로 데이터가 정렬되지 않은 상태에서도 사용이 가능하다. 정보없이 데이터를 찾아야하는 경우에도 유용하게 사용이 가능하다. 🔹쉬운 난이도 데이터를 정렬, 수정할 필요가 없기 때문에 난이도가 쉽다. 🔷 선형 검색의 단점 🔹비효율 방대한 양의 데이터가 있을 경우, 값이 마지막에 위치하거나 존재하지 않는 최악의 경우에 모든 데이터를 확인한다. 데이터의 양이 많아질 수록 검색 시간이 비례하여 늘어난다. 🔷 시간 복잡도 .. 2023. 8. 14. [Kotlin] 힙 - Heap 🔷 힙 (Heap)이란? 힙 (Heap)은 우선순위 큐 (Priority Queue)를 구현하기 위한 자료구조이다. 완전 이진 트리를 기초로 하며, 최소 혹은 최대값을 찾기에 효율적이다. 힙은 반정렬 상태 (느슨한 정렬 상태)를 유지한다. 🔹우선순위 큐 (Priority Queue) 큐(Queue)는 가장 먼저 들어온 데이터가 가장 먼저 나가는 형식의 FIFO(First-In First-Out) 구조이다. 우선순위 큐(Priority Queue)는 먼저 들어온 데이터가 아닌, 우선순위가 가장 높은 데이터가 먼저 나가는 구조이다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다. 🔹힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드와 서브트리간 대소 관계가 성립된다. : 반정렬 상태 이진탐색.. 2023. 8. 7. [Kotlin] 큐 - Queue 🔷 큐 (Queue)이란? 큐(Queue)은 일렬로 늘어선 사람들의 줄을 말하기도 한다. 선형 리스트의 한쪽에서 자료의 입력되고, 반대 쪽에서 출력이 가능한 자료구조이다. Q = (q0, ... , qn-1) 구조일 때 q0이 앞(front)원소, qn-1을 뒤(rear)원소라고 한다. 이런 큐의 구조를 선입선출 (FIFO, First-In First-Out)구조 라고 한다. 🔹큐의 시작과 끝 큐는 한 쪽에서는 입력, 반대 쪽에서는 출력이 일어난다. 가장 먼저 온 사람이 가장 먼저 나가는 대기줄의 형태와 동일하다. 큐는 사용하기 위하여 큐의 상태를 나타내는 front와 rear 변수가 필요하다. front는 가장 앞에 있는 원소를 가르키며, 제일 먼저 들어온 변수부터 나가는 출구이다. rear은 가장 뒤.. 2023. 7. 31. [Kotlin] 스택 - Stack 🔷 스택(Stack)이란? 스택(Stack)은 쌓아 올린다는 의미이다. 선형 리스트의 한쪽에서만 자료의 입력과 출력이 가능한 자료구조이다. 따라서 선형 리스트의 끝 부분에 대한 정보를 가지고 있는 변수가 필요하다. 이런 스택의 구조를 후입선출 (LIFO, Last-In First-Out)구조 라고 한다. 🔹스택의 끝 부분 : top 스택은 정해진 방향으로만 데이터를 삽입, 출력이 가능하다. 통 속에 물건을 집어넣거나, 접시를 쌓아올리는 형식과 유사하다. 스택을 사용하기 위해서는 데이터가 이동하는 위치 정보가 필요하며, 주로 변수명으로 top을 사용한다. top은 가장 최근에 삽입된 자료를 가르키며, 새 자료는 top이 가르키는 자료 위에 쌓인다. 삭제 또한 top이 가리키는 자료부터 순서대로 진행된다. .. 2023. 7. 31. 이전 1 ··· 4 5 6 7 8 다음
