우리들의 T'SPACE

유전 알고리즘(Genetic Algorithm, GA) 자연세계의 진화과정 및 유전법칙에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법(Global Optimization Method)생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용하였으며, 변이(돌연변이), 교배 연산, 세대, 인구 등의 개념을 문제 풀이 과정에서 사용문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최적해를 구하지는 못하더라도 최적해에 가까운 답을 얻을 수 있음 아래는 전반적인 GA의 과정이다 Starts with a population of individuals (다수의 개별 솔루션으로 시작)  Each..

P, NP, NP-hard, NP-complete 문제의 이해컴퓨터 과학에서 가장 중요한 개념 중  하나인 P, NP, NP-hard, NP-complete 문제.이 개념들은 알고리즘의 효율성과 문제의 복잡성을 이해하는 데 핵심적이다.이 글에서는 각 개념을 자세히 살펴보겠습니다.P Problems (Polynomial)P 문제는 결정론적 튜링 기계(deterministic Turing machine)로 다항 시간(Polynomial Time) 내에 해결할 수 있는 문제이다 결정론적 알고리즘: 특정 입력이 주어지면 항상 같은 출력을 예측 가능한 단계 순서로 생성하는 알고리즘이다\즉 Heuristic한 알고리즘은 결정론적이지 않은 비결정론적 알고리즘이라고 할 수 있다 다항 시간: 알고리즘의 시간 복잡도가인 ..

Convex Hull은 점들의 집합이 있을때 이 모든 점들을 포함하는 크기가 최소인 Convex Polygon을 찾는 문제이다Convexity 쉽게 말해 위처럼 집합 내에 있는 두 점을 연결한 선분이 집합 내에 있어야Convex하다고 할 수 있다하지만 우리가 찾는 것은 Convex Polygon 다각형임으로 모든 내각이 180도 이하라는 조건이 또 붙는다(180도는 각이 아님 ㅋ) 가장간단한 풀이 방법은 뭘까?? 좀 간지나게 mechanical way 라고 말하는데 2차원 평면에 수직되게 못을 점들과 대응되게 박아넣은뒤 고무줄을 늘려 풀어주면알아서 착! 감기며 Convex Hull 문제의 해를 구하게 된다 이렇게 시각적으로는 너무나 쉬운 내용이지많은 컴퓨터로 구현 혹은 알고리즘으로 정의 내리기가 매우 어..

문자열 처리는 컴퓨터 과학과 프로그래밍에서 매우 중요한 주제이다.특히, 특정 패턴을 텍스트 내에서 찾는 'Exact String Matching' 문제는 자주 등장하고 많은 분야에 활용된다. Exact String Matching 목표: 텍스트 문자열 T 내에서 패턴 문자열 P의 모든 출현 위치를 찾는 것.예: T = "AGCTTGAGCTTGA", P = "GCTTGA"라면, P는 T에서 두 번 index 1, 7에서 나타난다부분 문자열 (Substring)  vs Subsequence 부분 문자열(Substring): 원 문자열의 연속된 부분.S{i,j}=Si,S{i+1}...Sj예: S = "AGCTTGA"일 때, "GCT"는 부분 문자열.부분 수열(Subsequence):원 문자열에서 몇 개의 문자..

A* 알고리즘: 효율적인 경로 탐색을 위한 휴리스틱 기법 A* 알고리즘은 그래프에서 출발점부터 목표점까지의 최단 경로를 찾는 데 사용되는 휴리스틱 탐색 알고리즘이다.이 알고리즘은 Edsger W. Dijkstra의 최단 경로 알고리즘과 Best-First Search(최선 우선 탐색) 알고리즘의 아이디어를 결합하여 탐색 효율성을 높혀준다.A* 알고리즘의 기본 개념A* 알고리즘은 두 가지 주요 함수를 사용해 각 노드를 평가한다g(n): 출발점부터 현재 노드 n까지의 실제 비용 ->출발지에서 그 노드까지 비용h(n): 현재 노드 n부터 목표점까지의 예상 비용 (휴리스틱) ->그 노드에서 도착지 까지 비용 (예상)이 두 함수를 합한 f(n) = g(n) + h(n)이 각 노드의 평가 함수가 되며, A* 알고리..

