본문 바로가기

전체 글

 (28)
스택(Stack) LIFO(Last In First Out) 자료구조 먼저 들어간 데이터가 나중에 뽑혀 나오게 저장되는 자료구조. 우리가 이사를 할 때 짐을 싸게 되는데 박스안에 이삿짐을 차곡차곡 쌓아 저장하고 꺼낼때 나중에 넣어서 위에 저장된 짐을 뺴는 것과 같은 형태를 생각하면 이해하기 편하다. 재귀, 시스템 콜, 히스토리를 쌓아 나갈때(ex 인터넷 뒤로가기, 프로그램의 Ctrl+Z) 등에 사용된다. 시간복잡도 삽입 : O(1) 삭제 : O(1) 조회 : O(n) 공간복잡도 O(N) Java에서의 사용법 선언 Queue stack = new Stack(); 삽입 stack.push(items); 삭제 stack.pop(); // 데이터가 없는 상태에서 호출시 EmptyStackException empty 체크 stac..
링크드리스트(Linked List) 배열은 원소를 삽입, 삭제할때 새로운 저장 공간을 새로 만들거나 원소를 당겨버리는 행동을 하는 등 시간복잡도가 O(n)이 걸리곤 했다. 링크드 리스트는 이 삽입, 삭제에 걸리는 시간을 줄이기 위해 탄생한 자료구조 자료를 저장할때 자료값만 저장하는 것이 아니라 다음 자료가 저장되어있는 위치를 함께 저장시키는 자료구조 저장공간의 크기는 가변적이다. 메모리 공간이 배열과는 달리 연속적으로 구성되어 있지 않다. 원소의 저장이 메모리에 연속으로 들어가는 것이 아니라 원소값과 다음 원소값이 저장되어있는 주소값이 함께 저장되어 있어 그 주소값을 찾아 원소를 탐색해 나간다. 그러므로 배열(Array)의 인덱스(Index)를 통한 접근이 불가능하다. 장점 새로운 원소를 삽입할때 시간복잡도 O(1) 원소를 삭제할때 시간복..
배열(Array) & ArrayList 연관된 데이터를 하나로 묶어 그루핑해서 관리하기 위해 만들어진 자료구조 배열에서 위치를 가리키는 숫자를 인덱스(Index)라고 부름 인덱스는 0 부터 시작 참조 객체다. 배열을 가리키는 참조 변수는 스택(Stack) 영역에 할당된다. 참조 변수가 가리키고 있는 주소값(Address)는 힙(heap)영역에 생성되는 배열의 주소값이다 특징 선언할때 고정된 크기를 지정해야함. 즉 고정된 크기를 가지게 된다. 메모리 공간이 연속적으로 구성된다. 물리주소와 논리주소가 동일 ⇒ 인덱스(Index)를 활용 가능 장점 인덱스를 통한 접근이 가능하므로 원소를 조회할때 O(1) 인덱스를 통한 접근이 가능하므로 원소를 수정할때 O(1) 단점 배열의 크기가 고정적이라는 말은 다시 말해 더 추가하고 싶다면 더 큰 크기의 배열을..
이진 탐색(Binary Search) 탐색할 크기를 절반씩 줄여나가며 값을 탐색해나가는 알고리즘 1. 전체 배열의 중간값을 기준으로 앞 뒤를 나눈다. 2. 탐색하는 값이 중간값보다 크다면 뒤의 배열에서 다시 중간값을 나누고 탐색 3. 탐색하는 값이 중간값보다 작다면 앞의 배열에서 다시 중간값을 나누고 탐색 시간복잡도 매번 절반씩 나눠가며 탐색하므로 O(logn) 공간복잡도 O(logn) Code 반복문 class Main { public static void main(String[] args) { int[] data = {7,9,10,14,17,19,26}; int idx = binarySearch(data, 14); System.out.println("idx " + idx); } public static int binarySearch(in..
계수정렬(Counting Sort) 각 숫자가 몇번 나오는지 count를 한 후 앞 순서대로 차례대로 다시 내보내 정렬 시키는 정렬 알고리즘 0. [3,4,0,1,2,4,2,4], [개수를 count한 후 저장할 공간] 1. 개수를 저장할 공간을 0으로 초기화 시켜준다. 배열의 크기는 데이터 배열의 최대값 [3,4,0,1,2,4,2,4], [0,0,0,0,0] // 2. 처음부터 개수를 세어 저장합니다. 0은 1개, 1은 1개, 2는 2개, 3은 1개, 4는 3개 [3,4,0,1,2,4,2,4], [1,1,2,1,3] 3. 개수를 저장한 것을 누적합시킨다. [3,4,0,1,2,4,2,4], [1,2,4,5,8] 4. 누적합을 바탕으로 숫자를 결과에 넣어줌. 0은 1에, 1은 2에, 2는 3~4에 3은 5에, 4는 6~8에 넣어준다. 결과 ..
기수정렬(Radix Sort) 1,10,100... 등 각 자리수를 기준으로 비교없이 정렬을 수행하는 정렬 알고리즘 각 원소들 중 최대 자리수를 구한다. [1,2,3,10,157] 이라면 157, 세자릿수인 3이 최대 자리수가 된다. 0 ~ 9까지의 Queue를 만든다. 각 원소별 자리수의 숫자를 해당하는 번호의 Queue에 집어 넣는다. 0 ~ 9 까지의 Queue를 순회하며 원소를 뽑아 기존 배열에 교체해준다. 최대 자리수만큼 2 ~ 4를 반복해준다. 시간복잡도 최대자릿수 d만큼 반복하며 원소의 개수 n만큼 돌게 되므로 O(dn) 이므로 O(n)의 시간복잡도를 가지게 된다. 공간복잡도 기존원소 배열 크기 n에 추가적으로 자리수 Queue배열이 추가되므로 O(n) 왜 잘 안쓰지? 시간복잡도 O(n)이라는 빠른 속도를 가지고 있는데 ..
병합정렬(Merge Sort) 데이터 집합을 절반으로 쪼개어 나간 뒤 쪼개진 부분집합들을 다시 정렬된 형태로 합치는 방식의 분할정복 정렬 https://ko.wikipedia.org/wiki/합병_정렬 시간 복잡도 데이터를 균등하게 절반씩 쪼개나가기에 총 n개의 데이터가 logn 단계만큼의 연산을 수행하므로 O(NLogN)이 된다. 공간 복잡도 데이터를 정렬함에 있어 추가적인 데이터 리스트 공간이 필요하기 때문에 O(n)의 공간 복잡도를 가지지만 다른 정렬보다 n만큼의 메모리를 더 차지하게 된다. Code public class MergeSort { public static void mergeSort(int[] data) { if (data.length < 2) { return; } int mid = data.length / 2; i..
퀵정렬(Quick Sort) 분할정복 기반의 정렬 정렬방법 데이터 집합에서 기준점이 될 피벗 값 선정 피벗을 기준으로 피벗보다 작은 값을 왼쪽, 큰 값을 오른쪽으로 2개의 부분 집합을 만들어냄 왼쪽, 오른쪽 각각의 부분집합에서 앞선 1,2번 반복 부분집합내 데이터가 1이 될때까지 반복한다. 시간복잡도 최선 : NLogN 재귀 호출이 일어날 때 마다 부분 리스트의 크기가 절반씩 줄어들게 되므로 n개의 원소에 대해 logN만큼 연산을 하기때문에 시간복잡도는 NLogN이 된다. 최악 : n^2 피벗 선택이 항상 데이터 집합의 최소값을 선정했다고 가정한다면 부분집합의 크기가 절반씩 줄어드는 것이 아닌 n n-1 n-2 ... 로 줄어드므로 n번의 연산을 거치게 되면 O(n^2)이 되게 된다. 공간복잡도 정렬을 함에 있어 분할된 데이터 공간..

티스토리툴바