늦깎이 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/04/16 - [늦깎이 IT] - [정렬] 힙 정렬 (수정) :: 늦깎이 IT 에서 다시 수정하여 포스팅하였습니다. 지난 번 힙 기반의 우선순위 큐를 구현한데 이어, 오늘은 힙 정렬을 구현하겠습니다. 힙에 대한 설명은 아래 포스팅을 참고하시기 바랍니다.2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙 [관련 알고리즘 문제]2019/02/17 - [알고리즘 문제/알고스팟] - [알고스팟 RUNNINGMEDIAN] 변화하는 중간값 우선 힙은 1차원 배열로 표현할 수 있습니다. 우리가 보기에는 '완전 이진 트리'인 힙의 구조가 어떻게 배열로표현할 수 있는지 생각해봅시다. 다음과 같이 무작위 데이터가 저장된 배열과 완전 이진트리가 있다고 가정해봅시다.위의 배열과 트리의 연관..

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

오늘은 BFS와 DFS의 기초 개념부터 차근차근 설명하려고 합니다.(해당 포스트는 BFS와 DFS의 개념을 모르는 초보분들을 초점으로한 포스팅입니다.) 2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -2 지난 포스팅에서 각 정점들의 연결정보를 1) 인접행렬과 2) 연결 리스트에 저장하는 방법을 살펴보았습니다. 이번 포스팅에서는 이를 토대로 직접 DFS와 BFS를 구현해보겠습니다. 1. 깊이우선탐색 (DFS) 깊이우선탐색은 스택 혹은 재귀호출을 통해 그래프를 순회하는 방법입니다.깊이우선탐색은 우선 나(현재 노드)를 먼저 방문하고 나와 연결된 다른 놈들 중 하나를 방문하는 것입니다.(단, 방문했던 노드는 방문하지 않는다.) 다음과 같은 정점과 간선이 있을 때, DFS 했을 경우의 ..

오늘은 BFS와 DFS의 기초 개념부터 차근차근 설명하려고 합니다.(해당 포스트는 BFS와 DFS의 개념을 모르는 초보분들을 초점으로한 포스팅입니다.) 2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1 오늘은 지난시간에 이어 DFS와 BFS를 코드레벨에서 살펴보겠습니다.우선, 정점의 연결관계를 나타내는 가장 대표적인 방법은 인접 행렬과 인접 리스트로 나뉩니다. 1. 인접 행렬 위와 같은 노드와 간선을 연결하는 그래프가 있다고 가정하겠습니다.이 그래프의 연결 정보를 인접 행렬로 표현한다면 어떻게 해야할까요???? 결론부터 말씀드리면 아래 그림과 같은 2차원 배열에 연결 정보를 저장할 수 있습니다. 이 2차원 배열이 뜻하는 바를 살펴보면 행과 열의 데이터가 1이면 해당 노드들이 ..

오늘은 BFS와 DFS의 기초 개념부터 차근차근 설명하려고 합니다.(해당 포스트는 BFS와 DFS의 개념을 모르는 초보분들을 초점으로한 포스팅입니다.) 우선, 그래프는 정점과 간선으로 이루어진 자료구조라고 할 수 있습니다.아래 그림을 살펴보겠습니다. 이 그림에서 동그라미로 표시된 1부터 6까지는 정점(Vertex) 라고 불리며, 각 노드를 연결하는 직선을 간선(Edge)이라고 합니다. (포스팅에서는 정점을 노드라고 칭하겠습니다.....제가 좀 익숙해서) 너비우선탐색(BFS)와 깊이우선탐색(DFS)는 어느 한 노드로부터 시작해서 원하는 노드로까지 탐색하는 방법을가르키는 알고리즘이라고 할 수 있습니다. 1. 너비우선탐색(BFS)너비우선탐색은 말그대로 현재 노드와 인접한 노드들부터 탐색하는 방법입니다.예를 들..