https://tonnykang.tistory.com/224 Back Tracking 백트래킹 알고리즘백트래킹 알고리즘여러 다양한 방법을 순서대로 탑색하면서조건을 만족시키는 솔루션을 찾을 때 까지 되돌아가서 찾는 방법이다마치 미로를 탐색하는 것을 생각하면 되고탐색하다가 Promisingtonnykang.tistory.com백트래킹 알고리즘의 개선: 분기 한정법분기 한정법은 백트래킹 알고리즘을 개선한 방법으로, 각 노드에서 한계값(bound)을 계산하여 해당 노드가 유망한지 판단한다. 만약 한계값(bound)이 현재까지의 최적 해보다 좋지 않다면, 그 방향으로 탐색을 진행할 필요가 없음으로 필요없는 탐색을 줄일 수 있다.탐색 순서에는 크게 두가지가 있는데너비 우선 분기 한정법 (BF-Branch and B..

백트래킹 알고리즘여러 다양한 방법을 순서대로 탑색하면서조건을 만족시키는 솔루션을 찾을 때 까지 되돌아가서 찾는 방법이다마치 미로를 탐색하는 것을 생각하면 되고탐색하다가 Promising 하지 않은 길이면 (미로같은 경우 dead end) back track해서 마지막 갈림길로 돌아가 다른 길로 탐색하는 알고리즘이다탐색 Tree를 전체 탐색하지 않는 버젼의 DFS라고 할 수도 있다 이 알고리즘을 활용한 문제들이 여러개 있는데 N-Queens 문제N-Queens 문제는 N x N 체스보드에 N개의 퀸을 서로 위협하지 않도록 배치하는 방법을 찾는 문제이다. 각 퀸은 자신의 행, 열, 대각선 상에 있는 다른 퀸을 위협하지 않는 배치를 찾는 문제이다 백트래킹을 사용하여 N-Queens 문제를 해결할 때, 상태 공..

k-NN(k-Nearest Neighbors)는 지연 학습 알고리즘이다.정의k-NN은 함수가 Locally (가깝게) 근사되고, 모든 계산이 함수 평가 시점까지 미뤄지는 지연 학습 알고리즘이다. 분류와 회귀 모두에서 알고리즘은 Feature 공간에서 가장 가까운 k개의 훈련 예제를 기반으로 출력을 예측한다. 작동 방식학습 단계:k-NN의 학습 단계는 없다! Lazy Learning Algorithm학습 데이터는 단순히 저장되고, 명시적인 모델은 학습되지 않는다.예측 단계:분류:주어진 테스트 인스턴스에 대해, 알고리즘은 테스트 인스턴스와 모든 훈련 인스턴스 간의 거리를 계산한다.가장 가까운 k개의 훈련 인스턴스(이웃, neighbor)를 식별한다.테스트 인스턴스의 클래스 레이블은 k개 이웃 중 다수결 투표..

위와같은 두 행렬들이 있다하자 그러면 행렬 A와B의 곲 C는 다음과 같이 표현된다 그러면 아래와같이 이해될 수 있다 이 행렬의 곱 알고리즘의 시간 복잡도는 O(n^3)의 복잡도를 가진다 그래서 매우 큰 행렬들의 곱을 계산할 때는 매우 버거워진다 그의 결과로 분할정복의 한 방법인 Strassen 알고리즘이 나왔다 각 행렬들을 이렇게 4분할을 해보자 그러면 이렇게 계산해도 결과가 나온다 하지만 이건 또 결국 계산을 하다보면 O(n^3)의 복잡도를 가진다 그럼 Strassen 알고리즘은 어떻게 분할하냐? 위의 행렬들을 정의 해준다 그럼 아래와 같은 곱이 성립 한다 행렬의 곱셈을 한번 줄이고! 덧셈을 늘렸다! 그래서 O(n^3)->O(n^2) 로 수렴하게 된다 왜냐 행렬의 곱셈은 for문 골치거리이기 때문에 그..