개발이글스

버블 정렬(Bubble Sort) 버블 정렬이란 인접한 두개의 데이터를 비교해서 정렬을 진행하는 정렬방식이다. 방식이 간단한만큼 비효율적이다. ex) 배열에 숫자들을 오름차순으로 정렬할 때 첫번째 수를 시작으로 끝의 숫자까지 바로 인접해 있는 숫자와 비교하며 이동한다. 선택정렬(Selection Sort) 선택정렬이란 제자리 정렬 알고리즘 중 하나이며, 오름차순으로 정렬한다면 가장 작은 최솟값을 맨앞에 놓고 그 이후의 값들을 하나씩 비교한 후 올바른 값을 선택하여 채워넣는 정렬방법이다. (버블정렬과 비슷한 성능) 삽입정렬(Insertion Sort) 삽입정렬은 정렬대상을 정렬된 부분과 안된 부분 두 부분으로 나눈 후 정렬안된부분의 데이터를 정렬된 부분의 특정 위치에 삽입하는 정렬방법이다. 병합정렬(Mer..

1. 우선순위 큐(Priority Queue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다. ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우 자료구조 추출되는 데이터 Stack 가장 나중에 삽입된 데이터 Queue 가장 먼저 삽입된 데이터 Priority Queue 가장 우선순위가 높은 데이터 # 우선순위 큐를 구현하는 방법은 다양하다. 1) 단순히 리스트를 이용해서 구현할 수 있다. 2) 힙(Heap)을 이용해서 구현할 수 있다. 데이터의 개수가 N개 일때, 구현 방식에 따라서 시간복잡도를 비교한 내용은 다음과 같다. 우선순위 큐 구현 방식 삽입 시간 삭제 시간 ..

1. 해시 테이블(Hash Table) 이란? : 해시 테이블은 (Key, Value) 식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다. 해시테이블은 key 값을 해시함수(Hash Function) 를 사용하여 변환한 값을 색인(index)으로 삼는다. 해시함수(Hash Function)를 사용해 key 값을 index로 변환하는 과정을 Hashing 이라고 한다. 2. 해시 함수(Hash Function) 해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)로 이어지게 된다. 따라서 해시함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시테이블에 ..

너비우선탐색(BFS) 이란? : 루트노드 (혹은 다른 임의의 노드) 에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 순회방법. 즉 깊게(deep)탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택. BFS(너비우선탐색)가 DFS(깊이우선탐색) 보다 좀 더 복잡하다. 너비우선탐색(BFS) 의 특징 직관적이지 않은 면이 있다. -BFS는 시작노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다. BFS는 재귀적으로 동작하지 않는다. 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반..

1. 그래프(Graph) 그래프는 연결되어있는 원소간의 관계를 표현한 자료구조 이다. 그래프는 연결할 객체를 나타내는 Vertext 와 Edge 로 구성. G = (V,E) 로 정의, V는 정점의 집합, E는 간선들의 집합을 의미. 2. 그래프 종류 1. Directed Graph (방향 그래프) : 간선에 화살표로 방향이 표시되어 있는 그래프 방향 그래프에서 정점 Vi 와 Vj 를 연결하는 간선을 로 표현하는데 Vi를 꼬리(tail), Vj를 머리(head)라고 한다. 이때, 와 는 서로 다른 간선이다. V(G1) = {A,B,C,D} E(G1) = {, ,,,} 2. Undirected Graph(무방향 그래프) :두 정점을 연결하는 간선에 방향이 없는 그래프 무방향 그래프에서 정점 Vi 와 Vj 를..

깊이 우선 탐색 (DFS) 이란? : root node 에서 시작해서 다음 Branch 로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사. 즉, 넓게(wide) 탐색하기 전에 깊게 (deep) 탐색하는 것이다. 모든 노드를 방문하고자 하는 경우에 DFS를 사용한다. DFS(Depth First Search)가 BFS(Breadth First Search) 보다 더 simple 하다. 단순 검색 속도 자체는 DFS 가 BFS 에 비해 느리다. #깊이 우선 탐색(DFS)의 특징 자기 자신을 호출하는 순환 알고리즘 형태를..