Brute force Study

스택(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..

추상 자료형(Abstract Data Type, ADT) 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것. (지갑에서 카드를 꺼낸다 --> 지갑을 열고 카드를 꺼내고 지갑을 닫고.... 구체적인 완성과정을 언급하지 않는다) 자료형은 기능이다. 기능의 명세를 가리켜 자료형이라고 함. (사용 설명서) 데이터, 그리고 데이터의 처리는 항상 묶여있다. 데이터만 존재할 순 없다. 구조체를 정의하면 구조체와 관련된 연산을 담당하는 함수를 정의한다 ex) 지갑 카드의 삽입, 추출, 동전의 삽입, 추출, 지폐의 삽입, 추출 (과정을 신경쓰지 않는다.) // 자료형 Wallet 정의 typedef struct _wallet { int coin100Num; // 100원짜리 동전의 수 in..