DFS - 깊이 우선 탐색 - 인접 행렬(순환/stack), 인접 리스트로 구현 - 어떤 노드를 방문했는지 검사를 무조건 해줘야 한다 (검사를 안해주면 무한 루프에 빠진다) 검사를 위한 배열 int visited[MAX_VERTEX] → dfs 시작할 때, 전부 FALSE로 초기화 - 인접 행렬 : O(n²) (정점 n개) - 인접 리스트 : O(n+e) (정점 n개, 간선 e개) 인접 행렬로 구현한 DFS 1. 순환 : dfs_mat_recur(graph* g, int v) 정점 v에서부터 dfs 시작 v는 방문완료니까 visited배열에 TRUE 표시 v의 인접 정점 w에서 탐색 시작 -- (1) matrix[v][w] == 1 (인접)이고, visited[w] == FALSE (방문 X)이면, 정점..

연결리스트 스택 - 장점 : 크기 제한 X - 단점 : 구현이 복잡, 삽입/삭제 시간이 오래 걸린다 - 크기에 제한이 없기 때문에 스택이 포화인지 확인할 필요가 없다 [코드 - C] #include #include // 연결리스트를 이용한 스택 typedef int element; typedef struct { element data; struct stacknode* link; // 각 노드들을 연결 }stacknode; stacknode* top; // 스택의 top을 가리키는 top 포인터 void init() { top = NULL; } int is_empty() { return top == NULL; } void push(element item) { stacknode* new_node = (sta..

알고리즘 현재 위치에서 갈 수 있는 모든 위치(상하좌우) 모두 stack에 push --(1) stack에서 pop 시켜서 pop 시킨 것을 현재 위치로 설정하고 (1) 계속 반복 -> 갈 곳 = stack에서 pop, 안 간 곳 = 그대로 stack에 존재 -> 이미 간 곳을 또 가면 이미 stack에 1번 저장되었기 때문에 다시 stack에 push X typedef struct { int r; // 로우(row) int c; // 컬럼(column) }cur_locate; // 현재 위치를 좌표 (r, c)로 표현 typedef struct { int top; cur_locate maze[MAX_STACK_SIZE]; }stack; char maze[MAZE_SIZE][MAZE_SIZE] = { /..

※ 연산자 우선순위 : ( ) stack에 존재하는 연산자 pop한 후, 다음 처리 연산자 push 왼쪽 괄호 -> 오른쪽 괄호 만날때 까지, 왼쪽 괄호위에 push된 연산자 pop int priority(char op) { // 연산자 우선순위 switch (op) { case '(': case')': return 1; case '+': case'-': return 2; case '*': case'/': return 3; } return -1; } void infix_to_postfix(const char* str) { stack s; init_stack(..

알고리즘 - 후위 표기 수식 str이 존재 str에서 피연산자(숫자)를 만나면 stack에 push str에서 연산자를 만나면 stack에서 pop2번 (숫자1, 숫자2) pop한 숫자 2개를 연산자로 계산 계산결과를 stack에 다시 push int postfixCalc(const char*str) { // 후위 표기 수식을 계산한 값 리턴 stack s; init_stack(&s); char ch; // 후위 표기 수식 str에서 하나하나 추출하는 자료형 int value = 0; // str에서 추출한 숫자가 문자형일때 '1', '2' 숫자로 변환 1, 2 해서 저장하는 자료형 int pop1, pop2; // pop1 = 스택에서 pop한 첫번째 값, pop2 = 스택에서 pop한 두번째 값 in..

괄호 검사 - 대괄호 [], 중괄호 {}, 소괄호 ()가 서로 짝이 맞는지 검사 왼쪽 괄호 개수 = 오른쪽 괄호 개수 같은 종류의 괄호이면, 왼쪽 괄호가 더 먼저 나와야 한다 서로 다른 종류의 괄호면 쌍을 이루면 안된다 알고리즘 - 하나의 문자열 str이 존재 str안에 왼쪽 괄호 [, {, (는 push를 통해서 stack에 저장 오른쪽 괄호 ], }, )를 만나면 stack에 저장된 왼쪽 괄호를 pop시켜서 서로 짝이 맞는지 확인 오른쪽 괄호를 만났는데 stack이 비어있거나, pop한 문자가 다르면 검사 실패 모든 괄호 검사가 끝난 다음, stack을 봤는데 stack이 안비워져 있다면 검사 실패 int check_bracket(const char* str) { stack s; char ch, po..

스택이란? "LIFO 구조" : Last-In First-Out 프링글스 과자라고 생각하면 된다 프링글스는 제조 과정에서 과자들을 차례대로 통에 넣어준다 당연히 프링글스를 사먹는 사람들은 일반적으로 제조과정에서 마지막에 넣은 과자를 먼저 먹게된다 이처럼 스택은 몇몇 요소들을 넣으면 가장 나중에 넣은 요소들부터 차레대로 pop이 되는 구조이다 스택 ADT (추상 자료형) - n개의 element형의 요소들의 선형 리스트 boolean is_full(stack *s) 스택 포화 상태 검출 함수 boolean is_empty(stack *s) 스택 공백 상태 검출 함수 void push(stack *s, element item) 스택 s에 item을 삽입 element pop(stack *s) 스택 s의 가장..