분류 전체보기 (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로, .. [첫번째 공부] 최단 경로 알고리즘 [출처] https://roytravel.tistory.com/340 [자료 구조] 최단 거리 알고리즘 정리 (다익스트라, 벨만 포드, 플로이드 워셜) 최단 거리 알고리즘이란 그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘이다. 일반적으로 네비게이션과 같은 길찾기에 적용된다. 최단 거리 알고리즘 종류는 크게 3가지가 있다. 1. roytravel.tistory.com V: 정점(Vertex) E: 간선(Edge) 각 알고리즘의 시간복잡도는 다 알고 있어야지. 알고리즘명 다익스트라 알고리즘 벨만-포드 알고리즘 플로이드-워셜 알고리즘 시간복잡도 다익스트라 알고리즘이란 무엇인가. 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색알고리즘이다. 흔히 인공지능 G.. [1차시] RAM와 ROM에 대해서 알아보자! RAM은 Random Access Memory의 약자로 임의의 영역에 접근해 읽고 쓰기가 가능한 주기억장치이다. 메모리는 보통 RAM을 지칭하는데 RAM은 읽기 쓰기가 가능하다. 즉, 정보를 저장하고 불러오기가 가능하지만 전원을 끄면 데이터가 휘발된다는 특징을 가지고 있다. RAM이 RAM인 이유는 어느 위치에 있는 데이터든 접근하는데 동일한 시간이 걸리는 특징을 가지고 있어 이런 명칭으로 정해졌다. ROM은 Read Only Memory의 약자로 컴퓨터를 구동시키기 위한 기본적인 정보를 담고있다. 그 외의 정보는 저장하지 않는다. 사람으로 비유하자면 본능과도 같다. 출처 위키피디아. [백준] AC RATING [현재 골드4] 2023.02.07 Silver I 달성! 2023.03.01 Gold V 달성! 2023.06.12 Gold B IV 달성! 이전 1 다음
