본문 바로가기

알고리즘16

[알고리즘] LIS (최장 증가 부분 수열) 목차 LIS란? LIS는 Longest Increasing Subsequence의 약자이다. 말 그대로 최장 증가 부분 수열, 또는 가장 긴 증가하는 부분 수열이라고 불린다. LIS는 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘이다. 다만, 오름차순으로 정렬된 부분 수열이 연속적이거나, 유일할 필요는 없다. 풀이 방법으로는 DP를 활용한 방법과 이진 탐색을 활용한 방법이 있다. DP를 활용하면 조금 더 단순하지만 시간 복잡도가 O(n^2)이고 이진 탐색을 활용하면 조금 더 복잡하지만 시간 복잡도는 O(n logn)이다. 이번 글에서는 DP를 활용한 LIS만 살펴보도록 하겠다. LIS 접근 방법 & 예시 예시를 한번 보겠다. 수열 arr = {10, 20, 10, 30, 20, .. 2022. 3. 31.
[알고리즘] 큰 숫자 (정수) BigInteger 사용법 - JAVA [자바] 목차 BigInteger를 사용해야 하는 이유 가끔 알고리즘 문제들을 풀다 보면 큰 수를 처리해야 될 때가 있다. 여기서 큰 수란 int형의 범위를 넘어가고 심지어 long 형의 범위를 넘어갈 때이다. int형의 범위나 long형의 범위를 넘어서게 되면 모두 0으로 출력이 된다. 따라서 큰 수를 처리해야 할 때는 BigInteger를 사용해야 한다. BigInteger 사용법 BigInteger 선언 BigInteger number = new BigInteger("500000"); //선언할 때는 문자열 BigInteger를 선언할 때 보통 문자열을 인자 값으로 넘겨서 선언한다. BigInteger 계산 BigInteger number1 = new BigInteger("10000"); BigInteger.. 2022. 3. 27.
[알고리즘] LCS (최장 공통 부분 수열) 목차 LCS란? LCS는 Longest Common Subsequence의 약자이다. 말 그대로 가장 긴 공통된 부분 수열이다. LCS는 보통 주어진 두 수열에서 각각의 부분 수열들 중, 서로 같은 부분 수열 중에서 가장 긴 부분 수열을 뜻한다. LCS는 DP(다이나믹 프로그래밍)의 대표 유형 중 하나고 백준에서는 최소 난이도가 골드5 정도 된다. 따라서 LCS를 알면 DP 골드 문제들을 조금씩 풀 수 있게 된다. 예시를 하나 보겠다. s1 = ACAYKP, 그리고 s2 = CAPACK라고 하겠다. 문제 예시로 보자면 ACAYKP의 부분 수열을 표현하면 다음과 같다. ACAYKP : {A}, {C}, {A}, {Y}, {K}, {P}, {A, C}, ⋯ , {A, C, A, Y, K, P} CAPCAK의.. 2022. 1. 30.
[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming) 목차 다이나믹 프로그래밍이란? 다이나믹 프로그래밍 (Dynamic Programming) 또는 동적 계획법은 큰 문제를 작은 문제로 쪼개서 푸는 기법이다. 다이나믹 프로그래밍의 특징은 모든 작은 문제들은 단 한 번만 풀어야 한다는 것이다. 한 번 푼 것을 여러 번 다시 푸는 일이 없어 비효율적인 알고리즘을 개선시키는 방법 중에 하나다. 따라서 이미 정답을 구한 작은 문제의 결과는 따로 배열에 저장하고 나주에 필요할 때 다시 사용한다. 이것을 메모이제이션 (Memoization)이라고 한다. 그리고 다시 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞에서 메모한 작은 문제의 결괏값을O(1)의 시간복잡도로 이용해서 문제를 효율적으로 풀 수가 있다. 다이나믹 프로그래밍 접근 방법 다이나믹 프로그래밍의 .. 2022. 1. 23.
반응형

티스토리툴바