늦깎이 IT

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

오늘은 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)너비우선탐색은 말그대로 현재 노드와 인접한 노드들부터 탐색하는 방법입니다.예를 들..