창문을 열심히 닦아요

단순연결리스트 = 선형연결리스트 = 체인 각각의 노드가 하나의 포인터를 갖는 구조로 포인터는 다음 노드를 가리킨다. 포인터를 이용해 순차탐색하므로 시간 복잡도는 O(n) 마지막 노드의 링크는 null로 표현 해싱 기법에서 오버 플로 처리시 체이닝 기법에서 이용된다. 연결리스트 삽입 void insert(listPointer *first, listPointer x) { /* 입력데이터가 10인 노드를 fisrt의 노드 뒤에 삽입 */ listPointer temp; MALLOC(temp, sizeof(*temp)); temp -> data = 10; if (*first) { temp->link = x->link; x->link = temp; } else { temp->link = NULL; *first =..

1. 다원 탐색 트리(Multiway search tree) m-원 탐색 트리 (m-way search tree)라고도 한다. 다원 탐색 트리는 한 노드 안에 최대 m-1개의 요소와 m개의 자식을 가질 수 있다. 이진 탐색 트리는 m=2 인 다원 탐색 트리 2. B 트리 Balanced Tree. 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 균등한 응답속도를 유지하기 위해서 리프 레벨에서 좌우 균형을 유지한다. 모든 노드는 최대 m개의 자식들을 가진다. 루트 노드와 리프 노드가 아닌 모든 노드는 최소 m/2개의 자식을 가진다. 루트노드는 최소 2개 이상의 자식을 가진다. k개의 ..

[5장. 재귀 알고리즘] 1. 재귀의 기본 재귀란? 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라 한다. 재귀를 효과적으로 사용하면 프로그램도 간결하게 표현할 수 있다. 팩토리얼 구하기 음이 아닌 정수의 팩토리얼을 구하는 방법은 재귀적으로 정의할 수 있다. TODO 재귀 호출 소스코드 직접 재귀(direct) : 자기 자신과 같은 메서드를 호출하면 직접 재귀이다. 간접 재귀(indirect) : 메서드 a가 메소드 b를 호출하고, 다시 메소드 b가 메소드a를 호출하는 구조이다. int factorial(int n) { if (n == 1) return 1; // 1을 반환하고 재귀호출을 끝냄 return n * factorial(n - 1); // n과 factoria..

이전에 정리한 내용이 있지만, 책을 보며 예제 풀이를 진행하는 것이라 한 번 더 포스팅한다. [4장. 스택과 큐] 1. 스택 스택이란? 스택은 데이터를 일시적으로 저장하기 위한 자료구조이다. 후입 선출 방식(LIFO)으로 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. push : 스택에 데이터를 넣는 작업 pop : 스택에서 데이터를 꺼내는 작업 top : push와 pop을 하는 위치 bottom : 스택의 가장 아랫부분 스택 만들기 생성자 IntStack : 생성자는 스택 본체용 배열을 생성하는 등 준비작업을 수행한다. 생성시 스택은 비어있으므로 스택 포인터는 0을 가리킨다. 푸시 메소드 push : 스택에 데이터를 넣는 메소드이다. 스택이 가득차서 푸시할 수 없을 경우는 예외처리를 해준다. 포인터값..

[3장. 검색] 1. 검색 알고리즘 검색과 키 검색 : 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 것이다. 키 : 주목하는 항목. 키는 데이터의 일부에 해당한다. 조건은 하나만 지정하기도 하지만 논리곱이나 논리합을 사용하여 복합해서 지정하기도 한다. 배열에서 검색하기 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법이다. 오픈주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다. 데이터의 검색, 추가, 삭제에 소요되는 비용을 종합적으로 계산해..

자료구조와 함께 배우는 알고리즘 입문을 통해 자료구조 기초를 쌓아보자! [2장. 기본 자료구조] 1. 배열 자료구조 : 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계 데이터 단위는 데이터를 구성하는 한 덩어리. 자료구조는 쉽게 말해 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법. 배열 : 같은 자료형의 변수로 이루어진 구성요소가 모인 것 배열 본체를 생성하는 본체에 대한 참조를 생성. 본체를 참조하는 배열변수. 인덱스. 배열은 같은 형의 구성요소가 직선 모양으로 속하여 줄지어 있는 단순한 자료구조. 배열의 구성요솟수를 알고 있는 경우 int[] a = new int[5];와 같이 선언한다. 또는 배열의 변수 선언과 본체 생성을 따로 수행하는 것도 가능하다. //선언하기 int[..

자료구조와 함께 배우는 알고리즘 입문을 통해 자료구조 기초를 쌓아보자! [1장. 기본 알고리즘] 1. 알고리즘이란? - 값과 최댓값 순차적 구조 : 여러 문장(프로세스)이 순차적으로 실행되는 구조 선택 구조 : 식의 평가결과에 따라 프로그램의 실행 흐름을 변경하는 if문 개발할 때 순서도(플로우 차트)를 그리는 습관을 가지는 것이 좋다! 개발 구상이 복잡하거나, 팀원들과 전체 서비스 흐름을 공유하고 검토받는 데 유용하다. 알고리즘 : 문제를 해결하기 위한 것으로 명확하게 정의되고 순서가 있는 유한개의 규칙으로 이루어진 집합 - 조건 판단과 분기 연산자 : +,- 등의 연산기호 단항 연산자 : 피연산자 1개 a++ 2항 연산자 : 피연산자 2개 a < b 3항 연산자 : 피연산자 3개 a ? b : c 피..

Heap 힙은 자료구조의 일종으로 트리 형식을 하고 있다(Complete Binary Tree). 트리에서 가장 작은 원소를 최상위 루트에 두게 한다. 순서를 가진 큐나 리스트의 가장 작은 원소에 빠르게 접근해야 하는 경우에 유용하다. 우선 순위 큐(Priority Queue)를 위해 만들어진 자료구조다. 각 노드는 자신의 자식보다 작으므로 원소들을 순서대로 위치시키고 싶을 때 가장 유용한 방법은 아니다. 힙 트리에서는 중복값을 허용한다. 배열에 트리의 값들을 넣어줄 때, 0 번째는 건너뛰고 1 번 index 부터 루트노드가 시작된다. (= 노드의 고유번호 값과 배열의 index 를 일치시켜 혼동을 줄인다.) 부모노드와 자식노드를 찾기 쉽다. 왼쪽 자식 노드의 인덱스 = (부모 인덱스) * 2 오른쪽 자..

Map 맵은 hash라고도 불린다. 배열이나 딕셔너리와 관련 있는 key-value 형태의 저장소이다. 키 값은 트리상에서 한 번만 나타난다(중복되지 않는다). 만약, 동일 키로 다시 데이터를 입력할 경우 원본 키에 있던 값은 덮어씌워진다. Map의 종류 HashMap : Map 인터페이스를 구현하기 위해 HashTable을 사용한 클래스. 중복을 허용하지 않고 순서를 보장하지 않음. key와 value로 null이 허용 HashTable : HashMap보다 느리지만 동기화를 지원한다. key와 value로 null이 허용되지 않는다. TreeMap : 이진 검색 트리의 형태로 key-value 쌍으로 이루어진 데이터를 저장한다. 정렬된 순서로 키, 값 쌍을 저장하므로 빠른 검색이 가능하다. 저장 시 ..

자료구조의 분류 선형구조 : array, linked list, stack, queue, deque 비선형구조 : tree, graph Tree 트리는 자식이라 부르는 서로 다른 원소를 많이 나열할 수 있는 자료구조이다. (저장보다 표현에 집중하는 자료구조) 노드와 브랜치를 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태이다. 사용 예시 : 가족의 족보, 연산 수식, 회사조직도, heap 등을 표현하기에 적합 노드 : 트리의 기본요소. 자료항목과 다른 항목에 가지를 합친 것을 의미한다. 근노드 : 트리의 맨 위에 있는 노드이다. 차수(degree) : 각 노드에서 뻗어나온 가지의 수. 트리의 차수 : 노드들의 차수들 중에서 가장 많은 수. 단말노드(Terminal Node) = Leaf No..