재민

스택을 구현하기 위해서는 이전 포스팅에서 다루었던, 배열을 이용하는 방법과 연결리스트를 이용하는 방법이 있다. 연결리스트는 단순 연결 리스트를 이용하여 진행한다. 단순 연결리스트에서 변수의 top은 가장 최근에 삽입된 요소를 가리키는 변수가 된다. (head와 유사) 초기화시에는 top= NULL로 설정하는데, 이는 공백 스택을 의미한다. 스택에서 가장 먼저 삽입된 요소는 마지막 노드가 되므로(스택의 특징) link field를 NULL로 설정하여야 한다. 그리고 가장 최근에 삽입된 요소는 첫번째 노드가 된다. 이는 단순 연결리스트에서 첫 번째 노드로 삽입하는 연산과 동일하다. [스택 구현: 연결리스트 이용 방법 by 재민] #스택 구현: 연결 리스트 이용 by 재민 class Node: def __in..

스택을 구현하기 위해 배열을 사용할 경우, 일차원 배열 stack[MAX_STACK_SIZE] 를 사용한다. 스택의 변수 top은 가장 최근에 삽입된 요소를 가리키는 변수로, 초기값을 -1로 세팅한다(공백 스택을 의미) 스택에서 가장 먼저 삽입된 요소는 stack[0]에, 가장 최근에 삽입된 요소는 stack[top]에 저장된다 (스택의 개념) [c코드로 스택 구현] #include #define MAX_STACK_SIZE 100 typedef struct { int stack[MAX_STACK_SIZE]; int top; } Stack; // 스택 초기화 void initializeStack(Stack *s) { s->top = -1; // 초기값으로 -1을 설정하여 공백 스택을 나타냄 } // 스택이..

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있어서, 양방향으로 탐색이 가능하며, 삭제 시 양쪽의 연결을 수정해야 한다. Doublely Linked List에서 노드의 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 오른쪽 노드와 왼쪽 노드를 탐색한다. 2) 삭제할 노드의 오른쪽 주소를 삭제할 노드의 왼쪽 노드의 rlink에 저장한다. 3) 삭제할 노드의 왼쪽 노드 주소를 삭제할 노드의 오른쪽 노드의 llink에 저장한다. 4) 삭제할 노드를 삭제한다. [코드로 구현하기] #include #include // 이중 연결 리스트의 노드 구조체 정의 struct Node { int data; struct Node* llink; // 왼쪽 노드를 가리키는 포인터..

Natural Join은 두 테이블 간에 동일한 이름을 가진 열들을 기반으로 자동으로 결합하는 데이터베이스의 쿼리의 일종이다. Natural Join은 Join시 위험성이 존재하는데, 그 위험성들은 다음과 같다. 1) 의도하지 않은 결합: Natural Join은 열 이름이 동일한 열들을 기반으로 결합하기 때문에, 열 이름이 동일하지만 실제로는 서로 다른 데이터를 나타내는 경우에는 오류가 발생할 수 있다. 2) 향후 스키마 변경에 대한 취약성 : 새로운 열이 추가되거나 삭제될 시 혼란이 생김 3) 쿼리 이식성의 감소 : 다른 데이터베이스로 쿼리를 이식하는 데 무리(특정 열 이름에 의존하기 때문) 4) 성능저하: 다른 조인들보다 많은 계산을 필요로 하기 때문에 성능 저하가 될 수 있음

Doubly Linked List는 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트이다. linked list에서와 마찬가지로 중간노드, 첫번째 노드, 마지막 노드 삽입을 나누어서 보도록 하겠다. https://imsunbow.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-List-%EC%82%BD%EC%9E%85%EC%A4%91%EA%B0%84-%EB%85%B8%EB%93%9C-%EC%B2%AB%EB%B2%88%EC%A7%B8-%EB%85%B8%EB%93%9C%EB%A7%88%EC%A7%80%EB%A7%89-%EB%85%B8%EB%93%9C%EB%A1%9C-%EC%82%BD%EC%9E%85 [같이 보면 좋은 자료: linked lis..

