CS/Algorithm (8) 썸네일형 리스트형 [Kotlin] DFS, BFS 기본 구현 DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. 가장 머리 속에 남아있는 설명은 학부시절 들었던 설명인데, "DFS는 내가 보려는 드라마 시리즈들을 쭉 정주행 하는 것이고, BFS는 한 회씩 두루두루 보는 것이다." 라는 것 기본 구현에 익숙해지면 응용하는 문제들을 해결하는 데에 도움이 되기 때문에, 백지에 바로 작성이 가능해 질 때까지 보는 중.. 📎 백준 1260 문제를 바탕으로 글을 작성한다. Depth-First Search(DFS) 보통 Stack 혹은 재귀를 사용해 구현한다. 각 방법의 기본 구현 코드와 해당 방법을 사용했을 때의 장점을 살펴보겠다. Stack을 사용한 구현 fun dfsWithStack(graph: ArrayList, index: Int) { val visited = M.. 에라토스테네스의 체 ‣ 에라토스테네스의 체(Eratosthenes' sieve)고대 그리스의 수학자 에라토스테네스가 고안한 소수를 찾는 알고리즘아래의 사진처럼 마치 체를 치듯이 수를 걸러내어 소수만 남기기 때문에, 에라토스테네스의 체 라고 부른다. ‣ 동작 방식에라토스테네스의 체는 임의의 정수 n이 있으면 그 이하의 소수들을 O(nloglogn)O(nloglogn)O(nloglogn)의 시간 복잡도로 전부 찾아낼 수 있는 상당히 효율적인 알고리즘이다. 에라토스테네스의 체는 다음과 같은 원리로 진행된다.각 수에 대해 그 수의 배수를 모두 제거하는 작업을 수행한다.2의 배수를 제거할 때 n2 \frac{n}{2}2n 번, 3의 배수를 제거할 때 n3 \frac{n}{3}3n 번, 4의 배수를 제거할 때 n4 \frac.. 유클리드 호제법(Euclidean algorithm) ‣ 유클리드 호제법 유클리드에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘으로, 두 수의 최대공약수를 구하는 알고리즘이다. 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 것으로, 서로 호(互)와 덜(나누기) 제(除)를 써서 호제법이다. ‣ 예시: 1071과 1029의 최대공약수 계산하기 [일반적인 방법] 일반적으로 최대공약수를 구한다고 생각한다면, 먼저 소인수분해를 떠올린다. 1071 = 17 x 7 x 3 x 3 1029 = 7 x 7 x 7 x 3 두 수를 소인수분해한 결과, 공통된 소수를 찾으면 된다. 이를 통해 두 수의 최대공약수(GCD)가 " 7 x 3 = 21 "인 것을 알 수 있다. 하지만, 이 방법은 수가 커질 수록, 소인수분해를 수행하기 어려워진다는 단점이 있다. 유.. N진법 ⚠️ 코드 없이, 설명만 작성된 글입니다.[N진법]?10진법에 익숙한 우리에게 N진법은 다소 어색하게 느껴진다.하지만, 우리는 이미 일상에서 다양하게 N진법을 접하고 있다.예를 들어 생각해 보자.연필은 한 다스는 12자루이다.그럼 연필이 30개면? 2다스 6자루가 된다.즉, 10진수로 30은, 12진수로 26이된다.연필 12자루 / 셔터스톡아직 애매한가?그럼 계란의 경우도 생각해보자.계란은 한판에 30개로 구성된다.그럼 계란이 3판에 3개가 추가로 있다면 총 몇 개의 계란이 있는 것일까?답은 93개이다.즉, 30진수로 33은 10진수로 93이 되는 것이다.우리는 이처럼, 이미 자연스럽게 다양한 진법을 실생활에 사용해 왔다. 단순하게 아래와 같이 생각하고, 변환법을 바로 알아보자.N진법 = 모든 자리 수가.. 힙(Heap) 🥪🥅목표우선 순위 큐를 위하여 만들어진 자료구조, 힙(Heap)에 대해 이해한다.배열을 사용하여 힙(Heap)을 구현할 수 있다.힙(Heap)의 삽입과 삭제를 이해한다. 🤔시작 전…우선순위 큐(Priority-Queue)란?데이터틀이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나간다.자료구조삭제되는 요소스택(Stack)가장 최근에 추가된 데이터큐(Queue)가장 먼저 들어온 데이터우선순위 힙(Priority-Queue)가장 우선순위가 높은 데이터우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 이 중에서 힙(Heap)으로 구현하는 것이 가장 효율적이다.표삽입삭제순서 없는 배열O(1)O(n)순서 없는 연결 리스트O(1)O(n)정렬된 배열O(n)O(1)정렬된 연결리스트O(n)O(1)힙O.. 스택(Stack) 🥪Stack목표스택(Stack)의 기본 연산을 이해한다.Kotlin과 Python으로 Stack을 구현할 수 있다.📖개념한쪽 끝에서만 자료를 넣고 뺼 수 있는 LIFO(Last In First Out) 형식의 자료구조🧮연산스택(Stack)은 LIFO를 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.pop(): 스택에서 가장 위에 있는 항목을 제거한다.push(item): item 하나를 스택의 가장 윗 부분에 추가한다.peek(): 스택의 가장 위에 있는 항목을 반환한다.isEmpyty(): 스택이 비어있을 때 true를 반환한다. ⚒️구현문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.배열과 달리 스택은 상수시간(O(1)에 i번째 항목에.. 큐(Queue) 🥪🥅목표큐(Queue)의 기본 연산을 이해한다.Kotlin과 Python으로 Queue를 구현할 수 있다.📖개념컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식이다. 🧮연산큐(Queue)는 FIFO(First-In-First-Out)을 따른다.add(item) : item을 리스트의 끝부분에 추가한다.remove(): 리스트의 첫 번째 항목을 제거한다.peek(): 큐에서 가장 위에 있는 항목을 반환한다.isEmpty(): 큐가 비어있을 때에 true를 반환한다. ⚒️구현Kotlin으로 구현한 큐 예시 코드는 아래와 같다.class Queue { private val items = mutableListOf() fu.. 시간 복잡도와 공간 복잡도 알고리즘 성능 평가 어떤 알고리즘이 있을 때, 그 알고리즘의 성능 평가는 어떻게 할 수 있을까요? 알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'라는 척도를 사용합니다. 그 중 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때, 복잡도가 낮을 수록 좋은 알고리즘이라 말합니다. 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 1_1. 시간 복잡도 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 갖는 코드도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결.. 이전 1 다음
