SYSADMIN'S CELLAR

깊이우선탐색(DFS)은 시작 정점에서 시작하여 한 분기만을 선택해가며 최대 깊이까지 탐색한 후 나머지 분기로 이동하여 더 이상 탐색할 정점이 없을 때까지 탐색을 수행하는 알고리즘입니다. 재귀 함수로 구현되며, 정점(=노드, vertex) 수와 간선(edge) 수를 합한 값(V+E)에 비례하는 시간 복잡도를 갖습니다. DFS로는 단절점(articulation points), 단절선, 사이클 찾기 등을 해결할 수 있습니다. DFS를 구현하기 위해서는 그래프를 표현할 인접 리스트, 방문한 노드를 기록할 배열, 그리고 재귀 구조가 필요합니다. 예제1) 입력으로 무방향 그래프가 주어지면 그 연결 요소의 수를 구하는 프로그램을 작성하라. 입력의 첫 행에는 정점의 수 V와 간선의 수 E가 주어지며, 둘째 행부터 E번..

문제: 임의의 64비트 숫자의 비트열을 역순으로 만들어 리턴하라. 가장 단순한 방법은 2. 비트 스왑에서 사용한 해법을 모든 비트에 적용하는 것이다. 이 방법을 사용하면 입력의 크기 n에 대해 O(n)의 시간이 소요된다. public static long flip(long x) { int i = 63; for (int j = 0; j >> i) & 1) != ((x >>> j) & 1)) { x ^= (1L 16 & 0xFFFF)] >> 32 & 0xFFFF)] >> 48 & 0xFFFF)] ; } 연산에 걸리는 시간을 비교해 보면, long형 정수 100억 ~ 200억을 입력했을 때, 룩업 테이블 방법은 14.62초가 소요되었고, 비트 스왑 방법은 10분 정도 기다리다가 안끝나길래 종료시켰습니다. 연산..

