본문 바로가기

728x90

🖥 Computer Science/Algorithm16

[Algorithm] LRU(Least Recently Used) Cache 알고리즘이란? (feat. 페이지 교체 알고리즘) 안녕하세요 Foma 입니다. 오늘은 효과적으로 메모리를 관리할 수 있는 페이지 교체 기법 중 하나인 LRU Cache 알고리즘에 대해서 다뤄 보려고 합니다. 바로 시작할게요~ Least Recently Used Cache Algorithm이란? LRU 알고리즘은 FIFO, LFU, MFU 등과 같은 페이지 교체 기법 중 하나인데요. (페이지 교체 기법에 대한 것은 여기 에서 확인해 주세요 ㅜ) 그 중에서도 가장 오랫동안 사용하지 않은 페이지를 교체하는 방법입니다. LRU Design LRU Cache 알고리즘은 오랫동안 사용하지 않은 페이지를 삭제해 주고 새롭게 사용된 페이지를 추가해 줘야 합니다. 삭제와 추가를 효율적으로 빠르게 하는 것이 핵심인데요. 즉, O(1) 시간 복잡도로 해당 기능을 수행해야 .. 2022. 9. 22.

[Algorithm] Floyd's Cycle Detection이란? (feat. Linked List) 안녕하세요 Foma 입니다! 요새 LeetCode에서 Linked List의 사이클에 관련된 문제를 푸는데 slow, fast 포인터를 많이 이용하더라구요. 해당 풀이가 이해가 안돼서 찾아 보니 관련된 알고리즘이 있었고, 그것이 Floyd's Cycle Detection 이었습니다. 그래서 오늘은 링크드 리스트에서 사이클이 있는지 없는지를 확인할 수 있고, 해당 사이클의 시작점이 어디인지 알아낼 수 있는 Floyd's Cycle Detection 에 대해서 알아보려고 합니다. 바로 시작할게요~ Floyd's Cycle Detection 이란? 🔁 Robert W. Floyd가 고안한 리스트의 사이클을 빠르고 적은 메모리로 찾는 알고리즘입니다. (Robert W. Floyd는 플로이드 와샬 알고리즘을 만들.. 2022. 9. 18.

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

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

[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.

[Algorithm] 합병 정렬(Merge Sort)란? (feat. Swift) 안녕하세요 Foma 💻 입니다! 오늘은 분할 정복 알고리즘 중 하나인 합병 정렬에 대해서 알아보려고 합니다. 바로 시작할게요~ 분할 정복(Divide and Conquer Algorithm) 알고리즘이란? 🏡 위에서 합병 정렬은 분할 정복 알고리즘 중 하나라고 말씀드렸는데요. 그렇다면 분할 정복 알고리즘은 무엇일까요? 말 그대로 지금 해결할 수 없는 문제를 작게 쪼개서(분할) 풀어나가는(정복) 것입니다. 작은 문제를 해결하여 큰 문제를 해결해나가는 알고리즘으로 재귀 함수를 통해 자연스럽게 구현할 수 있습니다. 합병 정렬이란? 🤼‍♀️ 합병 정렬 또는 병합 정렬은 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1.. 2021. 10. 14.

[Algorithm] 시간복잡도(Time-Complexity)란? (feat. Big O) 안녕하세요 Foma 💻 입니다! 요즘 들어 알고리즘 공부를 하는데 알고리즘의 핵심인 시간복잡도에 대해서 정리하지 않은 것 같아서.. 이번 기회에 구체적으로 시간복잡도에 대해서 정리해보겠습니다! 바로 시작할게요~ 시간복잡도란? ⏱ 컴퓨터공학 용어로, 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 일반적으로 시간 복잡도는 점근 표기법을 이용하여 나타낸다. 즉, 계산되는 양에 따라서 시간이 얼마나 걸릴지를 나타내는 것입니다. 시간복잡도 표기법 🖊 시간복잡도 표기법은 빅오메가,빅세타,빅오 이렇게 3가지가 있습니다. 1. BigΩ (Best case) 빅오메가 표기법은 최선의 실행시간 즉, 가장 빠른 케이스를 나타내는 것입니다. 2. Big𝚯 (Average case) 빅세타 표기법은.. 2021. 9. 29.

[Algorithm] 삽입 정렬(Insertion Sort) 이란? (feat.Swift) 안녕하세요 Foma💻 입니다! 오늘은 학교 알고리즘 수업을 듣는 중에 삽입 정렬을 구현해보는 과제가 있었는데... 딱 이 방식이 어떤 것이고 어떻게 구현해야 한다! 라고 구체적으로 떠오르지가 않더라구요... 그래서 삽입 정렬이 무엇이고 어떻게 구현해야 하는지에 대해 정리해보려고 합니다! 바로 시작할게요~ 삽입 정렬이란? 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. -위키 백과 - 정렬하는 과정을 살펴보면 아래와 같습니다. 삽입 정렬 과정 82,10,9,72,31,45,60를 삽입 정렬을 하는 과정은 아래와 같습니다. 1. 먼저 맨 첫 번째인 82와 그 다음 숫자인 10을 비교해줍니다. 10이 더.. 2021. 9. 28.

[Algorithm] 백트래킹(Backtracking)이란? (feat. 예제포함) 안녕하세요 Foma 💻 입니다! 오늘은 프로그래머스 N-Queen 문제를 풀면서 해당 문제가 백트래킹 문제라는 것을 알게 되었는데요. 그래서 백트래킹이 무엇이고 어떻게 구현해서 사용해야 하는지에 대해 정리해보려고 합니다. 바로 시작할게요~ 백트래킹이란? 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만,.. 2021. 8. 28.

[Algorithm] 조합(Combination)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 정말 빈번하게 사용되는 "조합" 에 대해서 알아보도록 하겠습니다. 바로 시작할게요~ 조합이란? n개의 원소에서 r 개의 원소를 순서에 상관없이 뽑는 경우의 수 - 나무 위키 - 순열과 다르게 순서는 중요하지 않아요. 쉽게 설명하면 물건을 사고 총 가격을 구하는 것과 비슷해요. 과일로 예를 들면 사과,포도,수박이 있다면 사과,포도,수박 포도,사과,수박 수박,사과,포도 ... 등 어떤 방식으로 사도 총 가격을 똑같겠죠? 즉, 이루어진 과일이 똑같다면 하나의 조합으로 생각하는 것입니다. 코드 구현 먼저 경우의 수를 담을 배열을 만들어줍니다. var cases:[[Int]] = [] combination의 파라미터를 설정해주는데 인덱스들을 담고있는 ind.. 2021. 6. 27.

[Algorithm] 순열(Permutation)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 정말 빈번하게 사용되는 "순열"에 대해서 알아보도록 하겠습니다. 바로 시작할게요! 순열이란? 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 이른다. - 나무 위키 - 쉽게 설명하면 줄 세우기와 똑같아요. A,B,C라는 학생을 줄 세우는 방법은 ABC,ACB,BAC,BCA,CAB,CBA 등이 있겠죠? 이 중에서 2명의 학생으로 줄 세우는 방법은 AB,AC,BA,BC,CA,CB 등이 있을거에요. 코드 구현 경우의 수들을 담을 이중 배열을 만들어줍니다. var cases:[[Int]] = [] 몇 개를 뽑을지 정해줍니다. let pickCount = 3 본격적으로 순열 함수를 만들어줍니다. 파라미터로는 전체 인덱스가 담긴.. 2021. 6. 27.

이전 1 2 다음

728x90

티스토리툴바