C/알고리즘23 스택 응용(수식 계산) 1. 수식표기법 (1) 중위표기법(infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 => 우리가 사용하는 방식 ex) A+B (2) 후위표기법(postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 => 컴퓨터 처리 방식 : 응용하여 중위표기법->후위표기법->수식 계산 : 스택 이용 ex) AB+ 1.1 괄호 검사 : 이때 수식을 계산하기 위해서는 올바른 수식인지 확인하기 위해 괄호 검사가 필요하다 : 수식에 포함된 괄호는 가장 마지막에 열린 괄호가 가장 먼저 닫아주어야 하는 구조를 스택을 통해 구현가능 : 수식검사가 완료된 경우, 공백 스택 상태여야함 왼쪽 괄호를 만나면 스택에 push 오른쪽 괄호를 만나면 스택에서 pop하여 같은 종류의 쌍의 괄호인지 확인 #.. 2023. 9. 15. 강한 결합 요소(Strongly Connected Components) 강한 결합 요소 : 그래프 안에서 강하게 결합된 정점 집합 cf> scc 활용 : scc마다 묶으면 cyclic 존재하지 않는 방향 그래프이기에 위상정렬 수행 가능하다 1. 알고리즘 코사라주 알고리즘(Kosaraju's Algorithm) 타잔 알고리즘(Tarjan's Algorithm) (1) 타잔 알고리즘 : 모든 정점에 대해 DFS(Depth-First Search, 깊이 우선탐색)을 수행하여 scc 찾는 알고리즘 : 부모로 돌아올 수 있어야 scc 성립 : 각 정점마다의 부모 노드가 무엇인지 기록(초기값은 자기자신) => union-find algorithm 개념과 비슷 (2) 작동 방식 1) 정점번호가 낮은 순으로 DFS 탐색 (이때, 연결리스트 통해 오름차순으로 정렬하였음) 2) 현재 정점의 .. 2023. 8. 15. 위상정렬(Topology sort) 위상정렬 : 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘(=순서결정 알고리즘) : DAG(Directed Acyclic Graph)인 경우에만 적용 가능 : 여러 개 답이 존재할 수 있음 => 현재 그래프는 위상 정렬이 가능한지 알려줌(정렬을 다 수행하지 않았는데 공백 큐가 발생하면 위상 정렬 실패, 순환그래프) => 위상정렬이 가능하다면 그 결과가 무엇인지 알려줌(정렬 수행한 위상정렬 결과) 1. 동작방식 1) 진입차수가 0인 정점을 큐에 삽입 2) 큐에서 원소를 꺼내 연결된 모든 간선 제거(연결리스트 이용) 3) 간선 제거 이후 0이 된 정점들을 큐에 다시 삽입 4) 큐가 빌 때까지 2~3) 과정을 반복 -> 이때, 모든 원소를 방문하기 전 큐가 빈 경.. 2023. 8. 14. Floyd Washall Algorithm(플로이드 와샬 알고리즘) 1.플로이드 와샬 알고리즘 : 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘 :2차원 배열 이용하여 계속적으로 비용 업데이트 cf> 다익스트라(Dijkstra Alogrithm) :한 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로 :1차원 배열 이용 #include #define INF 100000 void Floyd_Washall(int(*g)[4], int size) { int cost[4][4] = { 0 }; int i, j,k; for (i = 0; i < size; i++) { for (j = 0; j < size; j++) { cost[i][j] = g[i][j]; } } for (i = 0; i < size; i++) { for (j = 0; j < size; j++) .. 2023. 8. 14. Dijkstra Algorithm[C] 다익스트라 알고리즘 : Dynamic Programming을 활용한 최단 경로 탐색 알고리즘 "현재까지 알고있던 최단경로를 계속해서 갱신해나가는 알고리즘" : 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌 =>이때 최단거리는 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기에 DP활용 알고리즘이다 ver1)선형탐색 1. 동작 방식 1) 출발 노드 설정(start 변수) 2) 초기에 출발 노드를 기준으로 각 노드의 최소 비용 저장 3) 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 => 선형탐색과 힙 이용한 두 가지 구현방식 존재 4) 해당 노드를 거쳐 특정 노드로 가는 경우를 고려하여 최소 비용 갱신 5) 3~4) 과정 반복 => 이때 반복문을 이용하여 방문하지 않는 모든 .. 2023. 8. 11. kruskal algorithm[c] #define _CRT_SECURE_NO_WARNINGS #include #include #include #define EDGE_MAX_SIZE 100 typedef struct _EDGE_ { int node1; int node2; int distance; }EDGE; int Edge(EDGE* graph, int x, int y, int d) { static int i = 0; graph[i].node1 = x; graph[i].node2 = y; graph[i].distance = d; i++; } void Sort(EDGE* graph, int size) { int i,j; for (i = 1; i .. 2023. 7. 31. 이전 1 2 3 4 다음
