본문 바로가기

5️⃣ CS15

[Swift Algorithm Note] 최장 증가 부분 수열 2 (feat. BS) 저번에는 DP로 최장 증가 부분 수열 (LIS)를 구하는 방법을 알아보았는데, 오늘은 DP보다 훨씬 시간복잡도가 좋은 이분 탐색 (BS)로 구하는 방법을 정리해보려고 한다. 두 가지 방법의 차이점도 알아보고, 이분탐색으로 LIS를 구하는 알고리즘도 구현해보자. (LIS에 대한 설명, 그리고 DP로 LIS 구하는 알고리즘이 궁금하신분들은 요기👇를 참고해주세요!) 2021.08.28 - [📍 Algorithm Note/🔍 with Swift] - [Swift Algorithm Note] 최장 증가 부분 수열 (feat. DP) [Swift Algorithm Note] 최장 증가 부분 수열 (feat. DP) 오늘은 최장 증가 부분 수열 (LIS)에 대해 정리해보려한다. LIS를 구하는 방법은 여러가지지만, .. 2021. 8. 29.

[Swift Algorithm Note] 최장 증가 부분 수열 (feat. DP) 오늘은 최장 증가 부분 수열 (LIS)에 대해 정리해보려한다. LIS를 구하는 방법은 여러가지지만, 그 중에서도 가장 간편한 DP를 이용한 방법을 소개한다. (DP에 대해 궁금하신 분들은 요기👇를 참고해주세요!) 2021.08.28 - [📍 Algorithm Note/🔍 with Swift] - [Swift Algorithm Note] 동적 계획법 (feat. Fibonacci) [Swift Algorithm Note] 동적 계획법 (feat. Fibonacci) 그리디 문제를 풀다가,, 도저히 안풀리는 문제를 맞닥뜨리고.. 알고보니 LIS라는 풀이 방법을 이용하는 문제였다. 근데 LIS는 DP(동적 계획법)을 사용해야 가장 효율적이라고 하더라.. 따라서 오늘 seolhee2750.tistory.com .. 2021. 8. 28.

[Swift Algorithm Note] 동적 계획법 (feat. Fibonacci) 그리디 문제를 풀다가,, 도저히 안풀리는 문제를 맞닥뜨리고.. 알고보니 LIS라는 풀이 방법을 이용하는 문제였다. 근데 LIS는 DP(동적 계획법)을 사용해야 가장 효율적이라고 하더라.. 따라서 오늘은 동적 계획법에 대해 공부해본 결과를 정리해보려고 한다. 📎 동적 계획법 (Dynamic Programming) 동적 계획법은 이름과는 좀 매칭이 안되는듯.?..한데 한 문제를 작은 부분으로 나누어 풀고, 그 결과를 저장하여 상위 문제를 풀어내는 상향식 접근 알고리즘이다. 위의 설명을 따르면 동적 계획법을 언제 사용할 수 있는지 구체화할 수 있다. 👇 1. 같은 반복을 시행하는 부분이 존재한다. 2. 동일한 반복 연산의 결과가 일정해야한다. 📌 Memoization 추가로, 위 설명을 다시 한 번 보면 작은.. 2021. 8. 28.

[Swift Algorithm Note] 꼬리 재귀 함수 (feat. Fibonacci) 저번 글에서 재귀 함수에 대해 다뤘다면, 이번엔 '꼬리' 재귀 함수에 대해 정리해보려고 한다. 피보나치 수를 구하는 함수를 구현해보면서, 재귀함수의 문제점을 알게 되었다. 그런데 이 문제점을 꼬리 재귀 함수가 해결해 준다는 사실을 알게 되었다,,!! 따라서 오늘은 꼬리 재귀 함수를 공부해보고, 구현 방법까지 확실히 이해해보자. 📎 꼬리 재귀 함수(Tail Recursive Call) 꼬리 재귀 함수는 일반적인 재귀 함수의 단점을 보완한다. 일반적인 재귀 함수가 가지는 단점은 바로 스택 오버플로우가 발생할 수 있다는 점,,!!!💥 일반 재귀의 경우, 저번 글에서 다뤘듯 스택에 함수 호출을 하나씩 쌓고, 거꾸로 반환 값을 넘기며 계산을 수행한다. (이 내용은 요기👇 글을 참고해주세요!) 2021.07.08 .. 2021. 7. 9.

[Swift Algorithm Note] 재귀함수 정리 (feat. Factorial) 대충은 알고 있었지만,, 지금까지는 알고리즘에 대한 정확한 개념 없이 문제를 해결해왔다. 하지만 점차 문제 수준이 높아지면서 알고리즘을 정확히 파악하고 있어햐 한다는 것을 느낌,, 따라서 오늘부터! 비교적 쉽고 필수적인 알고리즘부터 공부한 내용을 정리하려고 한다. 화이팅> Int { if num < 2 { return num } return Factorial(num-1) * num } print(Factorial(3)) // 6 print(Factorial(5)) // 120 먼저 Factorial 함수의 return 문을 보면, 위에서 구한 num * (num - 1)! 을 표현한 것을 확인 가능하다. 입력한 num 값에 대해 num - 1에 해당하는 Factorial 함수를 호출하고, num 값을 곱.. 2021. 7. 8.

이전 1 2 3 다음

티스토리툴바