Linked List에서 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 앞 노드를 찾는다. 앞 노드를 찾는 이유는 크게 두가지인데, 연결관계를 해제하기 위해서이자 노드를 효율적으로 찾아 해제시키는 방법이기 때문이다. 2) 앞 노드의 링크필드에 삭제할 노드의 링크 필드값을 저장한다. 3) 삭제할 노드를 삭제하고, 메모리를 해제한다. 삭제 연산을 c로 구현하면 다음과 같다. #include #include // 단일 연결 리스트의 노드 정의 struct Node { int data; struct Node* next; }; // 연결 리스트의 헤드를 전역 변수로 선언 struct Node* head = NULL; // 연결 리스트에 노드 추가 void insertNode(int val) { str..

연결 리스트에서 삽입은 어느 위치에 노드를 삽입하느냐에 따라 다르다. [중간 노드 삽입] 1. 삽입할 노드를 준비한다 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드의 링크값을 지정한다. 이 때 링크값은 삽입할 위치 앞 노드의 링크값이 된다. 4. 삽입할 위치 앞 노드에 새 노드를 연결한다. [첫번째 노드 삽입] 1. 삽입할 노드를 준비한다. 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드의 링크값을 지정한다. 이 때 링크값은 head가 가리키고 있는 노드의 주소값이 된다. 4. head에 새 노드를 연결한다. [마지막 노드로 삽입] 1. 삽입할 노드를 준비한다. 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드가 마지막 노드이므로 링크값으로 NULL을 지정한다. 4...

연결리스트에서 탐색은 다음과 같은 과정으로 이루어진다. 1. 헤드에서 시작 : 검색을 시작하기 위해 연결리스트의 헤드부터 탐색을 시작한다. 2. 노드 순회: 각 노드를 순차적으로 방문하면서 원하는 값을 찾을 때까지 계속 진행한다. 3. 비교 연산: 각 노드에서 찾고자 하는 값을 현재 노드의 데이터와 비교한다. 값을 찾을 경우 검색을 종료하고 노드의 위치를 반환하지만, 찾지 못할 경우에는 검색이 실패했다고 출력하게 된다. 다음은 자료구조 상에서 search 연산 예제이다. #include #include // 연결 리스트의 노드 구조체 정의 struct Node { int data; struct Node* next; }; // 연결 리스트에서 값 검색하는 함수 struct Node* search(struc..

리스트는 자료를 구조화하는 가장 기본적인 방법으로서, 값들을 나열한다. 리스트에서는 새로운 항목을 리스트의 처음, 중간,끝에 삽입하여 저장할 수 있다. 그리고 리스트의 특정 부분을 추출하거나 특정 값을 삽입 혹은 삭제할 수 있다. 리스트는 구현이 간단하지만 삽입 삭제시 오버헤드가 발생할 가능성이 있는 Linear List와, 삽입 삭제가 효율적이지만 구현이 복잡한 Linked List로 나뉜다. Linked List에서 한 원소가 삽입되면, 그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시켜야만 한다. 삽입을 위해서는 먼저 원소를 삽입할 빈 자리를 만들어서, 빈 자리에 원소를 삽입한다. (빈 자리를 만들기 위해 기존의 원소들은 한칸씩 뒤로 이동시킨다) 즉 n+1개의 ..

하노이탑의 제약조건은 다음과 같다. - 한 번에 하나의 원판만 이동 가능 - 맨 위에 있는 원판만 이동 가능 - 크기가 작은 원판 위에 큰 원판을 쌓을 수 없음 원반 N개를 A에서 C로 이동시키려면, 우선 작은 원반 1개를 A에서 B로 이동시키는 과정이 선행되어야 한다(그래야 마지막 원반을 C에 놓고 다음 프로세스 진행 가능) 그 다음 큰 원반을 A에서 C로 이동시키고, 작은 원반 n-1개를 B에서 C로 이동시킨다. c로 구현시 핵심 코드는 다음과 같다 if (n == 1) printf("Disk1: %c > %c\n, from, to) else{ hanoi(n-1,from,to,tmp); print("Disk%d: %c > %c \n, from, to); hanoi(n-1,tmp,from,to); }