CS지식/자료구조
-
자료구조 - 트리,이진 검색트리(BST)CS지식/자료구조 2024. 9. 23. 14:02
1. Tree 소개 1.1. Tree자료구조란 무엇일까? tree는 linked list처럼 노드로 이루어진 데이터 구조이다. 그렇지만 노드들 사이에 부모-자식 관계가 있다. 결과적으로 가지(branch)를 가지게된다. 그러니까 한 노드는 다른 노드로 연결되어 있는데 2개나 3개 10개 아니면 0개가 될 수도 있다. 그렇게 되면 노드가 branch를 가지는 구조가 되는데, 그래서 이름을 tree라고 한다. 가지를 따라가면 어느 지점에서 나뉘게 되고, 그 가지는 계속해서 나뉠 수 있다. 그러면 원래 줄기에서 뻗어나온 수많은 작은 가지들이 남게된다.보통 다이어그램을 보게되면 root노드를 기준으로 위에서 아래로 내려오는 경우가 많다. list는 선형구조이다. 한가지가 있고, 그 다음에 하나, 그다음에 하..
-
JAVA 자료구조 (리스트) - LinkedList 3 (기타작업)CS지식/자료구조 2024. 1. 3. 14:45
LinkedList 기타 작업 나머지 작업들을 하나씩 정리해보자. 리스트의 k번째 원소를 알려주는 함수 get(k)는 k번째 노드를 찾은 다음 그 노드의 원소를 리턴한다. 알고리즘 5-13 연결 리스트의 k번째 원소 알려주기 public T get(int k){ return getNode(k).item; } k번째 노드를 찾는 함수 getNode(k)는 여러 함수에서 필요한 보조 작업으로 코드는 다음과 같다. 노드의 인덱스는 0 ~ numItems -1 사이에 있지만 더미 헤드를 찾는 경우에도 지원하기 위해 k = -1이면 더미 헤드를 찾는 것으로 해석한다. 첫 번째 노드는 0번째 노드로 표기하고, 더미 헤드 노드는 -1번째 노드로 표기한다. public T getNode(int k){ if(k >= -..
-
JAVA 자료구조 (리스트) - LinkedList 2 (원소 삽입, 원소 삭제)CS지식/자료구조 2024. 1. 3. 12:12
연결리스트 2. 연결 리스트의 작업 원소 삽입 연결 리스트에서 중간 노드를 삽입하려면 삽입 노드의 바로 앞에 노드, 즉 직전 노드를 가리키는 레퍼런스preNode가 있어야 한다. [그림 5-15]의 예를 살펴보자 (a)와 같이 연결 리스트에서 원소 17과 35 사이에 원소 25를 삽입하려면 레퍼런스 preNode가 원소 25를 담고 있는 노드를 가리키도록 준비한다. 그런 다음 (b)와 같이 원소 17과 35노드 사이에 원소 25의 새 노드를 삽입한다. 이 작업을 위한 알고리즘은 다음과 같다. x는 삽입할 원소다. newNode.item = x newNode.next = preNode.next prevNode.next = newNode numItems++ 여기서 prevNode.next는 원소 35의 노드..
-
JAVA 자료구조 (리스트) - 배열리스트 2CS지식/자료구조 2023. 12. 28. 16:25
배열 리스트 2 2. 배열 리스트의 작업 원소 삭제 리스트에서 원소를 삭제할 때는 특정 위치의 원소를 삭제하게 할 수도 있고, 특정 원소를 삭제하게 할 수도 있다. [그림 5-11]은 리스트의 3번째 원소를 삭제하는 예다. 리스트에 총 9개의 원소가 저장되어 있어 변수 numItems 값은 9인 상태다. 3번째 원소인 17을 삭제하고 4~8번째 원소들을 왼쪽으로 시프트 한다. 알고리즘 5-3 배열 리스트의 k번째 원소 삭제하기 void remove(int k){ if(isEmpty() || k numItems-1) /* 에러처리 */ else{ for(int i = k; i < numItems-2l i++ item[i] = item[i+1]; // ◀ 왼쪽으로 시프트 numItems-..
-
JAVA 자료구조(리스트) - 배열리스트 1CS지식/자료구조 2023. 12. 27. 16:00
배열리스트 1. 배열 리스트의 객체 구조 [그림 5-5]에서 위쪽은 배열을 보는 물리적 관점이고, 아래쪽은 리스트를 보는 추상적 관점이다. 배열 item[0...] 에 원소들이 들어가 있다. ADT리스트 관점은 하부 구조를 특정하지 않는다. ADT에서 리스트는 원소를 리스트의 0번째 원소, 6번째 원소, 마지막 원소와 같이 추상적으로 본다. 배열을 이용해 리스트를 구현한다는 것은 이 추상적 관점을 물리적 배열에 대응시켜 주는 것이다. 예를 들어, 리스트의 0번째 원소를 배열의 item[0]에 대응시킨다. 마찬가지로 리스트 i번째 원소는 배열의 item[i]에 대응된다. 추상적 관점을 물리적으로 대응시킬 때 [그림 5-6]과 같이 배열을 역순으로 해석할 수도 있다. 배열로 구현한 리스트에 원소를 삽입하거나..
-
JAVA 자료구조 (리스트) - 리스트란CS지식/자료구조 2023. 12. 27. 13:57
리스트란 생활 속의 리스트 리스트는 대표적인 자료구조 중 하나로 자료구조&알고리즘을 공부하다 보면 아주 흔하게 만나게 될 것이다. 리스트는 '줄 세워져 있는 데이터 ' 또는 '죽 늘어선 데이터'를 의미한다. 리스트의 예는 풍부하다. 정수 리스트, 어떤 그룹에 속하는 사람 리스트, 서비스를 기다리는 사람 리스트, 선물 받고 싶은 목록을 적은 위시 리스트, 위험한 사람들을 적은 블랙 리스트, 선물 보낼 사람들 리스트 등 끝없이 예를 들 수 있다. 리스트의 작업 리스트를 관리하기 위해 필요한 작업을 생각해보자. 우선, 리스트에 새 원소를 삽입할 일이 많을 것이다. 이때 1)원소를 리스트의 맨 뒤에 넣을지 맨 앞에 넣을지 중간 어디쯤 넣을지 알려줘야 할 것이다. 또한 2)리스트에서 원소를 삭제할 때는 어디에 있..
-
자료구조 - 하노이 탑(Tower of Hanoi)재귀 호출 코드 구현CS지식/자료구조 2023. 12. 26. 11:44
하노이 탑 재귀 호출 코드 구현 각각의 기둥을 A, B, C라고 하고 원반의 갯수를 n이라고 하고 문제를 풀어 본다. 원반의 갯수가 1인 경우 A기둥에 있는 원반을 목표하는 B기둥으옮기기 위해서 (A → B) 이동 횟수 1회가 발생한다. 원반 갯수가 2개인 경우 원반1 (A → C) 원반2 (A → B) 원반1 (C → B) 1)A기둥에 원반1,2가 있다. → 2)일단 원반1을 C기둥으로 옮긴다.→ 3)원반2를 B기둥으로 옮긴다. → 4)원반1을 B기둥으로 옮긴다. 이렇게 하면 원반을 모두 목표하는 기둥으로 옮기게 되는데 이때는 3회의 이동 횟수가 발생한다. 원반 갯수가 3개인 경우 원반의 갯수가 3개여도 (A → C), (A → B), (C → B) 이동 과정을 거쳐 원반1,2가 임시 장소인 C에 가는..
-
JAVA 자료구조 (재귀와 귀납적 사고) - 재귀 구조 예CS지식/자료구조 2023. 12. 25. 14:04
2.재귀 구조의 예 3. 선택정렬 배열 A[0..n-1]에 n개의 원소가 주어지고 이를 크기순으로 정렬하려고 한다. 여러 정렬 알고리즘 중 가장 기초적인 알고리즘인 선택 정렬의 예를 살펴보자. [알고리즘 2-5]의 선택정렬 알고리즘에서 먼저 전체를 한 번 훑어 가장 큰 원소를 찾는다.(2️⃣) 이 원소를 제일 오른쪽 원소와 맞바꾼다.(3️⃣) 그러면 맨 오른쪽 제일 큰 원소가 자리하게 되고 이 원소는 더 이상 자리를 바꿀 필요가 없다. 즉, 제일 큰 원소에 관한 한 정렬이 끝난 것이다. 이제 맨 오른쪽 원소를 관심 대상에서 제외한다. 그러면 A[0...n-2]에 n-2개 짜리 정렬 문제가 남는다. 즉, 가장 큰 뭔소를 찾아 맨 오른ㅉ고 원소와 맞바꾸는 수고를 하고나면 자신과 성격이 똑같지만 크기가 하나만..