목록코딩 (6)

율코딩

[오라클] 인덱스 클러스터링 팩터

클러스터링 팩터(Clustering Factor)는 특정 컬럼을 기준으로 같은 값을 같는 데이터가 서로 모여있는 정도를 의미라며, 군집성 계수라고 표현할 수있다. CF(클러스터링 팩터)가 좋은 컬럼에 생성한 인덱스는 검색 효율이 매우 좋다. 예를 들어 거주지역 = '제주'에 해당하는 고객 데이터가 물리적으로 근접해 있으면 흩어져 있을 때보다 데이터를 찾는 속도가 빠르다. CF(클러스터링 팩터)가 좋은 컬럼에 생성한 인덱스는 검색 효율이 좋다라는 의미는, 테이블 액세스량에 비해 블록 I/O가 적게 발생함을 의미한다. 그 이유는, 인덱스 ROWID로 테이블을 엑세스할 때, 오라클은 래치 획득과 해시 체인 스캔과정을 거쳐 어렵게 찾아간 테이블 블록에 대한 포인터(메모리 주소값)를 바로 해제하지 않고 일단 유지..
데이터베이스 2022. 10. 2. 20:32
[알고리즘] 백준 2110번 문제

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이문제는 이진탐색을 활용하여 푸는 문제이다. 반복적으로 gap을 설정하여 c개 이상의 공유기를 설치할 수 있는 경우를 찾는다. 먼저,start, end를 설정하여 최소 gap과 최대 gap 을 설정한다. 예제를 활용하여 코드를 구현해 보자. n,c = 5,3 arr = [1,2,4,8,9] start = arr[1] - arr[0] end = a..
알고리즘/백준 2022. 9. 25. 17:56
[알고리즘] 키로거 5397번

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 이 문제는 스택을 활용하여 푸는 문제이다. 이 문제의 아이디어는 스택을 2개를 만들어서 커서를 스택 2개의 중간지점이라고 생각하면 된다. 데이터를 삽입하면 왼쪽 스택에 데이터를 넣는다. '-'가 나오면 왼쪽 스택에 마지막 원소를 뺀다. ''가 나오면 반대로 오른쪽 스택에서 왼쪽 스택으로 원소를 옮기면 된다. 이 방식으로 코드를 구현하면 아래처럼 구현된다. n=int(input()) for ..
알고리즘/백준 2022. 8. 15. 19:25
[자료구조] 퀵정렬 VS 병합정렬

퀵 정렬 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘 기준값(Pivot)을 중심으로 자료를 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다. 왼쪽 부분집합으로 기준값보다 작은 원소를 이동시키고, 오른쪽 부분집합으로 기준값보다 큰 원소를 이동시킨다. 퀵 정렬은 분할과 정복(Divide and Conquer)라는 작업을 반복하여 수행한다. 특징 기본적으로 지원되는 내장 정렬 함수는 대부분은 퀵 정렬을 기본으로 한다. 성능은 pivot 값을 어떻게 선택하느냐에 따라 크게 달라질 수 있음. 시간 복잡도: 최선의 경우 O(NlogN), 최악의 경우 O(N^2) 활용 케이스 메모리가 부족하고(병합정렬 사용 불가)할 경우 배열이 이미 정렬/역정렬되어있을 가능성이 없고(퀵..
자료구조 2022. 8. 15. 19:01
[알고리즘/백준] N과 M(1) 백트래킹 문제 풀이

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 설명 1부터 N중 하나를 선택한 뒤 다음 1부터 N부터 선택할 때, 이미 선택한 값이 아닌 경우 선택 M개를 선택 할 경우 프린트 아이디어 백트래킹 재귀함수 안에서 for 문 돌면서 숫자 선택 ( 이 때 방문여부 확인) 재귀함수에서 M개를 선택할 경우 print 시간복잡도 N!: 중복이 불가, N = 10까지 가능 자료구조 방문 여부 : bool[] 선택한 값 입력 배열: int[] n,m..
알고리즘/백준 2022. 5. 29. 18:50
[알고리즘] 백트래킹(Backtracking)이란?

백트래킹(backtracking) : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 알고리즘 문제 모든 경우의 수를 확인해야할 때 for로는 확인이 불가능 한 경우 (깊이가 달라질 때) 백준 15649 N과 M(1) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://hyeyul-k.tistory.com/11
알고리즘 2022. 5. 29. 18:18
Prev 1 Next