'CS' 카테고리의 글 목록

2024. 8. 16. 11:31 CS/Algorithm

"그래프 탐색"이란 그래프에서 하나의 노드를 시작으로 다수의 노드를 방문하는 알고리즘을 말한다. 이때, 방문하는 노드는 딱 한 번씩만 방문하는 것이 특징이다.만약, 자료구조 그래프에 대한 내용이 궁금하다면 아래 포스팅을 참고 바란다.https://seokyoungg.tistory.com/94 [Data Structure] Graph"그래프"(Graph)는 각 데이터와 그들을 잇는 선들로 이루어진 ADT이다. 각 데이터들을 "정점"(vertex) 혹은 "노드"(node)라 부르며, 이들을 잇는 선을 "간선"(edge)라 부른다. 즉, 그래프는 유한한 개수의seokyoungg.tistory.com 이러한 그래프 탐색 알고리즘에는 2가지가 있다. BFSDFS BFS"BFS"는 Breadth-first Sea..

[Algorithm] 정렬 알고리즘(2) - 머지 소트, 퀵 소트, 기수 정렬

2024. 8. 12. 16:12 CS/Algorithm

이전 포스팅에서 살펴본 정렬 알고리즘들은 평균, 최악의 경우 $O(n^2)$의 시간복잡도를 가지게 되었다. 병합 정렬 (Merage Sort)"병합 정렬"(또는 합병 정렬)은 문제를 분할하고, 문제를 정복하여 합치는 분할정복을 기반으로 한 정렬 알고리즘이다. 정렬 과정이러한 분할정복은 "하향식"과 "상향식"구현으로 구분할 수 있는데,병합 정렬에선 하향식 구현방식을 대부분 사용한다. 하향식(TopDown)방식으로 구현한 병합 정렬의 과정은 다음과 같다. (아래 그림은 정확한 Top-Down 방식은 아니지만, 분할되고 정복되는 순서만 차이 있을 뿐, 방법은 동일하다.)리스트를 절반으로 나누어 두 부분 리스트로 나눈다. 이를 부분 리스트의 길이가 1이하가 될 때까지 재귀적으로 위의 과정을 반복한다. (길..

[Algorithm] 정렬 알고리즘(1) - 버블정렬, 선택정렬, 삽입정렬

2024. 7. 10. 17:25 CS/Algorithm

"정렬 알고리즘"은 일련의 원소들에 대해 정해진 규칙에 맞게 재배열하는 알고리즘이다. 정렬 알고리즘은 현대까지도 계속 발명 될 정도로, 많은 알고리즘이 존재하지만 이중 대표적으로 몇가지만 살펴볼것이다. 정렬 알고리즘 분류 기준정렬 알고리즘은 여러 기준으로 분류된다. 안정 정렬 vs. 불안정 정렬 "안정 정렬"이란, 정렬조건이 동일한 원소가 여러개 있을 때, 입력 때와 동일한 순서로 정렬되는 정렬 알고리즘이다.반면, "불안정 정렬" 입력 때와 동일한 순서로 졍렬되는 것을 보장하지 않는다. "안정 정렬"은 정렬조건이 동일한 원소들의 순서를 보장해야할 때, 유용하게 사용될 수 있다. 예를 들어, 온라인 쇼핑몰에서 구매자의 구매 요청이 요청 순서대로 쌓인다고 가정해보자. 이때, 등급이 높은 회원부터 배송..

[Algorithm] 알고리즘이란?

2024. 7. 8. 13:00 CS/Algorithm

수학 혹은 컴퓨터 과학(Computer Science)에서 "알고리즘"이란 어떠한 문제를 풀기 위한 "유한한 갯수의 일련의 시퀀스"이다. 이때, 알고리즘은 컴퓨터 프로그램으로 대부분 구현되나, 전기 회로 혹은 기계 등등 다른 수단으로도 구현될 수 있다. 특성 앞서 알고리즘을 "유한한 갯수의 일련의 시퀀스"라고 정의했지만, 여기서 몇가지 조건이 더 붙는다. 입력 : 잘 정의된 입력들을 받아들일 수 있어야 한다.출력 : 정확성을 추론할 수 있는 출력이 있어야 한다.명확성 : 각 단계는 명확하게 정의되어야 한다. 각 단계에서 수행할 작업을 정확하게 지정할 수 있어야 한다. 유한성 : 유한한 수의 명령어의 시퀀스가 수행되면 반드시 종료되어야 한다.유효성 : 모든 명령어는 실행 가능해야 한다. 알고리즘 평가 "..

[PS] BOJ 2457 (공주님의 정원)

2024. 6. 23. 22:26 CS/Algorithm

문제부터 살펴보면 3월 1일부터 11월 30일까지 꽃이 지지 않게 하는 것이 핵심이다. 이때의 입력은 각각 꽃이 피는 날과 꽃이 지는 날이 들어온다. 1번째 접근우선, 가장 먼저 생각나는 것은 특정 날짜 이전에 피는 꽃 중 가장 늦게 피는 꽃을 매 시행시 구하면 된다. 하지만, 매 시행 시 $N$개의 꽃을 살펴보게 되기 때문에, 시작 복잡도는 $O(N^2)$이 된다. 해당 문제에서 $N$은 최대 100,000이기 때문에, $O(N^2)$은 시간 초과가 발생하게 된다. 2번째 접근 매 시행시 특정 날짜 이전에 피는 꽃 중 가장 늦게 피는 꽃을 상수 혹은 로그 시간에 구할 수만 있게 된다면, 시간초과가 발생하지 않고 문제를 해결할 수 있게 된다. 이와 같이 그리디 한 풀이로 접근하면, 매 시행마다 꽃이..

[PS] BOJ 1539(이진 검색 트리)

2024. 6. 18. 23:08 CS/Algorithm

https://www.acmicpc.net/problem/1539 문제 접근가장 먼저 생각할 수 있는 방법은 BST를 직접 구현해, 삽입될 때마다 위치를 확인하는 방법이다. 하지만, N = 250,000이고, BST가 편향 트리가 되는 경우 탐색 시간은 $O(logN)$이 아닌, $O(N)$이 되게 되어, 최종 시간 복잡도는 $O(N^2)$으로 시간초과가 발생하게 된다. 그렇다면, Self-Balancing 트리를 사용하면서 BST상에서 노드의 높이를 알 수 있어야만 한다. 이때, 노드가 삽입될 때, 부모 노드의 높이를 알 수만 있다면, 각 노드의 높이를 계산할 수 있을 것이다. 따라서, Self-Balancing 트리에서 새로운 노드가 삽입되는 부모 노드를 알아야 한다. 트리에서 새로운 노드는 "자..

[Data Structure] Tree(5) - Red-Black Tree Implementation

2024. 6. 17. 01:42 CS/Data Structure

이번 포스팅에선 "Red-Black Tree"를 Swift로 구현할 것이다.만약 개념에 대한 내용이 궁금하다면 해당 포스팅을 참고 바란다. 자세한 구현은 아래 링크에서 확인해 볼 수 있다. https://github.com/jungseokyoung-cloud/Data-Structure/tree/main/Data-Structure/Tree.playground/Sources/Red-BlackTree Data-Structure/Data-Structure/Tree.playground/Sources/Red-BlackTree at main · jungseokyoung-cloud/Data-StructureData Structures implemented with Swift. Contribute to jungseok..

[Data Structure] Tree(4) - Red-Black Tree

2024. 6. 2. 15:28 CS/Data Structure

"Red Black Tree"(RB Tree)란 이진 검색 트리의 일종으로 자가 균형 이진 검색 트리(Self-Balancing BST)이다. BST의 경우 평균적으로 $O(logN)$에 동작하지만, 최악의 경우 $O(N)$이 소요된다. 최악의 경우는 균형이 무너져 편향트리가 되었을 때 발생한다. 따라서, 최악의 경우에도 $O(logN)$을 보장하는 자가 균형 이진 검색트리인 AVL, Red-Black Tree를 사용한다. 특징 "Red Black Tree"는 다음과 같은 규칙을 만족하는 BST이다.#1: 모든 노드는 빨간색 혹은 검은색이다. #2: 루트노드는 검은색이다.#3: 리프(NIL)노드는 검은색이다. #4: 빨간색 노드의 자식은 검은색이다. (즉, 2 연속으로 빨간색이 나올 수 없다.)#5: ..

[Data Structure] Tree(3) - AVL Tree

2024. 5. 23. 14:29 CS/Data Structure

"AVL 트리"는 자가 균형(Self-Balancing) 이진 검색 트리로, 좌우 서브 트리의 높이 차이가 1을 유지한다. 만약, 높이 차이가 1 이상이 나게 된다면 스스로 균형을 맞추어 높이 차이 1을 유지한다. 이전 포스팅에서 보았던 이진 검색 트리의 경우에는 최악의 경우 모든 연산의 시간복잡도가 $O(N)$이 되었다. 이는 다음과 같이 편향트리가 될 수 있기 때문이다. 따라서, AVL트리는 자가 균형을 통해 높이차를 1을 유지함으로써, 모든 연산의 평균 최악 모두 $O(logN)$을 보장한다. Balance Factor 이진 트리에서 Balance Factor는 다음과 같이 정의된다. 즉, 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값이다. AVL 트리는 BF값이 [-1, 1]범위 ..

[Data Structure] Tree(2) - Binary Search Tree

2024. 5. 17. 23:13 CS/Data Structure

"이진 검색 트리"(Binray Search Tree)는 다음과 같은 성질을 만족하는 이진트리이다. 각 노드에 들어가는 값들은 대소관계를 비교할 수 있다. 노드의 왼쪽 서브트리는 작은 값들을 가진 노드들로 이루어져 있다. 노드의 오른쪽 서브트리는 큰 값들을 가진 노드들로 이루어져 있다. 좌우 서브트리는 각각 위의 2 조건을 만족한다.이러한 특성 때문에 정렬된 이진 트리(Sorted Binary Tree)라고도 부른다. 이진 검색 트리는 검색, 삽입, 삭제 연산들이 평균적으로 $O(logN)$에 동작한다. 해시의 경우, 위의 연산들을 $O(1)$에 제공하지만, 원소 간의 대소관계는 비교할 수 없다. 하지만, 이진 검색 트리의 경우 "5 보다 큰 최초의 원소"와 같은 대소비교 관련 연산을 수행할 수 있다...

[Data Structure] Tree(1)

2024. 5. 12. 15:32 CS/Data Structure

"트리"(Tree) ADT는 계층 구조를 가지는 그래프의 일종으로 비선형 자료구조이다. 그래프의 일종이기 때문에, 노드와 간선으로 이루어져 있다.이때, 각 노드는 하나의 부모 노드만을 가지며, 여러 개의 자식 노드를 가질 수 있다.이러한 계층 구조에 의해 트리에서는 절대로 순환이 발생하지 않는다. 즉, 트리는 각 노드를 한 번씩만 방문했을 때, 절대 순환이 발생하지 않는 연결 그래프이다. 이렇게 최상위의 노드를 루트노드라 부르며, 모든 트리에는 항상 하나만 존재한다. 또한, 트리 구조는 각 노드를 루트 노드로 하여 하위트리로 분류할 수 있으며, 이러한 특성에 의해 재귀적 자료구조라고도 부른다. 루트 노드(root) : 모든 트리에 하나만 존재하며, 부모가 없는 최상위 노드 리프(단말) 노드(leaf)..

[Data Structure] Graph

2024. 5. 6. 13:39 CS/Data Structure

"그래프"(Graph)는 각 데이터와 그들을 잇는 선들로 이루어진 ADT이다. 각 데이터들을 "정점"(vertex) 혹은 "노드"(node)라 부르며, 이들을 잇는 선을 "간선"(edge)라 부른다. 즉, 그래프는 유한한 개수의 정점과 간선으로 이루어진 ADT이다. 이러한 그래프 G를 G = (V, E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미한다. 정점(노드) : 각 데이터 간선 : 정점들을 잇는 선 인접 정점: 간선에 의해 연결된 정점 (ex. A의 인접 정점은 B,C)차수(degree) : 정점에 연결된 간선의 개수 (ex. A의 차수는 2)이러한 그래프를 순회하는데 사용하는 알고리즘에는 대표적으로 BFS와 DFS가 있다.순회란, 그래프내의 모든 정점을 한번씩 방문하는 것을 말..

티스토리툴바