본문 바로가기

728x90

🖥 Computer Science61

[Algorithm] 소수와 관련된 알고리즘(feat. 에라토스 테네스의 체) 안녕하세요 Foma 💻 입니다! 알고리즘 문제를 풀다 보면 소수를 찾아햐 하는 유형이 많은데요. 소수의 갯수를 찾아야 할 때, 소수인지 아닌지 분별해야 할 때 등 효율적인 알고리즘이 필요합니다. 오늘은 정확히 알고 빠르게 찾기 위해서 글을 정리해보려고 합니다. 바로 시작할게요~! 기존의 소수를 찾는 방법 기존의 소수를 찾는 방법은 k라는 수가 있다면 단순하게 2부터 n까지 k로 나눠서 나누어 떨어지는 숫자의 갯수를 판별하면 되겠죠? 하지만 이런 방법은 숫자가 커지면 커질수록 비효율적이기 때문에 시간이 오래 걸리게 됩니다. 그러므로 효율적인 방법을 사용해야 하는데요. 에라토스 테네스의 체 먼저 2부터 n까지의 구간에서 소수의 갯수나, 어떤 소수가 있는지 확인하기 위해선 "에라토스 테네스의 체"를 알고리즘을.. 2022. 1. 19.

[Algorithm] 동적 계획법(Dynamic Programming)이란? 안녕하세요 Foma 💻 입니다! 그 동안 알고리즘 문제를 풀면서 동적 계획법 관련된 문제가 나오면 어려움을 겪곤 했는데요.. 오늘은 동적 계획법에 대해서 제대로 정리를 해보려고 합니다. 바로 시작할게요! 동적 계획법(Dynamic Programming)이란? 다이나믹 프로그래밍은 1950년대 미국의 수학자인 리처드 벨맨이 최적화 문제(Optimization Problem)를 해결하기 위해서 고안되었다. 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말하며 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키 백과 - 즉, 분할 정복 알고리즘과 같이 큰 문제를 작게 쪼개서 문제를 해결해 나가는 알고리즘입니다. 다.. 2021. 12. 9.

[Data Structure] B-Tree란? 안녕하세요 Foma 💻 입니다! 오늘은 트리 자료구조 중 균형 끝판왕 (이름 자체가 Balanced - Tree)인 B-Tree에 대해 알아보겠습니다. 바로 시작할게요~ B-Tree의 배경 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. - 위키 백과 - 즉, 이진 트리를 조금 더 효율적으로 확장한 자료구조에요! 이진 탐색 트리는 최악의 경우 O(n)의 시간 복잡도를 갖기 때문에 그것을 조금 더 효율적으로 만든 것이 O(logn)의 시간 복잡도를 갖는 AVL 트리였습니다. 하지만 만약 2천만개의 데이터가 있다면 log20,000,000 = 24 즉, 최대 2.. 2021. 12. 6.

