혼자 공부하는 공간

안녕하세요 GODZ입니다. 오늘은 문자열을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 [설명] N개의 문자열의 집합에서 특정 문자열이 어떤 문자열의 접두사가 되지 않을 때, 그 집합을 접두사 X 집합이라고 한다. 또한 접두사 X 집합을 만족하는 가장 큰 집합을 만드는 게 관건이다. 문자열의 수(N)가 최대 50, 문자열의 길이(M)가 최대 50이다. ---> 각 문자열을 이중 반복문으로 순회해도 O(N^2)이고, 문자열을 비교할 때 역시 O(M)이므로 결국 O(MN^2) = 125,000회 이내이다. [로직] 기준 문자열(origin)과 N-1개의 비교 문자열(comp)을 비교한다. origin의 길이가 comp의 길이보다 같거나 짧을 때만 비교한다. ---> origin의..

안녕하세요 GODZ입니다. 오늘은 동적 프로그래밍을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 동적 프로그래밍에서 가장 중요한 것은 해결했던 문제에 대해서 다시 문제를 풀지 않는 것이다. 이전에 풀었던 문제를 메모이제이션(Memoization)을 통해 다시 계산하지 않고 결과 값만 가져온다. * res[k] : k원을 만들 수 있는 경우의 수 * cArr[i] : i번 째 동전의 값 * res[k] += res[k - cArr[i]] : k원을 만들 수 있는 경우의 수에 k - cArr[i]원을 만들 수 있는 경우의 수의 합 [설명] * cArr[i]가 1원일 때, 10원을 만들기 위해서는 res[10] += res[9] ---> cArr[i]가 1원일 때의 res[10] ..

안녕하세요 GODZ입니다. 오늘은 이분 탐색을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 정렬한 뒤, 최대값에서 빼가면서 총 예산(M)을 맞추는 것은 각 예산 값들이 100,000 이하인 것을 감안하면 시간 제한(1초)를 맞출 수 없다. 따라서 이분 탐색을 통해 시간 복잡도를 log로 변환하여 작업을 줄이도록 한다. 예산의 값 중 최대값을 찾는다. 최소값과 최대값의 평균값(mid)을 구해 각 예산에 상한선을 적용한 뒤, 총 예산과 비교한다. 총 예산보다 작으면, mid값을 저장하고 mid값을 최소값으로 설정한 뒤 4번 작업 반복. 총 예산보다 크면, mid값을 최대값으로 설정한 뒤 4번 작업 반복. 최대값과 최소값이 같으면 반복을 종료하고, 저장된 mid값 중 가장 큰 값을..

안녕하세요 GODZ입니다. 오늘은 이분 탐색과 투 포인터를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 N개의 수를 하나씩 입력 받으면서 합 sum을 구한다. sum >= S 일 때, 길이 len을 저장하고 0번 인덱스부터 S보다 작아질 때까지 sum에서 뺀다. sum = S 일 때, 2번 작업 반복. 모든 수를 다 입력 받았으면 저장한 길이 len 중 최소값을 찾는다. 만약 저장한 길이 len이 존재하지 않는다면 0을 출력한다. 4. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..

안녕하세요 GODZ입니다. 오늘은 문자열을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 원본 문자열의 길이 N(1이상 1백만 이하), 비교 문자열의 길이 M(1이상 36이하) 일 때, 원본 문자열을 한 번 순회하면서 비교 문자열을 지우는 작업은 O(NM)의 시간 복잡도를 가진다. O(NM)의 복잡도가 수없이 반복되기 때문에 제한시간을 맞출 수 없다. 따라서 문자열을 순회하면서 비교 문자열과 비교하는 작업을 병행한다. 원본 문자열을 저장할 자료구조는 StringBuilder나 Stack 그 외 List와 같은 mutable 구조를 사용하면 된다. 어떤 자료구조를 사용하든 간에 남은 원본 문자열을 출력해야 하므로 StringBuilder가 다른 자료구조에 비해 빠르다. 4. 코드..

더보기 NL JOIN Sort Merge JOIN Hash JOIN > * 조인이란 두 개 이상의 테이블을 하나의 집합으로 만드는 연산이다. * SQL 문에서 FROM 절에 두 개 이상의 테이블이 나열될 경우 조인이 수행된다. ex) A, B, C 테이블을 조인할 때, A와 B 테이블이 먼저 조인되고 조인된 결과와 C 테이블이 다시 조인되는 방식이다. ---> 이 때, 각 조인별로 다른 조인 기법을 사용할 수 있다. 1. NL JOIN * 프로그래밍에서 사용하는 중첩된 반복문(Nested Loop)과 유사한 방식으로 조인을 수행. * 반복문에서 외부에 있는 테이블을 선행 테이블(Driving Table) 또는 외부 테이블(Outer Table)이라하고 하고, 반복문의 내부에 있는 테에블을 후행 테이블(L..

더보기 인덱스 특징과 종류 트리 기반 인덱스 SQL Server의 클러스터형 인덱스 전체 테이블 스캔과 인덱스 스캔 전체 테이블 스캔 인덱스 스캔 비교 > 1. 인덱스 특징과 종류 * 인덱스는 원하는 데이터를 쉽게 찾을 수 있도록 돕는 개념이다. * 테이블을 기반으로 선택적으로 생성할 수 있는 구조이다. * 기본적인 목적은 검색 성능의 최적화. * INSERT, UPDATE, DELETE와 같은 DML 작업은 테이블과 인덱스 또한 함께 변경하므로 오히려 느려질 수 있기에 주의해서 사용한다. 1-1. 트리 기반 인덱스 * DBMS에서 가장 일반적인 인덱스 : B-트리 인덱스 * Root 블록, Branch 블록, Leaf 블록으로 구성되어 있다. Root 블록 * 가장 상위에 존재하는 블록. Branch ..

더보기 옵티마이저 실행 계획 SQL 처리 흐름도 > 1. 옵티마이저 * 사용자가 질의한 SQL 문에 대해 최적의 실행 방법(실행 계획 ; Execution Plan)을 결정하는 역할을 수행한다. * 최적의 실행 방법이란, 같은 일을 처리하더라도 최소의 일량으로 처리하는 방법을 말한다. * 규칙 기반 옵티마이저(Rule Based Optimizer ; RBO), 비용 기반 옵티마이저(Cost Based Optimizer ; CBO)로 분류할 수 있다. ---> 대부분의 관계형 DB는 비용 기반 옵티마이저만을 제공. A. 규칙 기반 옵티마이저 (RBO) * 규칙(우선 순위)을 가지고 실행 계획을 생성한다. * SQL문을 실행하기 위해 가용 인덱스 유무와 종류, SQL문에서 사용하는 연산자의 종류, SQL문에..