문제: 임의의 64비트 수 x의 i번째 비트와 j번째 비트를 교환하라. (0 ≤ i, j ≤ 63) 일반적인 배열 내에서 특정 위치의 값들을 스왑하기 위해서는 그 값을 저장할 변수가 필요하다. 그러나 비트는 어차피 0과 1밖에 없기 때문에, 두 위치의 비트가 다를 때만 해당 위치들의 비트를 반전시켜주면 문제를 상수 시간 내에 해결할 수 있다. public static long swap(long x, int i, int j) { if (((x >>> i) & 1) != ((x >>> j) & 1)) { x ^= 1L

문제: 입력값이 2의 거듭제곱인지 확인하라. 2의 거듭제곱인 수는 1로 세팅된 비트가 하나뿐이다. 모든 비트를 검사하는 방법보다 빠른 방법이 존재할까? XOR? AND? OR? 보수? 2의 보수? 4비트 입력을 가지고 여러 가지 시도를 해 본 결과, 2의 거듭제곱, 즉 1로 세팅된 비트가 하나 뿐인 이진수는 x = ~((x-1) OR ~x))를 만족하는 반면, 1이 두 개 이상 포함된 수는 저 식을 만족하지 않는다. 아래 표는 4비트 입력에 대한 모든 경우의 수를 확인해 본 결과이다. x 0000 0001 0010 0011 0100 0101 0110 0111 x - 1 0000 0001 0010 0011 0100 0101 0110 ~x 1110 1101 1100 1011 1010 1001 1000 (x-..

문제: 임의의 64비트 2진수가 주어지면, 1로 설정된 비트 중 가장 낮은 자리의 오른쪽에 위치하는 모든 비트를 1로 설정하라. 입력 예시: 0100...1000 출력 예시: 0100...1111 해설 이 문제는 이진수의 성질을 이용하면 간단히 풀린다. 입력에서 1을 뺀 값을 입력과 OR하면 된다. 입력에서 1을 빼면 가장 낮은 자리의 1이 내림되어 그보다 낮은 자리가 전부 1로 채워지기 때문이다. public static long carry(long x) { return ((x - 1) | x); }

어떤 2진수에 존재하는 1의 개수가 홀수개면 패리티는 1이 되고, 짝수개면 0이 된다. 예를 들어, 14=1110(2)에는 1이 홀수개 있으므로 패리티는 1이 된다. 1️⃣ 만약 임의의 64비트 2진수의 패리티를 구하는 프로그램을 작성한다면, 가장 먼저 떠올릴 수 있는 단순한 방법은 1이 홀수개인지, 짝수개인지 모든 비트를 검사하는 것이다. 검사(x & 1)하는 비트값이 0이든 1이든 하나씩 확인하므로 이 방법은 입력된 2진수의 크기 n에 따라 O(n)이 걸린다. public static short getParity(long x) { short result = 0; while (x != 0) {// x가 0이 될 때까지 오른쪽 시프트 할 예정 result ^= (x & 1);// x의 LSB가 1이면 초..

알고리즘이란? 알고리즘이란 문제를 풀기 위한 절차를 기술한 것입니다. 알고리즘은 하나 이상의 출력을 가져야 하고, 각 절차가 모호하지 않고 명확해야 하는 명확성, 유한한 시간 안에 결과를 생성해야 하는 유한성, 그리고 모든 컴퓨터에서 실행될 수 있어야 하는 유효성을 만족해야 합니다. 또 알고리즘이 예상대로 수행되는지에 대하여 수학적으로 증명하는 정확성 분석, 알고리즘이 문제를 얼마나 효율적으로 해결할 수 있는지 파악하는 효율성 분석을 통해 알고리즘을 평가합니다. 알고리즘의 효율성 분석에서는 알고리즘의 실행부터 완료까지 필요한 총 메모리의 양을 나타내는 공간 복잡도와, 마찬가지로 실행부터 완료까지 걸리는 시간을 나타내는 시간 복잡도를 평가합니다. 점근성능 알고리즘의 시간 복잡도는 알고리즘에 입력되는 데이터..

정규화(Normalization) 정규화: 관계형 모델에서 논리 스키마를 효과적으로 모델링하는 데 이용되는 기법 릴레이션의 정규형을 분석하여, 해당 릴레이션의 스키마가 실세계를 얼마나 효율적으로 반영하는지 평가할 수 있다. 정규화를 통해 생성된 릴레이션 스키마는 갱신 이상의 발생가능성을 최소화할 수 있다. 갱신 이상의 종류 삽입 이상: 필수적인 컬럼값만으로 새 레코드를 삽입하지 못하는 경우 삭제 이상: 삭제 시 의도하지 않은 데이터가 삭제되는 경우 수정 이상: 레코드들이 중복되어 데이터 일관성을 유지할 수 없는 경우 함수적 종속성 함수적 종속성: 속성들 간의 연관관계를 표현한 것 속성 A가 속성 B에 의해 결정될 때, 속성 A를 종속자(dependent)라 하고, 속성B를 결정자(determinant)라..

Structured Query Language 관계형 데이터베이스 관리 시스템에서 데이터를 관리하기 위한 비절차적 선언형 언어이다. SQL 구문은 그 역할에 따라 DDL, DML, DCL로 분류할 수 있다. *관계 대수는 절차적, SQL은 비절자적이다. SQL 데이터 타입 더보기 정수 TINYINT: 2^8 (-128~127) SMALLINT: 2^16 MEDIUMINT: 2^24 INT: 2^32 BIGINT: 2^64 고정 소수형 DECIMAL/NUMERIC(M, N): 전체 길이가 M이고 소수점 아래 길이가 N인 소수 부동 소수형 FLOAT: 4바이트 부동 소수 FLOAT(P): 유효숫자 자릿수가 P개인 부동 소수 DOUBLE: 8바이트 부동 소수 문자 CHAR(N): 길이가 N인 고정길이 문자열 ..

데이터베이스 모델링의 이해 데이터베이스 모델링 단계 DBMS 독립적 1. 사용자 요구사항 분석 ➡️요구사항 정의서 도출 2. 개념적 데이터 모델링 ➡️ER 모델 도출 ↓ 3. 논리적 데이터 모델링 DBMS 의존적 ➡️관계형 모델 도출 4. 물리적 데이터 모델링 ➡️물리적 세부사항 도출 1. 사용자 요구사항 분석 문서(RFP) 교환/인터뷰 등을 통하여 실제 업무에서 사용되는 데이터의 종류와 특징을 파악한다. 요구사항 도출 단계: 요구사항 명세서 도출 요구사항 분석 단계: 요구사항 명세서보다 더 상세화된 요구사항 정의서 도출 요구사항 기록 단계: 요구사항을 지속 반영하고 문서화한다. 2. 개념적 데이터 모델링 데이터 구조와 관계를 공통된 표기법(ER 모델)을 사용하여 추상화한다. 개체-관계 모델과 ER 다이..