본문 바로가기

Algorithm14

정렬 Sort 링크에 있는 내용을 한 눈에 보기 위해 옮겨온 글이며 원문을 참고해주세요 거품 정렬 (Bubble Sort) 인접한 두 원소의 값을 비교해 그 크기에 따라 위치를 서로 교환하는 정렬 방식 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘입니다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 합니다. Process (Ascending) 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환합니다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하.. 2021. 5. 23.
[C & Java] Heap 힙 힙 (Heap) 완전 이진 트리 기반의 더미와 모습이 비슷한 자료구조 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조 부모노드의 키 값이 자식 도느의 키 값보다 항상 큰 이진트리를 말한다. 부모노드와 자식 노드간에(루트 와 서브트리 간에) 위와 같은 조건이 항상 성립한다. 중복된 값을 허용한다. (이진 탐색트리는 안됨) 다른 용어로 이야기하면 히프안에서 데이터들은 느슨한 정렬 상태를 유지한다. 즉 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도이다. 히프의 목적은 삭제 연산이 수행될 때마다 가장 큰 값을 찾아내기만 하면 되는 것이므로(가장 큰 값은 루트 노드에 있음) 전체를 정렬할 필요는 없다. 히프는 완전 이진 트리이다. 힙의 종류 최대힙(Max .. 2021. 5. 19.
[Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 다익스트라 (Dijkstra) 알고리즘 하나의 시작 정점으로부터 모든 다른 정점까지의 음의 가중치가 없을 때 최단 경로를 찾는 알고리즘 다익스트라 알고리즘에서 음수 간선이 존재하면 안 되는 이유 다익스트라 알고리즘의 각 단계 먼저 집합 S를 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합이라고 하자. 다익스트라 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열이 반드시 있어야 한다. 이 1차원 배열을 distance라고 한다. 시작 정점을 v라 한다면 distance[v] = 0이고, 다른 정점에 대한 distance값은 시작 정점과 해당 정점 간의 가중치 값이 된다. 가중치 인접 행렬을 weight라 하면 distance[w] = wei.. 2021. 3. 12.
이진탐색 = 이분탐색 (Binary Search) - Java로 구현 이진 탐색 = 이분 탐색 (Binary Search) 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법이다. 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다. 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있다. 이러한 방법을 반복적으로 사용해 탐색하는 방법이 이진 탐색이다. 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합하다. ex 1) 10억 명이 정렬된 배열에서 이진 탐색을 이용해 특정 이름을 찾는다면 단 30번의 비교만으로 검색이 완료된다. 반면에 순차 탐색의 경우 평균 5억 번의 비교가.. 2021. 2. 6.
[Java] 트리 Tree 3 - 이진 탐색 트리 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리란 이진 탐색 트리의 성질을 만족하는 이진트리 이진트리 기반의 탐색을 위한 자료 구조 이진 탐색 트리의 성질 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. 오른쪽 서브 트리 키들은 루트 키보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 찾고자 하는 키 값이 이진트리의 루트 노드의 킷값과 비교해 루트 노드보다 작으면 원하는 키값은 왼쪽 서브 트리에 있고, 루트 노드보다 크면 원하는 키 값은 오른쪽 서브 트리에 있다. ex. 왼쪽 서브 트리의 값들 (3, 7, 12)는 루트 노드인 18보다 작다. 오른쪽 서브 트리의 값들 (26, 31, 27)은 루트 노드인 18보다 크다. 위의 이진 탐색 트.. 2020. 12. 31.
[Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현 4. 이진트리의 순회 이진트리에 속하는 모드 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미 이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후의의 3가지 방법이 있다. 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분된다. 루트를 방문하는 작업을 V 왼쪽 서브 트리 방문을 L 오른쪽 서브트리 방문을 R 루트를 서브 트리에 앞서서 먼저 방문하면 전위 순회 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회 루트를 서브 트리 방문 후에 방문하면 후위 순회가 된다. 이진트리에서 각각의 서브 트리 역시 이진트리이다. 전체 트리 순회의 알고리즘을 서브 트리에도 똑같이 적용해 순회한다. -> 문제의 구조는 같고 크기만 작아지는 경.. 2020. 11. 6.
[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현 1. 트리 1차원 배열로 구현 주로 포화 이진 트리나 완전 이진트리의 경우 많이 쓰이는 방법이다. 그외의 이진트리도 저장이 불가능한 것은 아니지만 기억공간의 낭비가 심해진다. 따라서 포화 이진 트리이진트리 또는 완전 이진트리를 1차원 배열로 구현해보자. 루트 노드는 1부터 시작한다.(인덱스 0은 사용하지 않는 편이 계산을 간단하게 함) 원하는 노드 n개까지 총 n+1 크기의 1차원 배열을 만든다. 그다음 이진트리의 번호대로 노드들을 저장한다. 배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다. 노드 i의 부모 노드 인덱스 = i / 2 노드 i의 왼쪽 자식 인덱스 = 2i 노드i의 오른쪽 자식 인덱스 = 2i + 1 /** * @author Gwon Minha * * 루트가 1인 완.. 2020. 11. 5.
[C & Java] 트리 Tree 1 - 트리? / 이진트리? / 트리 표현법 1. 트리(Tree)의 개념 계층적인 자료를 표현하는데 적합한 자료구조 한 개 이상의 노드로 이루어진 유합 집합 A~J를 노드(node) 이들 중 하나의 하나의 노드를 루트(root) 노드라 하고 나머지 노드들을 서브 트리(sub tree)라 한다. 계층적 구조에서 가장 높은 곳에 있는 노드 A가 루트가 됨 루트와 서브트리는 간선(edge)으로 연결됨 ex) {A, B, C, D, E, F, G, H, I, J} 중에서 루트 노드는 A이고 나머지 {B, E, F, G}, {C, H}, {D, I, J}의 3개의 노드 집합들은 A의 서브 트리라 한다. 다시 서브 트리 {B, E, F, G}의 루트는 B가 되고, 나머지 {E}, {F}, {G} 노드들은 다시 3개의 서브 트리로 나뉜다. 나머지도 마찬가지이다.. 2020. 11. 3.
[Java] DFS로 모든 이동 경로 구하기 DFS를 이용해 출발지(시작 정점)에서 목적지(도착 정점)까지의 모든 경로를 구해보자. DFS에 대해 자세히 알고 싶다면 아래 포스트 참고 [Java] DFS 깊이 우선 탐색 - 인접 리스트 / 인접 행렬로 구현 더보기) 인접 행렬을 이용해 그래프를 구성한 기존의 DFS 구현 코드 더보기 import java.util.*; public class DFS { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 정점의 개수 int m = sc.nextInt(); // 간선의 개수 int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 boolean visited.. 2020. 9. 23.
[Java] 조합 Combination 조합 조합이란 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 말한다. (위키백과 - 수학에서 조합은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다. 그 경우의 수는 이항 계수이다.) 예를 들어 [1, 2, 3] 배열에서의 조합은 아래와 같이 나온다. [1, 2] [1, 3] [2, 3] 참고 순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다. 말 그대로, 순서가 존재하는 열이라는 것이다. 즉 순열에서 { 1, 2, 3 }과 { 1, 3, 2 } , { 2, 1, 3 } 등 모두 다른 결과를 가져온다. 순서가 다르기 때문이다. 조합은 순서가 상관이 없는 모임을 의미한다. 순서가 상관없기 때문에 { 1, 2, 3 }, { 1, 3, 2 }.. 2020. 5. 12.
반응형

티스토리툴바