오딩이

🔍 완전 탐색 완전 탐색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법입니다. 코딩 테스트 문제를 풀 때, 우선 완전 탐색으로 접근하여 답을 찾고, 성능 개선을 위해 다른 알고리즘을 사용하며 시간과 메모리를 줄여나가는 것이 좋습니다. 보통 순열, 조합, 부분집합과 같은 조합적 문제와 함께 푸는 문제들이 많이 출제되는데, 만약 조합된 결과에 순서가 의미가 있다면 순열, 순서가 의미가 없다면 조합, 선택하는 개수가 고정되지 않고 상황에 따라 다르다면 부분집합을 사용합니다. 🔍 순열 (permutation), 중복순열 순열은 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것입니다. 즉, 서로 다른 n개중 r개를 택하는 것이죠!(nPr)순열은 팩토리얼과 연관되어있는데,..

최장 증가 수열 : Longest Increasing Subsequence 📌 최장 증가 수열이란? 어떤 배열이 있을 때, 배열의 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출한 것입니다. 예를들어, [4, 2, 3, 1, 5, 6]이라는 배열이 있을 때 LIS는 [2, 3, 5, 6]이 됩니다. 점차 증가하는 배열은 [4, 5, 6] 또는 [2, 3, 5, 6] , [3, 5, 6] 등 여러 부분집합이 있을 수 있지만, 그 중 부분집합의 최대 배열을 의미하므로 LIS는 [2, 3, 5, 6]이 됩니다. 🔍 가장 먼저 생각해 볼 수 있는 풀이는 완전탐색(Brute-Force)입니다. 수열의 모든 부분 집합을 구하여 그 부분 집합이 증가 수열인지를 판단합니다. 완전탐색으로 풀 경우 부..