CS공부/자료구조6 [자료구조] 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리 - 탐색에 유용하게 설계된 이진 트리를 말한다. - 이진 트리 : 자식 노드가 두개인 트리 - 설계 규칙 1. 각 노드는 서로 다른 키를 가진다. 2. 각 노드는 최대 2개의 자식 노드를 가진다(최대 두개 분기) 3. 각 노드의 key는 - left subtree의 모든 노드의 key보다 크고 - right subtree의 모든 노드의 key보다 작다. 검색 search(r, x) if(r == null || r.item == x) return r else if(r.item < x) return search(r.left, x) else return search(r.right, x) - 시간복잡도 평균 theta(logn), 최악 theta(n) 삽입 insert(r, x) //r : 서브.. 2022. 10. 11. [자료구조] 힙(Heap) 우힙힙힙 ^ㅇ^ 우히히 좌히히(웃기다!) 힙 - 완전이진트리이면서, 모든 노드의 key값이 각 자식노드들의 key값보다 크거나 작은 heap property를 지키는 자료구조 - heap property가 부모가 자식보다 큰 것인 경우 Maxheap이 되고, 작은 것인 경우 Minheap이 된다. - 주로 Priority queue로 사용된다. - 완전이진트리여야한다는 점에서 array로 구현이 용이하다. (i, 2i, 2i+1) 삭제 (O(logn)-최악 theta(logn), 최선 theta(1)) 1. root를 제거한다. 2. 마지막 노드를 root로 옮긴다. 3. heap property에 맞게 Percolate down한다. - 최대 logn 회의 교환이 일어난다. * Percolate dow.. 2022. 10. 10. [자료구조] Queue와 Stack 큐와 스택 큐 : First-In-First-Out(FIFO) 자료구조 스택 : Last-In-Last-Out(LIFO) 자료구조 큐 큐의 Circular 구조 - 사용하는 이유 : enqueue, dequeue를 반복하다 보면 앞부분이 비어 버리기 때문. - 구현법 1) ArrayList-based 구현의 경우 : 인덱스 사용할 때 모듀로 n 연산을 하면 되지 않을까요? 2) LinkedList-based 구현의 경우 : circular linked list를 사용한다. - 주의사항 : 어떤 구현 방법이든, Empty, Full을 front와 tail로 판단할 수 없기 때문에 길이를 저장해 둔다. 큐와 스택의 적용 큐 : BFS 스택 : DFS, 후위표기법 계산기, 괄호 판별하기, 함수 호출 큐, 스택.. 2022. 10. 10. [자료구조] 리스트(List) 리스트란 여러 원소들을 연결하여 저장하는 자료구조를 말한다. 연속된 공간 내에 물리적으로 연결되어 있을 수도 있고, 비연속적인 공간 내에 논리적으로 연결되어 있을 수도 있다. Array 혹은 Linked List로 구현한다. Array List - 내부적으로 배열을 운영하여 연속적 공간에 원소를 저장한다. - 장점 1) 배열을 운영하기 때문에 인덱스로 접근하는 것이 O(1) 만에 이루어진다. (Random Access 가능) 2) 직관적이고 간단하다. - 단점 1) 삽입/삭제에 shift가 필요하기 때문에 O(n)이 걸린다. 2) 배열의 고정된 크기를 넘어서는 경우 copy가 필요하다. Linked List - 내부적으로 포인터를 가진 구조체들을 운영하여 비연속적인 공간에 논리적으로 연결된 원소들을 저장.. 2022. 10. 10. 01. 객체지향 프로그래밍이란 무엇인가?(OOP, JAVA) 컴퓨터 프로그래밍, 논리 설계 같은 기본 강의들을 수강한 지 시간이 좀 지나서 기초 CS지식을 좀 까먹은 감이 있다. 기억을 떠올릴 겸 정리해 보기로 했다. 자료는 서울대학교 컴퓨터공학부 이영기 교수님의 [컴퓨터 프로그래밍]을 참고했다. 객체 객체지향 프로그래밍에서 클래스의 인스턴스이다. 클래스는 어떤 entity의 method나 attribute(멤버들)를 정의하는 틀이고, 이 틀에 맞게 실제 메모리 공간이 할당된 것을 인스턴스라 한다. 절차지향 프로그래밍에서는 하나의 명령어나 하나의 데이터를 객체라 한다. (몰랐다.) 객체지향 프로그래밍(Object Oriented Programming, OOP) 객체지향 프로그래밍이란 프로그램을 객체들의 상호작용으로 보고, "어떤 객체를 만들 것이며, 그 객체의 역.. 2022. 10. 1. 01. 재귀 1. Recursive Algorithm Recursive Algorithm : subproblem을 해결하기 위해 자기 자신을 호출하는 알고리즘 subproblem은 original problem과 유형 및 해결 방법이 동일하다. 이 알고리즘을 사용하면 복잡한 original problem을 subproblem의 합으로 구할 수 있다. 예 : 정렬, 탐색, 수열 ... 몇몇 문제를 더 간단하게 해 준다. 예 : 정렬, 탐색 ... 몇몇 문제는 더 복잡하게 만들어서 치명적인 문제를 발생시킨다. 특히 재귀 호출 과정에서 중복 호출이 일어나는 경우 치명적으로 비효율적인 알고리즘이 된다. 예 : 피보나치 수 구하기, 최적 행렬 곱 경로 ... 2. Recursive Algorithm 예시 1 - 재귀 알고리즘.. 2021. 3. 5. 이전 1 다음
