1. 후위 표기식이란?연산자를 피연산자 뒤에 배치하는 표기 방식이다.일반적인 중위 표기식(Infix)에서는 피연산자 사이에 연산자가 위치하지만, 후위 표기식은 피연산자 뒤에 연산자가 위치한다. 중위 표기식1 + 2A + B * C 후위 표기식12+A B C * + 후위 표기식의 특징으로는 괄호가 필요하지 않다는 것이다. 중위 표기식(A + B) * C후위 표기식A B + C * 2. 후위 표기식 계산 방법후위 표기식은 스택(Stack) 자료구조를 사용하여 계산할 수 있다.피연산자는 스택에 저장한다. 스택은 LIFO(Last In, First Out) 구조이다.연산자를 만나면 스택에서 피연산자 두 개를 꺼내고, 연산자와 계산한다. 계산된 값은 다시 스택에 저장한다.연산을 모두 마쳤을 때 스택에 저장된 값..
[알고리즘-자바] Floyd-WarShall 알고리즘
플로이드 와샬 모든 정점에서 모든 정점으로의 최단 거리를 구하기 위해서 플로이드 와샬 알고리즘을 사용할 수 있습니다. 즉, 정점 [A, B, C, D]가 존재할 때 A->C로 이동하기 위해서 중간에 B를 거치거나 D를 거쳐 갈 수 있습니다. B와 D를 거치는 게 A->C로 가는 것보다 더 짧은 거리로 이동할 수도 있고 아닐 수도 있습니다. 또한 기존에는 지나갈 수 없는 경로를 다른 정점을 거쳐 지나갈 수 있는 경로가 되기도 합니다. 다음 방향 그래프가 존재합니다. 무한대의 의미는 해당 방향으로 이동하는 경로가 존재하지 않음을 의미합니다 => ex. 정점A -> 정점C 정점A 정점B 정점C 정점D 정점A 0 4 무한대 6 정점B 3 0 7 무한대 정점C 5 무한대 0 4 정점D 무한대 무한대 2 0 위의..