주니어 개발자 성장기

트리란? 계층적 구조를 나타내는 자료구조로, 부모-자식 관계의 노드들의 집합 대용량 데이터를 저장하기 용이한 자료구조다. 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..

스택? 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조 스택은 자료구조 그 자체로서는 단순하지만 여러 알고리즘에서 쓰일 수 있다. 전위 표기법 -> 후위 표기법 전환 후위 표기법의 연산 괄호 검사 문자열 역순으로 재배치 실행 취소(undo) 재귀 알고리즘 웹 브라우저의 방문기록(뒤로가기) 재귀 알고리즘 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다. 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다. 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다. 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다. (출처: https..

연결리스트(Linked List)란? 정의: 추상적 자료형인 List를 구현한 자료구조로서, 노드(Node)를 하나의 Data라고 정의할 때 Node에 실제로 필요한 value뿐만 아니라, 포인터 변수로 다음 데이터의 주소를 저장해놓는 것이다. 장점 추가/삽입/삭제 가 빠르다. 연속된 메모리 공간이 필요하지 않다. 단점 : 순차적 탐색만 가능하기 때문에, 탐색의 속도가 느리다. 탐색, 정렬을 자주 하면 배열, 추가/삭제가 많으면 연결리스트를 사용한다. *B+ tree라는 자료구조는 연결리스트 + heap의 모양새로, 데이터의 추가/삭제/정렬/조회 모두에 용이하다. 구현 방법 1. 단순 연결 리스트(Singly Linked List) 다음 노드에 대한 참조만을 가지는 가장 단순한 형태의 연결 리스트다 탐색..

재귀함수란? 재귀함수: Recursive function 재귀, 즉 직접적, 간접적으로 자기 자신을 다시 호출 하는 함수로서 탈출조건이 반드시 있어야 한다. 재귀함수의 기저사례 재귀함수의 디자인 사례 재귀함수를 어디에 쓸것인가? 재귀함수의 기저사례 기저사례(Base Case)란 재귀함수의 필수적인 요건으로, 무한루프를 막고 함수를 끝내기 위해 반드시 필요하다. 기저사례를 놓칠 경우 예측불가능한 결과가 도출된다. 재귀함수의 디자인 재귀 알고리즘으로 쉽게풀 수 있는 문제들이 있다. 대표적인 것이 바로 하노이의 타워다. 1. 직접 호출(출처:https://www.geeksforgeeks.org/recursive-functions/) 코드: #include using namespace std; // Assu..

교재 : 윤성우의 열혈 자료구조 언어 : C 장소 : 중앙도서관 스터디룸 멤버 : 이준표, 최이섭 자료구조를 배워야 하는 이유 자료구조의 종류 시간 복잡도 자료구조를 배워야 하는 이유 자료구조란 '데이터의 표현 및 저장 방법' 을 의미한다면, 알고리즘은 자료구조를 대상으로 하는 '문제의 해결 방법'을 의미한다. int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 위와 같은 배열 선언은 '자료구조'적 측면의 코드라고 할 수 있다. 반면, 다음과 같은 코드는 '알고리즘'적 측면의 코드다. (데이터의 합을 구하는) for (int i = 0; i < n; ++i) { sum += arr[i]; } 보다시피 알고리즘에는 자료구조가 필연적으로 사용된다. 위의 알고리즘은 배열을 사..