자료구조 썸네일형 리스트형 정렬 알고리즘 정렬 알고리즘원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘Stable & Unstablestable : 동일한 key값을 갖고 있는 원소들의 순서가 보존 되는 것unstable : 동일한 key값을 갖고 있는 원소들의 순서가 보존 되지 않는 것Inplace & Not-In-Placein-place 알고리즘입력 데이터를 수정하면서 정렬을 수행즉, 추가적인 메모리 공간을 사용하지 않고, 주어진 입력 데이터 내부에서 직접적으로 작업을 수행not-in-place추가적인 메모리 공간을 사용하여, 입력 데이터를 복사하고 정렬을 수행 1. 버블 정렬두 개의 인접한 원소를 비교해 순서에 맞게 교환하여 정렬각 회차가 끝날 때마다 가장 큰 or 가장 작은 수의 자리가 확정func bubbleSor.. 더보기 비선형 자료구조 - 트리 트리- 순환 X, 무방향, 계층적인 구조를 갖는 그래프- 그래프의 표현(인접 리스트/행렬)과 탐색(DFS/BFS) 알고리즘을 그대로 사용 가능 등장 배경- 정보를 계층적이고 체계적으로 관리하고 싶음- 분기를 나눠 탐색 속도를줄일 수 있음 -> 분기로 통해 탐색 방향이 걸러지면 걸러진 분기는 탐색 X 트리의 종류 1. 이진 트리- 모든 노드가 최대 2개의 자식을 가짐ex. 이진 검색 트리, heap, 완전 이진 트리 2. N진 트리- 한 노드가 여러 자식을 가질 수 있음ex. 파일 시스템 디렉토리 구조 3. 균형 트리- 모든 리프 노드가 비슷한 깊이를 갖도록 설계ex. AVL 트리, Red-Black 트리이진 트리각 노드가 최대 2개의 자식을 갖는 트리 1. 정 이진트리- 모든 노드가 0 or 2개인 자식.. 더보기 비선형 자료구조 - 그래프 비선형 자료구조- 순차적으로 나열되는 것이 아닌 앞,뒤의 관계가 1:N, N:N인 자료구조ex. 그래프, 트리 왜 비선형 자료구조를 사용할까?- 더 많은 정보를 담고- 많은 정보를 담은 상태에서 더 빨리 탐색하기 위함 그래프- 노드(정점) + 간선 으로 연결관계를 표현하는 자료구조 그래프 특징 1. 방향성- 간선에 방향성 추가 (기존 A - B, 방향성 추가 A -> B )- 방향성이 추가되면서 한 쪽 방향으로의 접근만 가능해짐- 해당 연결성을 확인하기 위해 Floyd - Warshall 알고리즘 활용 2. 가중치- 간선에 가중치(비용) 추가- 가중치 + 방향 성분이 모두 포함된 그래프 -> 네트워크- 가중치 개념이 추가되면서 기존에 없던 minimum cost 를 확인해야하는 문제 발생 -> 최소 .. 더보기 선형 자료구조 선형 자료구조- 데이터를 순차적으로 저장 (각 데이터가 1:1로 연결되는 방식)- 배열, 링크드 리스트, 스택, 큐배열연속적인 메모리 공간에 순차적으로 저장되는 자료구조 특징- 모든 요소가 같은 타입>>> 연속적인 메모리 공간에 데이터들이 존재하고, 데이터들의 타입이 같으니 O(1)로 시간 복잡도로 랜덤 접근 가능- Sequence와 Collection 프로토콜을 채택하고 있는 컬렉션 타입 Capacity- 새로운 저장공간 없이 배열이 포함할 수 있는 요소의 개수- 초기화 시점에 요소의 개수만큼 capacity 설정- capacity를 넘어가게 되면 기존 capacity의 약 2배 크기의 새로운 공간을 만든 후 기존 배열을 복사하고 요소 추가- reserveCapacity 메서드를 활용하여 불필요한 배열.. 더보기 자료구조 사전지식 1. 시간복잡도- 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 => 쉽게 이야기하면 내 코드가 연산되는 횟수 1-1. Big - O 표기법- 모든 경우를 고려했을 때 최악을 기준으로 시간복잡도 표현- 가장 큰 영향을 주는 요소를 기준으로 표현=> 상수항 무시=> 계수 무시=> 최고차망만 표시 But, 항상 시간복잡도가 크다고 해서 연산횟수가 많은 것은 아님=> 데이터의 크기에 따라 결정 1-2. 그 외 표기법- Big-Ω (빅 오메가): 최선의 시간 복잡도- Big-θ (빅 세타): 평균적인 시간 복잡도 2. 공간복잡도- 입력의 크기와 문제를 해결하는 데 필요한 공간의 상관관계 2-1. Bit & ByteBit- 0,1 을 표현하는 데이터 양의 최소 기본 단위Byte- 1byte = 8bit.. 더보기 이전 1 다음
