Brute force Study

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

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

GUI(Graphic User Interface) - tkinter Tcl/Tk 툴킷을 사용하는데 필요한 인터페이스 모듈 (Std library) import tkinter as tk root = tk.Tk() # 실행했을 때 나타나는 창 root label = tk.Label(root, text='Hello World') # root 창에 포함되는 컴포넌트로 label 생성 label.pack() # label 객체를 창에 표시 root.mainloop() # root 창을 event loop에 들어가게 하여 root 창이 종료되지 않고 일을 계속 수행 블로그 프로그램을 만든다고 할 때 사용되는 tkinter component ListBox : 블로그의 목록 Label : '제목&..

정규 표현식 정규 표현식이란? 정규 표현식 : 복잡한 문자열을 처리할 때 사용하는 기법 파이썬 말고도 다른 곳에서도 사용함 정규 표현식이 필요한 이유? example : 주민번호 뒷자리 7자리를 *로 변환하기 data = """ park 800905-1049118 kim 700905-1059919 """ result = [] for line in data.split('\n'): word_result = [] for word in line.split(" "): if len(word) == 14 and word[:6].isdigit() and word[7:].isdigit(): word = word[:6] + "-" + "*******" word_result.append(word) result..