나홀로 프로그래밍 공부하기

문제 출처 : algospot.com :: JLIS algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 algospot.com 1. 문제를 해결하기 전 알아둬야 하는 이론 (1) 최적 부분 구조 최적 부분 구조(Optimal substructure) : 어떤 문제에 대해서 분할 방식에 성립하는 조건으로 각 부분 문제의 최척해를 통해 전체 문제의 최적해를 얻어낼 수 있는 경우 최적 부분 구조가 성립한다고 말한다. 즉, 각 부분 문제의 최적해가 전체의 최적해로 이어지는 경우를 말한다. 반대로 작은 부분 문제의 ..

문제 출처 : algospot.com :: WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 algospot.com 참고 자료 : [알고리즘2] 08.02 와일드 카드 문제 (WILDCARD) in 알고리즘 문제해결전략 (종만북) - YouTube 1. 문제 분석 ? : 어떤 글자와도 대응 * : 어떤 문자열에도 대응 여기서 문제를 해결하는데 *를 어떻게 처리하는지에 대한 어려움이 발생한다. *가 m번 발생하면 문자열을 m+1개의 조각으로 분해할 수 있다! ex. t*l?*o*r?ng*s -> [t..

1. 동적 계획법 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 주어진 문제를 더 작은 문제로 나눈 뒤 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산한다. 이 중 어떤 문제는 다른 두 개 이상의 부분 문제를 푸는데 사용될 수 있기 때문에 답을 여러번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하여 속도를 향상시킬 수 있다. 캐시(Cache) : 이미 계산한 값을 저장해두는 메모리의 장소 중복되는 부분 문제(Overlapping Subproblems) : 두 번 이상 계산되는 부분 문제 2. 메모이제이션(Memoization) 동적 계획법에서 함수의 결과를 저장하는 장소(캐시, Cache)를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법 주어진 입력에..

문제 출처 : algospot.com :: FANMEETING algospot.com :: FANMEETING 팬미팅 문제 정보 문제 가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가 algospot.com 1. 문제 해결을 위한 사고 과정 (1) 무식하게 풀기 팬의 수 N, 멤버의 수 M이라할 때 팬미팅 과정을 하나하나 시뮬레이션하는 방법 대략 O(M(N-M)) = O(NM_M^2)의 시간을 필요로 함 그러나 N과 M이 최대 200,000인 경우를 생각하면 제한 시간 안에 해결하기 어려움 (2) 곱셈으로 변형하기 1) 대략적인 생각 팬과 멤버들을 길이가 N과 M인 정수 배열로 생각하면 ..

문제 출처 : algospot.com :: FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체 algospot.com 1. 문제 해결을 위한 사고 과정 (1) 무식하게 풀기 각 판자 높이의 배열 h[]가 주어졌을 때 l번 판자부터 r번 판자까지 잘라내서 사각형을 만듦 가장 간단한 방법은 가능한 모든 l과 r로 만들 수 있는 사각형의 값을 계산한다. 2중 for문을 통해 계산할 수 있으므로 시간 복잡도는 O(n^2) 그러나 문제에서 제한된 입력의 최대 입력은 20,000으로 20,000^2은 1억을 넘어가므로 제한 시간(1..

문제 출처 : algospot.com :: QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 algospot.com 참고 자료 : [알고리즘2] 07.02 쿼드 트리 뒤집기 (QUADTREE) in 알고리즘 문제해결전략 (종만북) - YouTube 1. 문제 해결을 위한 사고 과정 (1) 무식하게 풀기 주어진 쿼드 트리 압축을 풀어서 실제 이미지를 얻고 상하 반전한 뒤 다시 쿼드 트리를 압축 하지만, 문제에서 주어진 제한에 의해 곧이곧대로 구현할 수 없음 이런 경우 선택할 수 있는 접근 방법은 ..

참고자료 : [알고리즘2] 07.01. 분할 정복과 카라츠바 알고리즘 in 알고리즘 문제해결전략 (종만북) - YouTube 1. 카라츠바의 빠른 곱셈 알고리즘 개요 구 소련의 아나톨리 알렉세예비치 카라츠바가 1960년대에 발견한 알고리즘 수백자리, 수만 자리가 되는 큰 정수를 곱할때 주로 사용하는 분할 정복의 한 예 큰 정수들을 배열을 이용해 저장하고 각 배열의 자리는 십진수의 자릿수를 의미한다. 두 큰 정수 A와 B가 있을 때, 배열을 이용하여 10^i번째 자리수를 각각 A[i], B[i]에 저장한다. A[i]와 B[j]의 곱셈 값을 C[i+j]에 저장하여 직관적인 코드를 작성할 수 있다. 2. 두 큰 수를 곱하는 O(n^2)시간 알고리즘 카라츠바의 빠른 곱셈 알고리즘을 구현하기 전에 먼저 마찬가지로..

1. 분할 정복(Divide & Conquer)이란? 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산하는 방법 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 2. 분할 정복을 사용하는 알고리즘의 3 가지 구성 요소 먼저, 분할 정복을 사용하기 위해서는 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다. 문제를 더 작은 문제로 분할하는 과정(Divide) 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(Merge) 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(Base case, 기..