전체 글 (6) 썸네일형 리스트형 [세번째 공부] 분할 정복을 이용한 거듭제곱 거듭제곱을 할 때 분할 정복을 이용하는 방법이다. 간단하게 x를 n번 곱하라고 하면 x * x * x ... * x 이렇게 하나씩 곱해서 시간복잡도가 O(n)이 되지만 분할정복을 이용하면 시간복잡도가 O(log n)이 된다. 이 개념과 행렬의 거듭제곱을 이용하면 피보나치 수열을 빠르게 구할 수 있다. 예제는 다음과 같다. 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net [두번째 공부] 최장 증가 부분 수열 최장 증가 부분 수열은 LIS라고도 부른다. (LIS: Longest Increasing Subsequence) 어떤 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수들을 제거하여 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 일부 혹은 전체가 오름차순으로 정렬된 수열을 '증가 부분 수열'이라 하며 이 중 가장 긴 수열을 최장 증가 부분 수열이라고 한다. LIS의 길이 구하는 문제를 해결하기 위한 알고리즘으로 2가지가 존재한다. 1. 첫번째 알고리즘(시간복잡도 O(N^2)) 새로운 배열 D를 정의하자. D[i]: A[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이 A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작.. [2장 데이터] 아스키코드란 무엇인가. ASCII (American Standard Code for Information Interchange, 미국 정보 교환 표준 부호)는 초창기 문자 집합 중 하나로, 영어 알파벳과 아라비아 숫자, 그리고 일부 특수 문자를 포함한다. 아스키 문자 집합에 속한 문자는 7비트로 표현되는데 7비트로 표현할 수 있는 정보의 가짓수는 2^7 = 128개 문자이다. (실제로는 8비트를 사용하나 그중 1비트를 패리티 비트(parity bit)라고 불리는 오류검출 비트로 사용하기 때문에 실제 문자 표현을 위해 사용되는 비트는 7비트다.) 표에서 보듯이 아스키 문자들은 0부터 127까지 총 128개의 숫자 중 하나의 고유한 수에 일대일로 대응됩니다. 예를 들어 'A'는 십진수 65로 인코딩되고, 'a'는 십진수 97로, .. 이전 1 2 다음
