Computer Science 13

[인공지능] 기말시험 정리 (2)

컴퓨터 비전점잡음 영상에는 중간값 필터를 취하면 좋다.소벨과 라플라스 연산자는 각각 1차, 2차 미분에 의한 에지검출 연산자이다.거리측정자일반적인 거리측정자: 해밍 거리, 맨해튼 거리, 유클리드 거리군집의 평균벡터와 공분산행렬을 고려한 거리측정자: 마할라노비스 거리베이즈 분류기매개변수 방식(최대가능도추정 등): 패턴의 분포가 잘 알려진 모델(가우시안 모델 등)을 따른다고 가정한다.비매개변수 방식(k-NN 등): 유사한 입력은 유사한 출력을 낸다고 가정한다. 즉, 근접한 패턴들은 같은 클래스에 속할 가능성이 높다고 추정한다. 많은 양의 학습표본을 기억해야 하고, 많은 거리계산이 필요하므로 계산복잡도가 높다.분류기의 평가 기준정확도(accuracy): 분류기가 맞게 분류한 데이터 / 전체 데이터정밀도(pre..

Computer Science 2025.06.12

[인공지능] 기말시험 정리 (1)

게임트리최대최소탐색을 이용하여 게임문제를 해결하고자 할 때, 적절한 깊이 이상이 되면 자원 한계를 고려하여 경험적 지식을 반영한 평가함수를 통해 그 상태의 가치를 추정해야 한다.몬테카를로 트리 탐색은 탐색공간의 무작위 표본화(선택, 확장, 시뮬레이션, 역전파)를 바탕으로 탐색트리를 구성한다.선택 전략: 탐사와 활용의 균형을 이루는 전략 필요(UCT, UCB 등)시뮬레이션 전략: 무작위/유사 무작위 등역전파 전략: 가치 누적값과 방문횟수의 평균을 활용최적 행동 결정: 최대자식(가장 큰 보상), 강인자식(가장 많이 방문), 최대-강인 자식, 안전자식(저점이 높음) 지식표현지식데이터 → (분류, 정리) → 정보 → (개념화, 체계화) → 지식메타지식: 지식의 사용에 관한 관한 지식선언적 지식: 독립적, 단편적..

Computer Science 2025.06.12

[알고리즘] 깊이우선탐색(Depth-First Search)과 파이썬 구현

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

[알고리즘][비트연산] 3. 비트 뒤집기

문제: 임의의 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분 정도 기다리다가 안끝나길래 종료시켰습니다. 연산..

[알고리즘][비트연산] 2. 비트 스왑

문제: 임의의 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

[알고리즘][비트연산] 응용 문제 1-3

문제: 입력값이 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-..

[알고리즘][비트연산] 응용 문제 1-1

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

[알고리즘][비트연산] 1. 패리티(Parity) 계산하기

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

[알고리즘] 제1장 알고리즘 분석: 점근성능과 재귀 알고리즘의 성능

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

[DB] 제4장 정규화

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