본문 바로가기

728x90

Algorithm36

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

[Swift] 2019 KAKAO BLIND RECRUITMENT 블록 게임 Problem 코딩테스트 연습 - 블록 게임 [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2 programmers.co.kr Solution 1. 먼저 검은 블록을 떨어뜨려 삭제가 가능한 블록들을 찾아낸다. 주어진 블록은 차례대로 1번 블록의 0,1,2,3 타입, 2번 블록의 0,1,2,3 타입 , 3번 블록의 0,1,2,3타입이 있다고 가정할 때 검은 블.. 2022. 3. 28.

[JS] 프로그래머스 폰켓몬 Problem 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr Solution 1. nums의 길이의 반을 구한다. let half = nums.length/2 2. Set에 nums에 있는 번호를 넣는다. let set = new Set() for (let i = 0; i < nums.length; i++) { set.add(nums[i]) } 3. Set의 사이즈와 nums의 길이의 반과 비교해 더 작은 것을 반환한다. return Math.min(set.size,half) Source Code fun.. 2022. 2. 6.

[Swift] Baekjoon 나이순 정렬 10814번 Problem 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net Solution 1. 딕셔너리를 활용해 유저 정보를 넣는다. key값으로 나이를,value값으로 이름을 넣습니다. 만약 딕셔너리에 key값이 비어있지 않다면 value에 추가로 append 해줍니다. var userDic:[Int:[String]] = [:] let numberOfUser = Int(readLine()!)! for _ in 0.. 2022. 1. 30.

[Swift] 2022 KAKAO BLIND RECRUITMENT 주차 요금 계산 Problem 코딩테스트 연습 - 주차 요금 계산 [180, 5000, 10, 600] ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"] [14600, 34400, 5000] programmers.co.kr Solution 1. records의 기록대로 시간을 계산해 저장한다. var timeInfo:[String:Int] = [:] var parkInfo:[String:Int] = [:] func calTimeByRecord(_ records:[String],_ parkIn.. 2022. 1. 19.

[Swift] 2022 KAKAO BLIND RECRUITMENT k진수에서 소수 개수 구하기 Problem 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr Solution 1. n을 k진수로 바꾼다. let change = String(n,radix: k) 2. 바꾼 문자를 0을 기준으로 나눈다. let numbers = change.split(separator: "0") 3. 소수인지 판별한다. func isPrimeNumber(_ n:Int) -> Bool { if n == 1 { return false } if n == 2 || n == 3 {.. 2022. 1. 19.

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

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

[Swift] 프로그래머스 월간 코드 챌린지 3 n^2 배열 자르기 Problem 코딩테스트 연습 - n^2 배열 자르기 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부 programmers.co.kr Solution 1. 배열에 숫자가 채워지는 규칙을 파악한다. 배열에 숫자가 채워지는 규칙은 i행에 i개의 i가 채워지고 그 다음 i+1부터 n까지 채워집니다. 예를 들어 n이 10이고 i가 5라면 5번째 행은 5가 5개가 먼저 채워집니다. -> [5,5,5,5,5] 그리고 6(5+1)부터 10까지 채워집니다. -> [5,5,5,5,5,6,7,8,9,10] 2. 시작되는 행과 열, 끝나는 .. 2021. 12. 1.

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

이전 1 2 3 다음

728x90

티스토리툴바