알고리즘4 [알고리즘] 이진탐색 이진탐색 알고리즘은 정렬이 되어있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 먼저 배열의 중간값을 찾고하자는 값과 비교한다. 그리고 중간값이 찾고하자는 값보다 크다면 배열의 왼쪽, 작다면 배열의 오른쪽 부분으로 탐색 범위를 제한하여 다시 탐색한다. 탐색 단계가 진행될 때마다 탐색 범위는 반씩 줄어든다. 시간 복잡도는 빅오표기법에 따라 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. [알고리즘] 시간 복잡도 알고리즘은 시간 복잡도와 공간 복잡도로 평가한다. 시간 복잡도는 알고리즘을 수행하는 데에 걸리는 시간, 공간 복잡도는 사용되는 메모리양에 해당한다. 빅오표기법(Big O) 표기 시간 설명 예시 O(1) 상수 시간 문제 해결에 오직 한번의 시간만 소요됨 스택의 Push, Pop O(log N) 로그 시간 문제 해결에 필요한 단계가 특정 요인에 따라 줄어듦 이진 트리 O(N) 선형 시간 문제 해결에 N번의 단계가 필요함 한 단계의 반복문 O(N²) 이차 시간 N을 제곱한 단계가 필요함 퀵 정렬, 병합정렬, 힙 정렬 O(2ⁿ) 지수 시간 문제 조건에서 주어지는 상수의 n 제곱 단계가 소요됨 피보나치 수열 N에 따른 시간 복잡도 비교 Big O 표기 1 10 100 O(1) 1 1 1 O(log N) 0 1 2.. 2020. 8. 13. [알고리즘] 공부할 것들 한 항목씩 공부하며 내용을 정리하고 예제를 추가할 예정입니다. 시간 복잡도 [알고리즘] 시간 복잡도 알고리즘은 시간 복잡도와 공간 복잡도로 평가한다. 시간 복잡도는 알고리즘을 수행하는 데에 걸리는 시간, 공간 복잡도는 사용되는 메모리양에 해당한다. 빅오표기법(Big O) 표기 시간 설명 예�� 12teamtoday.tistory.com 자료구조 1. 선형 자료구조 1.1 랜덤 접근 가능 1.1.1 배열 1.1.2 해시 1.2 랜덤 접근 불가능 1.2.1 스택 [자료구조] 배열을 이용한 Stack구현 스택은 상자에 데이터를 집어넣는 형태의 구조이다. 데이터가 저장 될 때마다 위로 쌓이고, 데이터를 꺼낼 때는 가장 위에 있는 것만 꺼내오는 후입선출형(Last In First Out) 구조이다. 스택의 맨 위.. 2020. 8. 13. 이전 1 다음
