우리들의 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 문제를 해결할 때, 상태 공..

get_dummies()https://tonnykang.tistory.com/216 k-Nearest Neighbors (k-NN) 모델 KNNk-NN(k-Nearest Neighbors)는 지연 학습 알고리즘이다.정의k-NN은 함수가 Locally (가깝게) 근사되고, 모든 계산이 함수 평가 시점까지 미뤄지는 지연 학습 알고리즘이다. 분류와 회귀 모두에서 알고리즘은tonnykang.tistory.comKNN 모델은 참 편하고 단순한 Base 모델로 사용하기에는 너무나 좋은 모델이다 하지만 각 instance간의 거리를 구해야하는 모델이기에범주형 Catagorical Feature같은 경우에는 문제가 생긴다... 예를 들어 아래와같은 데이터가 있다고 하자data = { 'Color': ['Red',..

네이브 베이즈는 베이즈 정리에 기반한 간단하지만 효과적인 확률론적 분류기의 집합이다."네이브(Naive)"라는 이름은 각 특성(또는 예측 변수)들이 클래스 레이블에 대해 서로 독립적이라고(independent) 가정하기 때문에 붙여졌다. 실제로 미국에서는나이브라고 발음한다단순한 사람보고  Don't be so Naive!이런식으로 사용된다 Independent 하다는 이 가정은 실제 데이터에서는 자 만족되지 않지만 계산을 크게 단순화시켜 준다.Bayes' Theorem 베이즈 이론P(C|X) = P(X|C)P(C) / P(X)  여기서:P(C|X)는 특성 X가 주어졌을 때 클래스 C의 사후 확률이다.P(X|C)는 클래스 C가 주어졌을 때 특성 X를 관측할 가능성인 값으로, 훈련 데이터 (Train Set..

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