728x90 반응형 자료구조, 알고리즘3 [자구, 알고] 트리, 그래프, 인접행렬, 인접리스트 질문답변 ● Binary Tree (이진 트리) - 자식노드가 최대 두 개인 노드들로 구성된 트리 ● Full Binary Tree (전 이진 트리) - 모든 노드가 0개 혹은 2개의 children 을 가지고 있을 때 - leaf 노드들을 제외한 모든 노드들이 2개의 children 을 가지는 것. ● Complete Binary Tree (완전 이진 트리) - 마지막 level 을 제외한 나머지 level 에 node 들이 가득 차있고, 마지막 level 에서 node 는 가장 왼쪽 부터 채워지는 형태 - 데이터의 크기는 상관하지 않음 ● Perfect Binary Tree (포화 이진 트리) - 모든 internal node 가 두개의 children 을 가지고 있고, 모든 leaf 노드가 같은 level .. 2023. 4. 7. [자구, 알고] Array, List, LinkedList, heap 질문답변 ● Array vs List 차이점 - Array - 메모리 상에 데이터가 연속적으로 저장 - 사용할 크기를 미리 할당하기 때문에 고정된 크기를 갖는다. 그래서 메모리 낭비가 생길 수도 있다. 10을 할당했는데 데이터를 5개만 넣으면 5가 낭비된다. - 인덱스로 접근할 수 있다. - int[] numArray = {1, 2, 3}; -> numArray[0] 인덱스 접근 가능 - List - 메모리 상에 데이터가 비연속적으로 저장 - 사용할 크기를 미리 할당하지 않아도 된다. 때문에 메모리 낭비가 없다. - 인덱스로 접근할 수 없다. - List numList = List.of(1, 2, 3); -> numList.get(0) 인덱스 접근 불가능 - List는 인터페이스이다. - LinkedList, A.. 2023. 4. 7. [자구, 알고] 복잡도, 빅오, 스택, 큐 질문답변 ● 시간복잡도와 공간복잡도에 대해 설명해 주세요. - 시간복잡도 : 알고리즘을 수행하는데 시간이 얼마나 걸리는가를 표기하는 것 - 공간복잡도 : 알고리즘을 수행하는데 얼만큼의 공간(그러니까 RAM이나 하드디스크의 메모리 같은 곳)이 필요한가를 표기하는 것 ● 빅오, 빅오메가, 빅세타 - 빅 오(Big-Oh) 표기법 : 최악의 경우 - 빅 오메가(Big-Omega) 표기법 : 최선의 경우 - 빅 세타(Theta) 표기법 : 빅 오와 빅 오메가의 공통부분. 최소와 최악의 중간인 평균적인 복잡도 https://vaert.tistory.com/117 ● 다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요? - 현실에서는 항상 최악의 경우를 생각해야 하기 때문. 빅-오메가나 빅 세타를 이용해서 자원을.. 2023. 4. 7. 이전 1 다음 728x90 반응형
