목록개인 공부/알고리즘 (14)

코딩 기록 저장소

[알고리즘] 상태 공간 트리의 탐색

1. 상태 공간 트리 - 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리. - TSP를 예로 들어 상태 공간 트리를 설명함. TSP - 그래프에서 모든 정점을 순회하고 돌아오는 사이클을 해밀토니안 사이클이라 함. - 완전 그래프에서 해밀토니안 사이클은 수없이 많은데 TSP는 그중 짧은 것을 찾는 문제. - TSP의 형태는 다양하지만 이차원 평면상에 n개의 정점이 있고, 이 정점들로 구성된 가장 짧은 해밀토니안 사이클을 찾는 문제가 가장 단순한 형태의 TSP 문제. - 첫 번째 그림은 TSP 예로 평면에 6개의 정점이 존재함. 두 번째와 세 번째 그림은 해밀토니안 사이클의 예. 이 중 오른쪽의 그림은 모든 가능한 해밀토니안 사이클 중 가장 짧은 해밀토니안 사이클, 즉 최적해. - TSP는 임의의..
개인 공부/알고리즘 2023. 3. 8. 21:46
[알고리즘] NP - 완비

1. 문제의 종류 - 세상에 다양한 종류의 문제가 존재하고, 이 문제들은 해결 가능성에 따라 풀 수 있는 문제와 풀 수 없는 문제로 나눌 수 있음. - 컴퓨터 과학의 정지 문제나 힐버트의 열 번째 문제는 우리의 논리 체계하에서 풀 수 없는 대표적인 문제. - 풀 수 있는 문제는 해결하는 데 필요한 시간에 따라 현실적인 시간에 풀 수 있는 문제와 그렇지 않은 문제로 나뉨. - 현실적인 시간에 풀 수 없는 문제는 주어진 시간 범위에서 근사해를 구하는 것을 목표로 할 수 밖에 없음. - NP-완비는 현실적인 시간에 풀 수 없다 추정되면서 서로 강력한 논리적 연관성을 가진 특이한 문제군에 관한 것. - 보통 다항식 시간은 현실적인 시간이라 간주하고, 지수 시간은 비현실적인 시간이라 간주함. 2. Yes / No..
개인 공부/알고리즘 2023. 3. 7. 22:15
[알고리즘] 문자열 매칭

1. 원시적인 매칭 방법 - 문자열 매칭 : 텍스트 문자열이 패턴 문자열을 포함하고 있는지 알아보는 것. - 원시적인 방법으로는 순서대로 비교해나감. - 패턴을 총 n-m+1번 비교하면 작업이 완료됨. naiveMatching(A[], P[]) { for i
개인 공부/알고리즘 2023. 3. 4. 18:03
[알고리즘] 그리디 알고리즘

1. 전형적인 그리디 알고리즘의 구조 - 눈앞의 이익만 우선 추구하는 알고리즘을 총칭해서 그리디 알고리즘이라 함. - 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우도 있음. - 그리디 알고리즘은 최적화 문제를 대상으로 함. - 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼음. do { 가장 좋아 보이는 선택을 함; } until ( 해 구성 완료 ) - 그리디 알고리즘은 하나의 온전한 해가 만들어질 때까지 눈앞에 가장 좋아보이는 선택을 반복함. - 간선이 하나도 없는 집합에서 시작해서 간선을 하나씩 더해가면서 n-1개의 간선이 될 때까지 집합을 키워나감. - 각 단계에서 어떤 간선을 택할지 결..
개인 공부/알고리즘 2023. 3. 1. 19:49
[알고리즘] 그래프

1. 그래프 - 그래프는 현상이나 사물을 정점과 간선으로 표현하는 것. - 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타냄. - 방향을 가진 간선으로 그래프를 나타내면, 방향을 가진 그래프 또는 유향 그래프라고 함. - 반면, 간선의 방향이 없는 그래프를 무향 그래프 또는 무방향 그래프라고 함. - n개의 정점 집합 V와 이들 간에 존재하는 간선의 집합 E로 구성된 그래프 G를 보통 G=(V,E)로 표시함. 2. 그래프의 표현 - 크게 행렬을 이용하는 방법과 리스트를 이용하는 방법이 있음 인접 행렬을 이용한 방법 - 행렬 표현법은 이해하기 쉽고 간선의 존재 여부를 즉각 알 수 있다는 장점이 있음. - 정점 i와 정점 j의 인접 여부는 행렬의 (i, j) 원소나 (j, i) 원소의 값만 ..
개인 공부/알고리즘 2023. 2. 22. 18:24
[알고리즘] 동적 프로그래밍

1. 어떤 문제를 동적 프로그래밍으로 푸는가 - 동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 재귀적 중복을 해결하는 방법을 뜻함. - 피보나치 수 구하기에 동적 프로그래밍의 개념을 이해할 수 있는 핵심이 모두 들어있음. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 - n의 피보나치 수는 n-1의 피보나치 수와 n-2의 피보나치 수를 포함하고 있음. - 이처럼 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조를 가졌다고 함. - 동적 프로그래밍을 적용하려면 문제가 일단 이 성질을 가져야 함. - 간명하지만 때때로 엄청난 비효율을 초래할 수 있음. - 문제의 크기가..
개인 공부/알고리즘 2023. 2. 18. 22:57
이전 Prev 1 2 3 Next 다음