본문 바로가기

자료구조

[정렬] 큌정렬 (Quick Sort) * 퀵정렬 (Quick Sort) "전체 원소에 대해서 정렬을 수행하지 않는다" - Divide and Conquer (분할 정복) : 재귀적 구현 필요기준값(pivot) 을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(divide)기준값(pivot) 보다 큰 원소는 배열의 오른쪽, 기준값(pivot) 보다 작은 원소는 배열의 왼쪽으로 이동 - 실행 성능은 선택한 기준값(pivot) 에 의해 결정- 일반적으로 기준값(pivot) 은 전체 원소 중에서 가운데 위치한 원소를 선택 [시간 복잡도] * 최선의 경우, 평균의 경우 : O(nlogn)pivot 에 의해서 원소들이 왼쪽 부분집합과 오른쪽 부분집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복* 최악의 경우 : O(n^2)pivo.. 더보기
[자료구조/java] 원형 연결 리스트 (Circular Linked List) * 원형 연결 리스트 (Circular Linked List) - 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 리스트 단순 연결 리스트는 현재노드에서 이전 노드를 접근 하려면 현재 위치에 상관없이 항상 리스트의 첫번째 노드부터 시작그러나, 원형 연결 리스트는 마지막 노드와 첫번째 노드가 연결되어 링크를 따라 순회하면 이전 노드에 접근 가능* 원형 연결 리스트는 마지막에 노드를 삽입하는 것이 곧 리스트의 첫 번째에 노드를 삽입하는 것과 같은 의미를 가짐 [ 삽입연산 ] if 리스트가 비어있는 경우 (CL==null)삽입하는 노드가 리스트의 첫번째 노드이자 마지막노드1. 리스트에 새로운 노드를 추가하고, 첫번째 노드로 지정2. 새 노드의 next가.. 더보기
[자료구조/java] 단순 연결 리스트 (Linked List) * 단순 연결 리스트 (Linked List) - 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결 리스트 * 장점 : 삽입, 삭제가 빠르다.하지만 중간에 있는 노드를 삭제하는 경우 탐색에 소요되는 시간이 있기 때문에맨 앞에 있는 요소를 삽입, 삭제하는 경우 O(1), 중간요소를 삽입, 삭제하는 경우 O(n)의 시간복잡도를 가진다.* 단점 : 탐색이 느리다.탐색의 경우 배열이 index를 이용하기 때문에 더빠르다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344Test.java package LinkedList; public class Test { public static void mai.. 더보기
[자료구조] 자료구조 시작 * 자료구조 란? - 자료를 효율적으로 관리하기 위한 데이터 구조 - [자료구조의 분류] - 단순구조 : 정수, 실수, 문자, 문자열- 선형구조 : 리스트, 연결리스트(단순 연결리스트, 이중 연결리스트, 원형 연결리스트), 스택, 큐, 덱- 비선형구조 : 트리(일반트리, 이진트리), 그래프(방향그래프, 무방향그래프)- 파일구조 : 순차파일, 색인파일, 직접파일 [자료의 표현] - 비트(bit) : 디지털 시스템에서 자료를 표현하는 최소 단위- 니블(nibble) : 4개의 비트 그룹- 바이트(Byte) : 8개의 비트 그룹 더보기

티스토리툴바