CS30 Heap 사전학습 PriorityQueue 큐를 활용한 자료구조. 데이터 들의 우선순위를 가지고 있다. 먼저 들어간 것이 먼저 나오는 것이 아니다. 우선순위를 지정할 수 있는 데이터의 기준을 정하여 우선순위가 높은 데이터가 먼저 나가는 자료구조. 힙을 사용하여 활용된 자료구조이다. HEAP 완전 이진 트리이다. ※마지막 레벨을 제외한 모든 서브트리의 레벨이 같고, 마지막 레벨은 무조건 왼쪽 부터 채워줘야 한다. 최대 힙과 최소 힙으로 이루어져 있다. 최대 힙 : 루트노드로 올라 갈 수록 저장된 값이 커지는 구조. 최소 힙 : 루트노드로 올라 갈 수록 저장된 값이 작은 구조. 최대 힙,최소 힙 둘다 노드에 우선순위가 가장 높은 것이 자리잡는다. 중복 된 값을 허용한다.(이진 탐색 트리에서는 중복이 허용되지 않는다... CS/DataStructure 2021. 3. 30. Tree Tree 비선형 자료구조 이다. Hierachical 관계를 갖는다.(= 부모와 자식 관계를 갖는다) 트리는 DAG의 한 종류다( Directerd Acyclic Graphs 방향성 있는 비순환 그래프) 검색에 효율적인 구조를 갖는다. ※트리 관련 용어 Node : 트리 구성 각 요소. Edge : 트리를 구성 하기 위한 노드 간 연결을 하는 선. Root Node : 트리 구조에서 가장 위에 있는 노드. Terminal Node(=Leaf Node) : 하위에 따른 노드가 연결되지 않은 노드. Internal Node : Terminal 노드를 제외한 모든 노드로 루프 노드를 포함한다. +++ 노드의 크기 : 자신을 포함한 모든 자손의 노드 개수 노드의 깊이 : 루트에서 어떤 노드에 도달하기 위해 거쳐.. CS/DataStructure 2021. 3. 30. Stack and Queue Stack LIFO(Last In First Out) 구조.(입구/출구가 하나) 차곡 차곡 쌓이는 구조로 먼저 들어간 원소가 가장 먼저 나온다. 먼저 들어간 것이 먼저 나오는 것이 아닌 나중에 나온다. 활용예시 브라우저의 방문 기록 (뒤로가기) 역순 문자열 만들기(가장 마지막에 들어간 것이 마지막에 나온다) 실행 취소. 후의 표기법. 수식의 괄호 연산. 재귀 호출의 구조 방식. DFS Queue FIFO(First In First Out) 구조.(먼저 들어간 것이 먼저 나온다.) Stack 과 정반대로 입구/출구가 각각 따로 존재하며 1개씩 갖는다. 일상 생활에서 흔히 볼 수 있는 질서 있는 형식이다. 큐의 활용예시 프린터의 인쇄 은행 창구(먼저 와서 대기 순번을 발급받은 대로) 콜센터 고객 대기 시간 .. CS/DataStructure 2021. 3. 30. Array vs Linked List Array 논리적 저장 순서와 물리적 저장 순서가 일치.(index를 활용하여 해당 element에 접근 할 수 있다.) 해당 원소에 인덱스를 알고 있으면 O(1)이라는 시간 복잡도를 갖는다. Random Access가 가능하다. 하지만 삭제 또는 삽입과정에서 비용이 많이 발생한다. 해당 원소의 삽입 과정에서 맨 뒤의 경우를 제외하고 원소들이 있는 처음 또는 중간에 넣게 된다면 삽입할 공간을 만들기 위해 해당 원소들이 뒤로 이동해야하는 비용이 발생한다. 해당 원소의 삭제 과정에서 해당 원소를 삭제 한 후 빈 공간이 생긴다. 이 빈 공간을 매우기 위해 빈 공간 다음으로 이어지는 원소들을 한 칸씩 앞으로 떙겨야 하므로 비용이 발생한다. 비용에 대한 시간 복잡도는 O(n) 이다. Linked List 배열에 .. CS/DataStructure 2021. 3. 30. 개발상식 좋은 코드란 목적대로 잘 동작하는 코드 가독성이 좋은 코드 코드리뷰에 대한 시간이 줄어든다. 다른 곳에서 사용하기 용이하다. 버그가 발생했을 때 파악하기 용이하다. 중복이 없는 코드 재사용성이 좋다. 코드가 간결해진다. 객체 지향 프로그래밍이란 컴퓨터 사고 중심의 패러다임에 벗어나 인간 중심적 프로그래밍 패러다임이라 한다. 현실 세계를 프로그래밍적인 관점으로 옮겨와 하는 것이다. 사물들의 특징들을 가지고 프로그래밍 하는 것.(정적인 개념,추상적 개념==객체) 장점 코드의 재사용성. 객체 단위로 나누어져 코드가 작성되므로 디버깅과 유지보수가 용이하다 대형 프로젝트에 적합(클래스 단위로 모듈화) 단점 객체간의 메시지 교환으로 많은 오버헤드가 발생한다. 설계 단계에 많은 시간과 노력이 필요. + 객체 지향의 .. CS/Basic 2021. 3. 22. 이전 1 ··· 3 4 5 6 다음