Brute force Study

이중 연결 리스트(Doubly Linked List)링크드 리스트의 탐색 기능을 개선한 자료구조양방향 탐색이 가능함 (vs 싱글의 단방향)자신 앞에 있는 노드를 가리키는 포인터를 가짐으로써 양방향 탐색이 가능함구조체typedef int ElementType;typedef struct tagNode{ ElementType data; // 저장할 데이터 struct tagNode* prevNode; // 앞 노드의 주소와 데이터 struct tagNode* nextNode; // 뒤 노드의 주소와 데이터} Node; 더블 링크드 리스트의 주요 연산기존 링크드 리스트의 연산과 동일(명세는 구현방식과 상관없이 동일함)노드의 생성/소멸 연산노드의 생성Node* ..

Singly Linked List(SLL) 구현구조체typedef int ElementType; // 필요할 때 원하는 타입으로 바꿔 쓰자typedef struct tagNode { ElementType Data; // 데이터 struct tagNode* NextNode; // 다음 노드} Node;연결 리스트의 주요 연산노드 생성 / 소멸힙(자유 저장소)에 새로운 노드를 생성Node* SLL_CreateNode(ElementType newData) { Node* NewNode = (Node*)malloc(sizeof(Node)); // 새로운 노드 동적할당으로 생성 NewNdoe->Data = newData; // 데이터 저장 NewNode->NextNode = NULL; /..

스택(Stack)의 응용 - 미로 탐색 미로 탐색 문제 미로에 갇힌 주인공이 출구를 찾는 문제 미로가 서로 연결된 여러 개의 방 또는 칸으로 구성되어 있다고 가정 출구를 찾는 과정 기본적인 방법은 시행착오 방법으로서 하나의 경로를 선택하여 한 번 시도해보고 안되면 다시 다른 경로를 시도 이 때, 현재의 경로가 안 될 경우에 다른 경로를 선택해야 하므로 다른 경로들이 어딘가에 저장되어 있어야 함 현재 위치에서 가능한 경로 중에서 가장 가까운 경로를 저장해야 유리함 가장 최근에 저장한 경로가 쉽게 추출되도록 스택을 사용 현재 위치에서 갈 수 있는 방들의 좌표를 스택에 저장한 후 막다른 길을 만나면 아직 가보지 않은 방 중에서 가장 가까운 방으로 다시 돌아가서 새로운 경로를 찾는다 한 번 지니간 방을 다시 가..

스택(Stack)의 응용 - 후위 표기 수식의 계산 수식 수식은 연산자와 피연산자, 괄호로 이루어져 있음. 연산자들은 우선순위가 있어 우선순위가 높은 연산자가 먼저 계산된다. 컴퓨터는 스택을 이용하여 수식을 계산한다. 중위 / 후위 / 전위 표기 수식 중위 표기 수식 사람들이 일반적으로 수식을 표기하는 방식 연산자가 피연산자 사이에 있으면 중위 표기 수식 후위 표기 수식 연산자가 피연산자 뒤에 있으면 후위 표기 수식 전위 표기 수식 연산자가 피연산자 앞에 있으면 전위 표기 수식 예시 2 + 3 * 4 (중위) 234*+ // 후위 표기 수식 +2*34 // 전위 표기 수식 a * b + 5 (중위) ab*5+ // 후위 표기 수식 +*ab5 // 전위 표기 수식 (1 + 2) * 7 (중위) 12+7* ..

스택(Stack)의 응용 - 괄호 검사 문제 괄호 검사 문제 프로그램에서 괄호들의 쌍이 올바르게 사용되었는지를 판단하는데 스택을 이용 괄호의 검사 조건 3가지 왼쪼 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 교차하면 안 된다. example { A [(i + 1)] = 0; } // 오류 X if ((i == 0) && (j == 0) // 오류 : 조건 1 위반 A [ (i + 1] ) = 0; // 오류 : 조건 3 위반 의사 코드 check_matching(expr): while (입력 expr이 끝이 나면): ch top = -1; } // 공백 상태 검출 함수 int is..

스택 LIFO(Last-In First-Out) in Korean, 후입 선출 가장 최근에 들어온 object가 가장 위에 있어 먼저 나가게 된다. 스택의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 스택 상단(stack top) : 스택에서 입출력이 이루어지는 부분 스택 하단(stack bottom) : 스택 상단의 반대쪽인 바닥부분 요소(element) : 스택에 저장되는 것 공백 스택(empty stack) : 스택에 요소가 하나도 없을 때 그러한 스택 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 매우 긴요하게 사용된다. ex. Undo(되돌리기) 기능 ex. 함수 호출 함수가 실행히 끝나면 자신을 호출한 함수로 되돌아간다. 시스템 스택에는 함수가 호출될..

배열의 응용 : 희소행렬 행렬을 표현하는 첫 번째 방법 : 2차원 배열을 사용 #define MAX_ROWS 100 #define MAX_COLS 100 int matrix[MAX_ROWS][MAX_COLS]; 단점 : 많은 항들이 0으로 되어 있는 희소행렬의 경우메모리의 낭비가 심하게 됨 첫 번째 방법을 통해 전치행렬 구하기 #include #define ROWS 3 #define COLS 3 // 행렬 전치 함수 void matrix_transpose(int A[ROWS][COLS], int B[ROWS][COLS]) { for (int r = 0; r

배열의 응용 : 다항식 $ p(x)=a_nx^n + a_{n-1}x^{n-1}+ ... + a_1x + a_0 $를 배열을 이용하여 표현해보자 첫 번째 방법 : 모든 차수의 계수값을 배열에 저장 (ex. 10x^5 + 6x + 3) #define MAX_DEGREE 101 // 다항식의 최대 차수 + 1 typedef struct { int degree; float coef[MAX_DEGREE]; } polynomial; polynomial a = {5, {10, 0, 0, 0, 6, 3}} 문제점 : 대부분의 항의 계수가 0인 희소 다항식의 경우에 공간의 낭비가 심함 장점 : 다항식의 덧셈이나 뺄셈 시에 같은 차수의 계수를 쉽게 찾을 수 있어 알고리즘이 간단해짐 ex) 두 다항식을 더하는 프로그램 차수..

리스트에 대한 설명은 다음을 참조 [자료구조] 배열을 이용한 리스트 구현 순차리스트 구현 ArrayList.h #ifndef __ARRAY_LIST_H__ #define __ARRAY_LIST_H__ #define TRUE 1 #define FALSE 0 #define LIST_LEN 100 typedef int LData; typedef struct _ArrayList { LData arr[LIST_LEN]; int numOfData; int curPosition; } ArrayList; typedef ArrayList List; void ListInit(List *plist); void LInsert(List *plist, LData data); int LFirst(List *plist, LData ..

배열을 이용한 리스트 구현 - 순차 리스트, 연결 리스트 순차 리스트 : 배열을 기반으로 구현된 리스트 연결 리스트 : 메리의 동적 할당을 기반으로 구현된 리스트 --> 두 리스트는 ADT(기능)는 동일, 구현방법만 다름. 리스트의 특징 저장형태 : 데이터를 나란히 저장한다. (어느 방향으로 저장하든 상관 없다.) 저장 특성 : 중복이 되는 데이터의 저장을 허용. --> 배열과 연결을 기반으로 함. 배열 기반 리스트의 단점 배열의 길이가 초기에 결정되어야 함. 변경이 불가능 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어남. 배열 기반 리스트의 장점 데이터의 참조가 쉽다. 인덱스 값 기준으로 어디든 한 번에 참조 가능. 리스트 자료구조의 ADT(기능) 리스트의 초기화 void ListInit(L..