Hope Everyone Is Happy

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링 *비선형 자료 구조 : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조 ◆ 맵 (map) - 맵은 특정 순서에 따라 키(Key)와 매핑된 값(Value)의 조합으로 형성된 자료구조 ex) Key : 모르고리즘, SSAFY, CS_Study, 모각공 Value : 0, 1, 2, 3 Map : , , , - 레드 블랙 트리 자료구조를 기반, 삽입하면 자동 정렬 - 맵을 쓸 때는 map 형태로 구현 - 배열과 비슷하게 clear()함수로 맵에 있는 모든 요소 삭제 가능 - size()로 크기 반환 가능, erase()로 특정 키와 키에 매핑된 값 삭제 가능 - map은 해시 테이..

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링 *비선형 자료 구조 : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조 ◆ 힙 (Heap) - 완전 이진 트리 기반의 자료 구조이며 최소힙, 최대힙 두 가지가 있음 - 최대힙 : 루트 노드에 있는 값은 모든 자식 노드의 값들 중 가장 커야 함, 각 노드의 자식 노드들 또한 같은 속성 ex ) 99는 나머지 노드들 보다 높은 값 88은 11, 22 보다 높은 값 - 최대힙의 삽입 : 힙에 새로운 요소가 들어오면, 일단 새로운 노드들의 마지막 노드로 삽입 후 부모느들과의 크기를 비교하며 위치를 교환 ex) 최대힙의 삽입- step 1 : 90을 마지막에 삽입 최대힙의 삽입 - s..

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링 *비선형 자료 구조 : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조 ◆ 트리 (Tree) - 정보의 항목들이 가지(Branch)로 연결되어 자료를 구성되고, 노드 사이의 관계가 계층적 - 그래프 자료 구조의 부분적 표현으로, 노드(정점)와 가지(간선)로 구성 - 즉, 정점인 노드와 각각의 노드를 연결시켜 주는 선분인 가지로 형성된 구조 - 트리는 같은 경로에서 어떤 노드보다 위에 있으면 해당 노드를 부모 노드, 아래에 있으면 자식 노드 ex) 위 트리 예시에서 A 노드는 B의 부모 노드, B노드는 A노드의 자식 노드 - 같은 부모 노드 들은 형제 노드 ex) 위 트리 예시..

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링 *비선형 자료 구조 : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조 ◆ 그래프 (Graph) - 정점(Vertex)과 간선(Edge)으로 연결 되어 있는 원소들의 관계를 표현한 자료 구조 - 예시 : 위와 같은 구조에서 A,B,H,D,G,F,E == 정점(Vertix), 정점들 사이를 잇는 선 == 간선(Edge) - G = (V,E)로 정의, V는 정점의 집합, E는 간선들의 집합 - 무방향 그래프 : 간선의 방향이 정해져있지 않은 그래프 - 단방향 그래프 : 간선의 방향이 한 방향으로만 설계되있는 그래프 - 양방향 그래프 : 간선의 방향이 양 방향으로 설계 되있는 그래..

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링 *선형 자료 구조 : 요소가 일렬로 나열되있는 자료구조 ◆ 스택 (Stack) - 스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오게 되는 자료구조 - Last in First Out (LIFO) 구조 - 재귀적인 함수 or 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰임 - 삽입 및 삭제에 O(1), 탐색에 O(n) #include #include using namespace std; int main() { stack stackSample; // 0~9까지 차례대로 삽입 for(int i =0; i < 10; i++) stackSample.push(i); // 9..

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링 *선형 자료 구조 : 요소가 일렬로 나열되있는 자료구조 ◆ 벡터 (vector) - 동적으로 요소를 할당할 수 있는 배열 - 중복을 허용하고 순서가 있으며 랜덤 접근이 가능 - 맨뒤나 맨앞이 아닌 요소를 삽입과 삭제에 O(1), 맨뒤나 맨앞이 아닌 경우, O(n) - vector에서의 push_back 은 뒤에 메모리 공간이 없으면 할당하여 값을 입력, 메모리 공간이 있으나 값이 비어 있으면 값만 할당 - C++ 라이브러리에서 vector 자료형에 관한 다양한 함수 구조 지원 ex) push_back, pop_back, erase, find() , clear() #include #..

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링 *선형 자료 구조 : 요소가 일렬로 나열되있는 자료구조 ◆ 연결 리스트 (Linked List) - 연결리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료구조 - head 노드 에서 시작되어 tail 노드로 끝나는 구조 - 삽입과 삭제에 O(1), 탐색에는 O(n) 소요 - 싱글 연결 리스트 (Single Linked List)는 노드가 한방향으로 연결되어 있는 연결리스트 : next포인터로 다음 노드로 연결 ex) struct ListNode { int nData; ListNode* next; } int main(){ ListNode* FirstN..

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링 ◆ 시간 복잡도 & 빅오 표기법 - 시간 복잡도란 '문제를 해결하는데 걸리는 시간과 입력의 함수 관계' - 설계한 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타내느데 쓰이며, 보통 빅오 표기법으로 표시 ex) 입력 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 10n2+n 이라고 하면, 아래와 같이 코드 구성 가능 (C++) for (int i = 0; i < 10; i++) { for(int j = 0; j < n;j ++) { for(int k = 0; k < n; k++) { if(true) cout