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이면 초..

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