본문 바로가기

Archived(CSE Programming)

 (169)
B+ Tree의 삽입 기본적으로 차수 3의 B+tree의 삽입에서는 다음의 원칙을 따른다. 삽입 시 Overflow가 발생할 것 같으면 먼저 Right Split 후에 삽입 leaf 노드에서는 삽입 시 가득 차 있으면 Right Split(기존의 값 중 오른쪽 값이 구분자로) 탐색 노드에서는 필요한 구분자 3개 중에서 중간 값을 루트 노드로 한다. 들어오는 쿼리 순 x,y,z, / 만들어지는 Page 순 A, B, C 로 해도 상관없음 참고사항 차수 4의 B+tree는 Split 시에 2/1개로 분리 후 삽입한다(따라서 왼쪽이 항상 무거워지게 구성되어 있다). 만약, 같은 ename '이순신'이 2000개 있다면? -> B+ tree에 같은 레벨로 두기 / 같은 rid 집합 속에 정렬되어있기(key value rid 집합 쌍..
Oracle Table Index Oracle에는 테이블 인덱스의 대표적인 두 가지 형태가 있다. Heap-Oraganized Table(HOT), Index-Organized Table(IOT) 이다. 1. Heap-Oraganized Table(HOT) 오라클에서 사용되는 표준 데이터베이스 테이블. 레코드들은 기본적으로 삽입 순으로 정렬된다(Heap 형태로 레코드들이 정렬되어 저장됨) Secondary Index(기본 키) : Unique Index(고유한 인덱스), Dense Index(해당되는 레코드들이 꼭 채워져야 함) 데이터 자체가 저장되는 것이 아닌 Index가 저장되어 Data Segment Table을 구성하여 해당 값을 저장. 데이터를 추가할 때 데이터에 맞는 세그먼트 중 첫 번째로 발견된 가용공간에 데이터를 저장. 데..
백준 14891_톱니바퀴 문제 : https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴 www.acmicpc.net 해당 문제도 역시 시물레이션 문제였다. 그래서 상황을 코드로 옮기는 것에 주안을 해야하는데, 문제의 조건을 하나 잘못 이해한..
백준 14499_주사위 굴리기 문제 : https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 해당 문제는 시뮬레이션 문제로 문제 상황을 그대로 프로그래밍으로 옮기는 과정이 중요하다. 주사위를 굴릴 때마다 각 면이..
ER 다이어그램(ER Diagram) 1. 정의 ER diagram 이란 Entity-Relationship Model을 표현하는 것으로, 현실세계의 요구사항(Requirements)들로 부터 Database를 설계과정에서 활용된다. 즉, 개념을 모델링하는 것으로 개체(entity)와 속성(attribute), 관계성(relationship) 을 표현한다. 일반적으로, Peter Cheng's Notation으로 표현한다(기타 방법은 맨 아래 참고) 1) 개체(Entities) 표현할 정보를 가지고 있는 독립적인 객체 또는 실체 비슷한 속성의 개체 타입을 구성하며 개체 집합으로 묶임 약한 개체(Weak Entity) : 고유적으로 구분될 정보를 가지고 있지 않은 개체. 이러한 Weak Entity는 의존하고 있는 주인 개체(Owner Ent..
프로그래머스_입국심사 문제 : https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 | 프로그래머스 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사 programmers.co.kr 처음에는 해당 문제가 왜 이분탐색인지 조차도 이해가 가지 않았다...
프로그래머스_섬 연결하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/42861# 코딩테스트 연습 - 섬 연결하기 | 프로그래머스 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 기본적으로 Kruskal 알고리즘을 통해 해결이 가능하였다. 최소 비용의 간선들만을 가져오면서 연결을 하는데 주의할 점은 Cycle을 만들지 않도록 하는 것이다. Cycle check는 Union Find의 방식을 통해 해결이 가능하였다. (부모까지 올라가서 부모 비교하면서 합치기) 풀이 1. 실제 이차원 vector의 graph를 만들어서 탐색하고 결과값 도출하기 답을 구할 수 있지만, 실질적으로 문제에서 주어지는 costs만을 통..
프로그래머스_NQueen 문제 : https://programmers.co.kr/learn/courses/30/lessons/12952?language=cpp# 코딩테스트 연습 - N-Queen | 프로그래머스 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다. 체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요. 제한사항 퀸(Queen)은 가로, 세로, 대각선으로 programmers.co.kr 풀이 1. 순열을 사용하기 처음 순..

티스토리툴바