본문 바로가기

Basic/자료구조

삽입정렬 1. 삽입정렬이란?삽입정렬은 정렬 안된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해가면서 정렬을 진행하는 것이다.전체적인 원리는 처음 5는 정렬되어있다고 생각하고 3부터 2,4,1을 차례대로 정렬을 진행한다.이를 위한 구체적인 다른 예시를 봐보자아래와 같이 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾는것이다. 2. 삽입정렬 구현구현설명은 코드 주석을 봐보자1234567891011121314151617181920212223242526272829303132public class InsertionSort { public static void main(String[] args) { int[] arr = {3, 2, 4, 1}; SelSort(arr, arr.length); for(int i=0;..
선택정렬 1. 선택정렬이란?정렬 순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그자리에 있던 데이터는 빈자리로 이동하는것.2. 선택정렬 구현- 버블정렬과 유사하다- for문 중첩으로 구현하였다. - 안쪽 for문의 반복조건과 바깥쪽 for문의 반복조건에 대한 이해가 정확히 필요하다.123456789101112131415161718192021222324252627282930313233public class SelectionSort { public static void main(String[] args) { int[] arr = {3, 2, 4, 1}; SelSort(arr, arr.length); for(int i=0; i
정렬-버블정렬 1. 정렬자료구조에서 정렬을 얘기하는 이유는 탐색을 설명하기 위한것이다.탐색은 어떤 기준을 근거로해서 정렬된 데이터들을 어떻게 효율적으로 탐색할것인가?그것을 논의하는게 탐색이다.탐색에 앞서 선행된 주제가 정렬이다. 2. 버블정렬 이해- 버블정렬은 구현하기는 쉬우나 성능은 떨어진다.- 인접한 두개의 데이터를 비교해가면서 바뀌어야 한다면 두 데이터를 바꾸면서 정렬을 진행한다. 1) 첫번째 : 제일 큰 값을 맨 뒤로 보낸다. 2) 두번째: 두번째로 큰 값을 맨뒤에서 한 칸 앞으로 보낸다. 3) 세번째: 나머지를 동일하게 정렬한다. 이와 같이 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 한다. 3. 버블정렬 구현- for문 중첩으로 구현하였다. - 안쪽 for문의 반복..
우선순위 큐와 힙 1. 우선순위 큐와 힙 큐와 우선순위 큐는 다르다. 큐는 선형 자료구조에 속한다.우선순위 큐는 비선형 자료구조에 속한다큐의 연장선이 아닌 트리의 연장선이라고 봐야한다 우선순위큐는 들어가는 순서와 나가는 순서가 아무런 관계가 없다단지 입구와 출구가있어서 큐라하는것이다.우선순위를 근거로 데이터 뽑아낸다.우선순위는 프로그래머가 결정함. 2. 우선순위 큐의 구현 1) 배열과 연결리스트로 구현 데이터의 수가 많아지면 배열이나 연결리스트는 성능이 떨어진다 그래서 힙을 이용해 구현하는게 좋다 2) 힙이라는 자료구조를 통한 우선순위 큐 구현 힙이 우선순위큐라고 말할수는 없다. 우선순위 큐를 만들기 위해 힙(이진트리)을 사용한것이다. 힙의 특성 2가지 - 이진트리의 일종이다 그런데 그냥이 아닌 완전 이진트리이다 위에서 ..
Queue의 다양한 구현 1. 원형 큐(링 버퍼) - 배열 기반 - front(머리), rear(꼬리)라는 변수를 인덱스로 활용해 삽입,조회,삭제를 구현하였다.- front와 rear의 변수가 같다면 큐가 비어있는것이다.- front와 rear+1 이 같다면 큐가 꽉차있는것이다.- 배열의 끝에 도달하면 첫번째 인덱스로 순환하여 원형큐라 한다.- 삭제의 경우 배열에서 실제로 하지 않고 front(머리-출구), rear(꼬리-입구)의 값을 조정한다. 12345678910111213141516171819202122package queue;public class ArrayQueueMain { public static void main(String[] args) {//배열 기반 큐 ArrayQueue queue = new ArrayQue..
Queue - 큐의 개념과 특성들 1. Queue의 정의 - Queue는 먼저 들어간 데이터가 먼저 나오는 자료구조이다.- 입구와 출구가 다르다.- 파이프 구조이다. 2. Queue의 기본연산 offer - 큐의 입구에 데이터 추가poll - 큐의 출구로부터 데이터의 반환과 + 삭제peek - 큐의 출구로부터 데이터의 반환isEmpty - 데이터의 유무 확인 Method Description boolean isEmpty() Queue가 비어있는지 알려준다. boolean offer(Object o) Queue에 객체를 저장. 성공하면 true, 실패하면 false를 반환. Object poll() Queue에서 객체를 꺼내서 반환+삭제. 비어있으면 null을 반환. Object peek() 삭제없이 요소를 읽어 온다. Queue가 비어있..
Stack의 다양한 구현 1. 순수 배열로 직접 구현 배열에서 인덱스를 활용해 topIndex의 값을 바꿔주는것이 포인트이다. POP을 호출해도 배열에서 값을 실제로 삭제하지는 않고 인덱스만을 활용한다. 1234567891011121314151617181920212223package Stack; public class ArrayStackMain { public static void main(String[] args) { ArrayStack st = new ArrayStack(); st.push("0");//삽입 st.push("1"); st.push("2"); System.out.println("= MyStack1 peek="); System.out.println(st.peek());//마지막 값 리턴 System.out.pri..
Stack 스택의 개념과 특성들 1. Stack의 정의 - Stack은 쌓아 올린다는 의미로서 마지막에 들어간 데이터가 먼저 나오는 자료구조 입구와 출구가 같다 2. Stack의 기본연산 push - 스택의 맨 위에 데이터 추가pop - 스택의 맨 위 데이터의 반환과 + 삭제peek - 스택의 맨 위 데이터의 반환empty - 데이터의 유무 확인 Method Description boolean isEmpty() Stack이 비어있는지 알려준다. Object peek() Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 끼내지는 않음.(비었을 때는 EmptyStackException발생) Object pop() Stack의 맨 위에 저장된 객체를 삭제후 반환한다. (비었을 때는 Empty StackExce..