주니어 개발자 성장기

트리란? 계층적 구조를 나타내는 자료구조로, 부모-자식 관계의 노드들의 집합 대용량 데이터를 저장하기 용이한 자료구조다. Why? 탐색이 아주 빠르기 때문이다. 선형 자료구조와 달리 탐색의 시간 복잡도를 O(log N)로 줄일 수 있다. (단, 삽입 삭제의 최소 O(log N)의 시간 복잡도를 갖는다.) 트리의 구성요소 Node Edge Sibling Subtree Root node Leaf Node(Terminal Node) Level Height, Degree 이진 트리(Binary Tree) 모든 노드가 최대 2개의 서브 트리를 갖는 트리 모든 노드의 차수가 2 이하인 트리 이진트리의 서브트리는 이진트리라는 재귀적 정의를 갖고 있다. 특징 노드 개수가 n이면 엣지의 개수는 n-1 높이가 h인 이진 ..

큐란? FIFO(선입선출)의 구조를 갖는 자료구조 Rear(후단)으로 데이터를 넣고, Front(전단)으로 데이터를 빼는 자료보관이 가능한 자료 구조이다. 응용 시뮬레이션의 대기열 통신에서 데이터 패킷들의 모델링 프린터와 컴퓨터 사이의 버퍼링(성능차) CPU의 태스크 스케줄링(Task Scheduling) 다양한 이벤트 구동 방식( Event-driven) 컴퓨터 시뮬레이션 이진 트리의 레벨 순회(Level-order Traversal) 그래프의 너비우선탐색(BFS) 등 ADT Objects: 0개 이상 n개의 원소를 가진 유한 순서 리스트 Functions Queue createQueue() queue 만들기 Bool is_empty(queue) queue가 비어있는 지에 대한 Bool값을 return..

거듭 제곱을 구할 때 우리는 보통 $$a^n = a*a*a* \cdots *a$$를 떠올린다. 즉, a를 n번 무식하게 곱하는 것이다. 하지만 이것을 컴퓨터가 연산한다면, 시간복잡도가 어떻게 될까? int main(void) { int a, n; cin >> a >> n; //a^n을 선형 시간 복잡도로 곱한다. long long result = 1; for (int i = 0; i a >> n; ll result = 1; while (n > 0) { //n이 홀수일 경우 즉, 이진수의 가장 아래 자리수가 1인 경우 if (n % 2 == 1) result = (a * result); a = (a * a); //이 비트 연산은 수슬 이진수 자릿수를 1..