본문 바로가기

728x90

알고리즘49

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

[Swift] 프로그래머스 월간 코드 챌린지 3 공 이동 시뮬레이션 Problem 코딩테스트 연습 - 공 이동 시뮬레이션 n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리 programmers.co.kr Solution 해당 문제는 효율성이 핵심인 문제였습니다. 최대 행과 열이 각 10^9, 최대 쿼리 갯수가 20만으로 어마어마한 크기를 가지고 있어 만약 모든 위치에서 시뮬레이션을 돌릴 경우 최대 10^9 * 10^9 * 200000 이 됩니다. 시간초과를 피하기 위해선 목적지에서부터 쿼리의 역순으로 되돌아가면서 가능한 범위가 어디까지인지를 체크하는 것이 중요했습니다. 이론 설명 아래와 같이 목적.. 2021. 11. 15.

[Swift] 프로그래머스 월간 코드 챌린지1 스타 수열 Problem 코딩테스트 연습 - 스타 수열 programmers.co.kr Solution 1. a에 있는 숫자들의 갯수를 세준다. 숫자들의 갯수를 세주는 이유는 갯수가 많은 숫자로 정렬하여 시간 초과를 막기 위해서 입니다. func countNumbers(a:[Int]) -> [Int:Int] { var countDic:[Int:Int] = [:] for n in a { if countDic[n] == nil { countDic[n] = 1 }else { countDic[n]! += 1 } } return countDic } 2. 각 숫자들의 가장 긴 부분 수열 길이를 구해준다. 간단하게 설명하면 각 숫자들의 앞 뒤를 비교해줍니다. 만약 앞과 뒤 중 하나라도 현재 숫자와 같지 않은 숫자가 있다면 +2.. 2021. 11. 6.

[Swift] 프로그래머스 하노이의 탑 Problem 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr Solution 이번 문제의 핵심은 재귀를 이용하는 것 입니다. 아래와 같이 n개의 원판이 1번 기둥에 모두 있습니다. 1. 1번 기둥에 있는 원판 중 가장 무거운 원판을 제외한 원판(n-1개)을 모두 2번 기둥으로 옮깁니다. 2. 가장 무거운 원판을 3번 기둥으로 옮깁니다. 3. 2번에 있는 n-1개의 원판을 모두 3번으로 옮깁니다. 하노이의 탑을 푸는 과정을 간단하게 설명드리면 위와 같이 진행됩니다. 하지만 여기서 의문이.. 2021. 10. 31.

[Swift] 프로그래머스 월간 코드 챌린지 3 나머지가 1이 되는 수 찾기 Problem 코딩테스트 연습 - 나머지가 1이 되는 수 찾기 자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다. 제한사항 입 programmers.co.kr Solution 2부터 n-1까지 나누면서 나머지가 1이 나오면 반환한다. func solution(_ n:Int) -> Int { for i in 2.. 2021. 10. 29.

[Swift] 프로그래머스 월간 코드 챌린지2 110 옮기기 Problem 코딩테스트 연습 - 110 옮기기 0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다. x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 programmers.co.kr Solution 이번 문제의 핵심은 스택을 이용해서 풀어야 하는 것 입니다. 1. 문자열의 모든 "110" 삭제해준다. 여기서 스택을 사용하지 않으면 4번,18번,19번,21번 에서 시간초과가 나게 됩니다. 문자 하나식 쌓으며 가장 마지막 두 글자와 현재 글자를 비교해서 "110" 이라는 문자가 나오면 스택의 가장 마지막 두 문자를 지워줍니다. "110"을 지웠을 때 그 이전에 있던 문자와 이후에 있던 문자가 합쳐져서 또 ".. 2021. 10. 27.

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

[Swift] 프로그래머스 스티커 모으기(2) Problem 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr Solution 해당 문제는 DP(Dynamic Programming)으로 풀어야 하는 문제입니다. 1. 스티커의 갯수가 3개 이하라면 가장 큰 수를 반환한다. 스티커의 갯수가 3개 이하라면 하나밖에 뗄 수 없으므로 가장 큰 수를 반환합니다. if sticker.count < 4 { return sticker.max()!} 2. 첫 번째 스티커를 뜯어냈을 경우와 두 번째 스티커를 뜯어냈을 경우의 dp를 만들어줍니다. var dp1:.. 2021. 10. 19.

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

[Swift] 프로그래머스 위클리 챌린지 8주차 최소직사각형 Problem 코딩테스트 연습 - 8주차 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr Solution 1. 가로와 세로가 담긴 배열을 오름차순으로 정렬한다. let sorted = sizes.map{$0.sorted()} 2. 가로와 세로의 가장 큰 값을 곱해준다. return sorted.map{$0[0]}.max()! * sorted.map{$0[1]}.max()! Source Code 2021. 9. 30.

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

이전 1 2 3 4 5 다음

728x90

티스토리툴바