[Data Structure] AVL 트리 구현해보기 (feat. Swift) 안녕하세요 Foma 💻 입니다! 저번 시간에 AVL 트리가 뭔지 이론에 대해 알아보았는데요. (혹시 안보신 분들은 여기 에서 확인해주세요!) 오늘은 AVL 트리를 직접 구현해보려고 합니다. 바로 시작할게요~ AVLNode 기본적으로 이진탐색트리의 노드와 똑같지만 왼쪽과,오른쪽 자식의 높이와 밸런스 팩터를 측정할 변수를 따로 만들어었습니다. class AVLNode { var value:T var leftChild:AVLNode? var rightChild:AVLNode? var height:Int = 0 var leftHeight:Int { return leftChild?.height ?? -1 } var rightHeight:Int { return rightChild?.height ?? -1 } var.. 2021. 12. 6.

[Data Structure] AVL(Adelson-Velsky and Landis) 트리란? 안녕하세요 Foma 💻 입니다! 오늘은 저번에 정리했던 이진 탐색 트리를 더 업그레이드(?)한 자료구조인 AVL 트리에 대해서 알아보도록 하겠습니다. (혹시 이진 탐색 트리에 대해 모르시는 분들은 여기 에서 보고 와주세요!) 바로 시작할게요~ AVL(Adelson-Velsky and Landis) 트리란? 🤔 컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 스스로 균형을 잡는 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다. - 위키 백과 - 즉, .. 2021. 12. 1.

[Data Structure] 이진 탐색 트리(Binary Search Tree) 구현해보기 (feat.Swift) 안녕하세요 Foma 💻 입니다! 저번 시간에 이진 탐색 트리가 뭔지 이론에 대해 알아보았는데요. 오늘은 이진 탐색 트리를 직접 구현해보려고 합니다. 바로 시작할게요~ BSTNode 이진 탐색 트리의 노드를 만들어 주겠습니다. 노드는 값,왼쪽,오른쪽 자식의 노드 정보를 가지고 있습니다. class BSTNode { var value:T var leftChild:BSTNode? var rightChild:BSTNode? init(value:T) { self.value = value } } Binary Search Tree 이진 탐색 트리의 최상단 값을 가질 root를 프로퍼티로 정의했습니다. struct BinarySearchTree { var root:BSTNode? Insert public mutatin.. 2021. 11. 18.

[Data Structure] 이진 탐색 트리(Binary Search Tree)란? 안녕하세요 Foma 💻 입니다! 오늘은 트리 자료구조 중 효율적인 검색,삽입,삭제를 할 수 있는 이진 탐색 트리에 대해서 알아보겠습니다. 바로 시작할게요~ 이진 트리(Binary Tree)란? 🤔 이진 탐색 트리는 이진 트리 자료구조로 되어있기 때문에 먼저 이진 트리가 뭔지에 대해 알아보겠습니다. 이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.... - 위키 백과 - 즉, 노드마다 자식이 2개 이하인 트리를 말합니다. 아래 그림처럼 이루어진 트리를 말합니다. (자식이 없어도 되고, 하나여도 되고, 두 개여도 됩니다.) 이진 탐색 트리(Binary Search Tree)란? 🧐 이진 탐색 트리는 다음과 같은 속.. 2021. 11. 17.

[Data Structure] 해쉬 테이블(Hash Table) 구현해보기(feat. Swift) 안녕하세요 Foma 💻 입니다! 오늘은 저번 글에서 해쉬 테이블의 이론에 이어서 직접 구현해 보려고 합니다! (혹시 저번 글을 안보셨다면 여기 를 통해서 보고 와주세요~) 바로 시작할게요~ HashTable 먼저 저는 해쉬 함수를 Digit Folding 알고리즘을 이용해서 만들 것이기 때문에 key값을 String으로 설정했습니다. 또한 충돌이 났을 때 해결 방법으로 Chaining 기법을 사용하였지만 연결 리스트 대신 배열을 사용했습니다. 아래와 같이 typealias로 별칭을 설정해주고 버킷을 이중배열로 선언했습니다. public struct HashTable { public typealias Key = String private typealias Element = (key:Key,value:Val.. 2021. 11. 16.

[Data Structure] 해쉬 테이블(Hash Table)이란? (feat. 이론) 안녕하세요 Foma 💻 입니다! 오늘은 우리가 아주 흔하게 사용하고 있는 해쉬 테이블, Swift로 말하면 딕셔너리에 대해서 알아볼 거에요! 이미 구현되어 있는 코드로 쉽게 사용했는데 직접 구현하려고 하니 진짜 복잡하더라구요. 그래서 오늘은 해쉬 테이블에 대해서 정리해보려고 합니다! 바로 시작할게요~ 해쉬 테이블(Hash Table)이란? 정의는 아래와 같습니다. 해시 테이블은 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. - 위키 백과 - 즉, key와 value를 사용해서 데이터를 저장하는 자료구조입니다. key값으로 value를 한 번에 찾을 .. 2021. 11. 15.

[Algorithm] 퀵 정렬(Quick Sort)란? (feat. Swift) 안녕하세요 Foma 💻 입니다! 오늘은 드디어 정렬 알고리즘에서 말 그대로 매우 빠른 수행시간을 가진 퀵 정렬에 대해서 알아보려고 합니다! 바로 시작할게요~ 퀵 정렬(Quick Sort)이란? 🧐 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. - 위키 백과 - (참고로 리처드 호어가 퀵 정렬을 개발했을 당시 나이는 26살이라고 하네요...) 합병 정렬과 같이 분할 정복 알고리즘에 속하고 평균적으로 매우 빠른 수행속도를 자랑합니다. 퀵 정렬 과정 🔨 퀵 정렬을 하기 위해선 피봇(Pivot)이 핵심이 되는데요. 여기서 피봇은 어떤 것일까요? 피봇은 바로 기준입니다. 피봇을 가장 첫 번째 인덱스를 선택할 수도 .. 2021. 10. 25.

[Algorithm] 힙 정렬(HeapSort)이란? (feat.Swift) 안녕하세요 Foma 💻 입니다! 저번 시간에 힙이란 자료구조에 대해서 알아보았는데요. (혹시라도 안보신 분은 여기 에서 보고 와주세요!) 오늘은 힙을 이용해서 정렬을 하는 힙소트에 대해서 알아보려고 합니다! 바로 시작할게요~ 힙 정렬((HeapSort)이란? 🧐 힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. - 위키 백과 - 즉, 힙을 이용해서 정렬을 하는 방식이에요. 힙 정렬 과정 🔨 힙 정렬 과정은 힙에서 삭제를 구현할 때와 똑같아요. 삭제과정이 아래와 같은데요. 모든 노드를 삭제하고 배열에 차례로 쌓게되면 어떻게 될까요? 최대힙이라면 가장 큰 숫자가 차례.. 2021. 10. 19.

[Data Structure] 힙(Heap)이란? (feat. Swift) 안녕하세요 Foma 💻 입니다! 요즘 알고리즘을 공부하고 있는데 그 중 힙소트에 대해 알게 되었습니다. 힙소트를 하려면 힙이라는 자료구조가 필요하더라구요. 그래서 힙이 무엇이고 어떻게 구현하는지에 대해 정리하려고 합니다! 바로 시작할게요~ 완전 이진트리(Complete Binary Tree)란? ⛓ 먼저 힙에 대해 알아보기 전에 완전이진트리에 대해서 알아보겠습니다. 이유는 힙이 완전이진트리로 되어있기 떄문입니다. 완전 이진 트리에서, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h 에서 1부터 2h-1 개의 노드를 가질 수 있다. 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다. - 위키 백과 - 즉, 맨 마지막.. 2021. 10. 15.

이전 1 2 3 4 5 6 다음

728x90

티스토리툴바