C++/자료구조 (2) 썸네일형 리스트형 [C++/백준 1918번] stack을 사용하여 중위 표기식을 후위 표기식으로 변환 (Postfix Expression) 중위 표기식 (Infix Expression) 중위 표기식은 연산자가 피연산자 사이에 오는 연산식을 의미한다. 예를 들어 (A+B)*C처럼 우리가 흔히 사용하는 표현법이다. 후위 표기식 (Postfix Expression) 후위 표기식은 연산자가 피연산자 뒤에 오는 연산식을 의미한다. 예를 들어 중위 표기식 A+B를 후위 표기식으로 나타내면 AB+로 표기할 수 있다. 이때 연산자가 여러 개 있을 경우 먼저 오는 연산자를 먼저 계산해 준다. 예를 들어 ABC*+라는 후위 표기식이 있으면 B*C를 먼저 하고 +A를 해주면 된다.즉, 중위 표기법으로 나타내면 A+B*C와 동일하다. 중위 표기식을 후위 표기식으로 변환 중위 표기식을 후위 표기식으로 변환할 때에는 stack 자료구조를 사용하여 .. [C++] 단일 타입의 Singly Linked List 구현 Linked List linked list는 데이터를 저장하는 구조 중 하나로 여러 개의 노드가 포인터로 연결된 선형 데이터 구조이다. 해당 자료구조는 구조체(혹은 클래스) 안에 저장할 데이터와 노드를 갖고 있다. Linked List vs Array linked list는 array와 비교했을 때 장단점이 존재한다. 먼저 장점으로는 특정 데이터를 제거하거나 저장하려고 하면 array는 항상 O(n)의 시간복잡도를 갖지만 linked list는 O(n-k)의 시간복잡도를 갖기 때문에 해당 작업에서 빠른 속도를 보인다. (최악의 경우에는 동일하다) 이때 특히 맨 앞의 데이터를 삽입하거나 제거하려고 할 때 linked list는 O(1)의 시간복잡도를 갖는다. 단점으로는 특정한 위치의 데이터에.. 이전 1 다음