본문 바로가기

Algorism10

선택정렬(Selection sort) 선택정렬 시간복잡도 공간복잡도 전체 요소를 순회하기 위해 N 요소들을 비교하며 가장 작은 요소를 찾기 위해 N N x N = O(N²) 비교 후 배열 내 스왑을 하기 위해 O(1) 배열을 순회하며 가장 작은 요소를 찾아 맨 앞에 위치시키는 방식의 정렬 [7, 4, 5, 1, 3] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 배열은 총 5개의 요소를 가지고 있다. 맨 앞의 요소부터 전체 요소와 비교해가며 가장 작은 요소를 찾아 비교요소와 위치를 바꾼다. 먼저 가장 작은 요소의 index를 0번으로 초기화한다. 첫번째 loop는 0번을 기준으로 비교한다. 0번과 1번, 0번과 2번, 0번과 3번, 0번과 4번하며, 만약 비교하는 요소가 가장 작은 요소(현재 0번)보다 더 작다면 가장 작은 요소의 인덱.. 2022. 7. 12.
버블정렬(Bubble sort) 버블정렬 시간복잡도 공간복잡도 전체 요소를 순회하기 위해 N 인접 요소를 비교하기 위해 N N x N = O(N²) 인접 요소 비교 후 스왑을 하기 위해 O(1) 버블 정렬은 인접한 두 요소를 비교하며 큰 값을 뒤로 보내는 방식이다. [4, 1, 3, 5, 6, 2] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 배열은 총 6개의 요소를 가지고 있다. 이때 배열의 0번 요소부터 인접한 두 개 요소를 비교한다. 첫번째 loop는 0번과 1번, 1번과 2번, 2번과 3번, 3번과 4번, 4번과 5번을 비교한다. 만약 앞의 요소(i번째)가 뒤의 요소(i + 1번째)보다 크다면 둘의 위치를 바꾸고, 뒤의 요소가 더 크다면 다음 비교로 넘어간다. 두번째 loop는 다시 0번과 1번, 1번과 2번, 2번과 3.. 2022. 7. 12.
[알고리즘] 이진탐색 이진탐색 알고리즘은 정렬이 되어있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 먼저 배열의 중간값을 찾고하자는 값과 비교한다. 그리고 중간값이 찾고하자는 값보다 크다면 배열의 왼쪽, 작다면 배열의 오른쪽 부분으로 탐색 범위를 제한하여 다시 탐색한다. 탐색 단계가 진행될 때마다 탐색 범위는 반씩 줄어든다. 시간 복잡도는 빅오표기법에 따라 O(logN)과 같다. 이진탐색은 선형탐색에 비해 속도가 빠르지만 정렬이 되어 있는 데이터에만 적용할 수 있다는 단점이 있다. 예시 {1, 12, 38, 41, 60} 위와 같은 배열에서 41을 찾는다고 하자. 배열의 길이는 5이고 중간값은 3이다. 배열의 인덱스는 0부터 시작하므로 2번 인덱스의 값은 38이다. 38은 41보다 작기때문에 찾고자하는 값은 배열의 가운데 .. 2020. 8. 31.
[자료구조] 배열을 이용한 Stack구현 스택은 상자에 데이터를 집어넣는 형태의 구조이다. 데이터가 저장 될 때마다 위로 쌓이고, 데이터를 꺼낼 때는 가장 위에 있는 것만 꺼내오는 후입선출형(Last In First Out) 구조이다. 스택의 맨 위에서만 데이터가 들어가고 나오기 때문에 이에 적합하 구조에서 사용하기 매우 간편하고 데이터에 접근하고 처리하는 속도도 빠르다. public class MyStack { private int top; private int maxSize; private Object[] stack; public MyStack() { this.top = -1; this.maxSize = 5; this.stack = new Object[maxSize]; } public MyStack(int maxSize) { this.top.. 2020. 8. 24.

티스토리툴바