늦깎이 IT

후위표기법을 계산하는 방법은 아래 포스팅을 확인하기 바랍니다. 2019/03/21 - [알고리즘 이론] - [자료구조] 스택으로 후위표기식 계산하기 :: 늦깎이 IT [전체 구현 소스 코드 확인하기] 이번 포스팅은 스택 자료구조를 활용해서 중위 표기법을 후위 표기법으로 바꾸는 방법을 알아본다. 중위 표기법을 후위 표기법으로 바꾸는 데에는 아래와 같은 규칙이 있다. [소괄호가 없는 중위표기법] 1. 중위 표기법을 저장하는 배열 A와 후위 표기법을 저장하는 배열 B가 있다. 2. 아래 규칙에 따라, 피연산자와 연산자를 배열 A에서 배열 B로 이동시킨다. 1) 피연산자는 무조건 B 배열로 이동시킨다. 2) 연산자는 스택에 저장한다. 스택이 비어있다면, 연산자를 저장한다. 스택이 비어있지 않다면, 이미 저장된 ..

이번 포스팅에서는 이진 검색 트리에 대해서 알아봅니다.[전체 구현 소스코드 확인하기][전체 구현 이클립스 프로젝트 확인하기] 우선, 데이터를 저장, 검색, 삭제 등을 할 때 사용되는 자료구조는 대부분 배열과 연결 리스트를 사용합니다.저장, 검색, 삭제 등의 연산(?)을 할 때 배열과 연결 리스트에서 걸리는 시간 복잡도를 우선적으로 확인해봅시다. 1. 데이터가 정렬되지 않은 상태일 때, [배열을 사용할 경우]1) 검색 - 원하는 데이터를 찾기 위해서는 배열의 처음부터 끝까지 모두 확인해야 하므로 O(N)만큼의 시간이 걸립니다. 2) 저장 - 데이터들이 정렬되지 않은 상태이므로, 배열의 맨 마지막에 데이터를 저장하면 되기 떄문에 O(1)만큼의 시간이 걸립니다. 3) 삭제 - 삭제할 데이터를 검색하기 위한 시..

이번 포스팅에서는 이진 트리의 순회 방법에 대해 알아봅니다. [이진 트리] 1. 중위 순회 (Inorder-Traverse)A → B → C → D → E → F → G → H → I1) 왼쪽 자식 노드를 중위 순회한다.2) 루트 노드를 방문한다.3) 오른쪽 자식 노드를 중위 순회한다. [의사 코드]12345INORDER-TRAVERSE(x) if x is not NULL then INORDER-TRAVERSE(left[x]) print key[x] INORDER-TRAVERSE(right[x])cs2. 후위 순회 (Postorder-Traverse)A → C → E → D → B → H → I → G → F1) 왼쪽 자식 노드를 후위 순회한다.2) 오른쪽 자식 노드를 후위 순회한다.3) 루트노드를 방문..

오늘은 우선순위 큐에 대해서 말해보려고 합니다. [관련 알고리즘 문제]2019/02/17 - [알고리즘 문제/알고스팟] - [알고스팟 RUNNINGMEDIAN] 변화하는 중간값 우선 일반적인 큐의 특성에 대해 설명하자면 먼저 들어간 데이터가 먼저 나옵니다.반면 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다. 그럼 여기서 궁금한 점이, 우선순위 큐에 저장되는 모든 데이터들은 각자 우선순위를 나타내는 값을 지녀야하는것일까요? 꼭 그렇지는 않습니다. 우선순위를 지녀야한다기 보다는, 데이터를 근거로 우선순위를 판단할 수 있어야 합니다. [우선순위 큐 구현방법]1. 배열을 기반으로 구현하는 방법2. 연결 리스트를 기반으로 구현하는 방법3. 힙(heap)을 이용하는 방법 [배열로 구현..