본문 바로가기

개인 공부/알고리즘6

[알고리즘] 재귀 & 그리디 알고리즘 🎯 목표 재귀 알고리즘의 구조를 이해한다. 그리디 알고리즘을 이해하고 자주 나오는 유형을 익힌다. 🔄️ 재귀 알고리즘 자기 자신을 다시 호출하는 구조를 가진 알고리즘이다. 보통 더 작은 구조를 다시 호출해서 해결한다. 이는 분할-정보 알고리즘과 유사하다. public void recursion(int n) { if (n == MIN_SIZE) { // 가장 작은 단위의 일을 한다. } // 가장 작은 단위가 될 때까지 쪼갠다. return recursion(n - 1); } ✌ 특징 코드가 이뻐보일 순 있다. 하지만 스택 오버플로우가 발생할 수 있고 정확한 호출 회수를 예측하기 어렵다. 따라서, 재귀로 풀 수 있는 문제는 다른 방법으로 먼저 접근해본다. 그래도 재귀로 풀겠다면, 가장 작은 단위의 일에 대.. 2023. 5. 3.
[알고리즘] 정렬 & 탐색 알고리즘 😋 들어가기 앞서 이번에 알고리즘 스터디를 새롭게 시작했다. 내 입맛대로 그러면서 이전에 공부했던 것을 복습하는 시간을 가지기 위해서 한번 싹 정리해볼까 한다. 내가 가장 기본이라 생각하는 정렬, 탐색 알고리즘부터 시작해볼까 한다. 🎯 목표 정렬 알고리즘의 종류를 익히고, 각각의 시간복잡도와 구현법을 익힌다. 이분탐색 알고리즘을 이해한다. 🪜 정렬 알고리즘 이름 그대로 주어진 데이터를 정렬하는 알고리즘이다. 7가지 알고리즘이 기본이고, 응용에 따라서 추가적인 알고리즘이 존재한다. 1️⃣ 선택 정렬 선택한 값을 모두 비교해서 알맞은 자리를 찾는 정렬 알고리즘이다. 즉, 선택한 값 다음에 오는 모든 값을 비교해서 가장 작은 값과 위치를 바꾼다. 시간복잡도 : O(n^2) public void selectio.. 2023. 4. 28.
[알고리즘] 에라토스테네스의 체 알고리즘 문제 중에 소수 문제가 간혹 등장한다. 소수란, 1보다 큰 자연수 중에 1과 자기 자신만을 약수로 가지는 수이다. 어떤 수(N) 가 소수인지 확인하기 위해선 2부터 N-1까지의 모든 수로 나누어지지 않으면 소수인지 확인할 수 있다. def isPrime(N): for i in range(2, N): if N % i == 0: return False return True 정석의 코드를 예시로 들어봤다! 하지만 위의 코드로 넓은 범위의 수를 모두 확인하려면 많은 시간이 걸리게 된다. 이때 사용하는 알고리즘이 바로 에라토스테네스의 체이다! ✨ 에라토스테네스의 체란? 고대 그리스 수학자 에라토스테네스가 만든 소수를 찾는 방법으로 마치 체로 수를 걸러내는 것과 같아서 에라토스테네스의 체라고 부른다. 소수.. 2022. 7. 1.
[알고리즘] 배낭 채우기 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 위의 문제는 대표적인 배낭 채우기 문제이다. 찾아보니 배낭 채우기 문제는 두 가지 유형으로 나뉜다고 한다. 물건(보석)을 자를 수 있을 때의 "Fractional Knapsack"과 자를 수 없을 때의 "0-1 Knapsack Problem"로 나뉜다고 한다. 자를 수 있는 경우는 보통 그리디 알고리즘으로 해결한다고 한다. 이 글에서 다루는, 그리고 보통 많이 다루는 배낭 채우기 알고리즘은 자를 수 없는 경우이다. 배낭 채우기 문제를 푸는 방법은 여러 가지가 있다. 모든 .. 2021. 11. 24.
[알고리즘] 유클리드 알고리즘(최대공약수, 최소공배수 구하기) 일반적으로 최대공약수(Greatest Common Factor)와 최소공배수(Lowest Common Multiple)를 구할 때 소인수분해를 해서 구한다. 하지만 프로그래밍을 통해서 구할 때는 특정한 알고리즘 없이 직접적으로 구하기 까다롭다. 여기서 유클리드 알고리즘은 최대공약수를 구하는 특별한 알고리즘이다! ※ 유클리드 알고리즘이란? 주어진 두 수 사이에 최대공약수(GCD)를 구하는 알고리즘 유클리드 알고리즘은 "두 수 A, B가 주어졌을 때(단 A > B) A를 B로 나눈 나머지 r에 대해서 GCD(A, B) = GCD(B, r)이고, 여기서 나머지 r이 0이면 B가 두 수의 최대공약수이다!"라는 원리를 이용한 알고리즘이다. 알고리즘을 구현하는 방법은 재귀를 이용하는 방법과 반복문을 이용하는 방법 .. 2021. 7. 3.
[알고리즘] 가장 긴 증가하는 부분수열(LIS) ※ 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)이란? 부분 수열 중에서 각 원소가 이전 원소보다 큰 부분 수열 중에서 가장 긴 것! 예를 들어서, { 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 때, 증가하는 부분 수열은 { 2, 5 }, { 1, 4, 3} 등이 있지만 LIS는 { 2, 5, 7, 8 } 이다! 알고리즘은 시간복잡도에 따라서 2가지가 있다. ( O(N^2)과 O(N log N) ) 첫 번째 방법은 다이나믹 프로그래밍을 통한 방법이다. 시간 복잡도는 O(N^2) code#1 1 2 3 4 5 6 7 for (int i = 0; i arr[i]; } dp[0] = arr[0]; int idx = 0; for (int i = 1; i 2021. 6. 23.

티스토리툴바