근사 문자열 매칭과 거리 함수 근사 문자열 매칭 (approximate string matching) 은 비슷한 문자열을 매칭하는 것을 말합니다. 거리 함수는 어떤 문자열과 문자열 사이의 거리를 구하는 함수로 다음 3가지의 예가 있습니다.해밍거리편집거리가중 편집거리 편집 거리 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집연산들의 최소 수 연산의 종류는 [삽입, 삭제, 교체, 유지]가 있습니다. DP Idea D(i,j)는 두 문자열 S1, S2에 대한 편집거리를 나타낸다고 할때, 제일 오른쪽 문자부터 비교를 하면서 연산들 중 값이 가장 작아지는 것을 고르면 됩니다. D(i,j)값은 아래 4가지 값들 중 가장 작은 값입니다:D(i,j-1) + 1 → 삽입D(i-1,j) + 1 → 삭제D(i-1,j-..
분류 전체보기
주제 선정 저희는 이전 프로젝트에서 TF-IDF나, cosine-similarity, n-grams와 같은 전통적인 NLP기법들을 사용했었습니다.2024.11.01 - [[Deep daiv.]/[Deep daiv.] Deep Learning 입문 프로젝트] - [Deep daiv.] 딥러닝 입문 프로젝트 (1) - Do you know? [Deep daiv.] 딥러닝 입문 프로젝트 (1) - Do you know?주제 Do you know? 게임 Do you know? 게임은 파리올림픽에 출전한 선수들의 이름을 맞추는 게임입니다. 선수들의 이름을 맞출 수 있는 힌트 단어를 플레이어에게 보여주고 플레이어는 해당 힌트 단hw-hk.tistory.com 그렇기 때문에, 이번 후반기 프로젝트에서는 전통적인 기법..
Zero-sum Games and AI A player's utility gain or loss is exactly balanced by the combined gain or loss of opponentsThis is a powerful concept important to AI development for measuring the cost/benefit of a particular move어느 한 플레이어에게 이득인 것은 반대편 상대에게는 손해인 제로 섬 게임이어야합니다. 이는 게임의 비용과 이득을 계산하는데에 필수적입니다. Games and AI Traditional strategy - Minimax:Attempt to minimize opponent's maximum reward at each s..
Min-Max Search Min-max algoritm is applied in two player gamesexample: chess, go, tic-tac-toe, and so on. The characteristics of two-player gamesLogic game: the game can be described by a set of rules and promisesFull information games: it is possible to know from given point in the game, what are the next available moves모든 rule이 공개되어있어야 하며, 모든 정보가 보여서 다음 가능한 step이 무엇인지 알 수 있어야합니다. Search using ..
반복적 깊이 심화 탐색 깊이 한계가 있는 깊이 우선 탐색을 반복적으로 적용하는 방법으로,메모리 사용이 최적화된 DFS와 최적해를 탐색하는 것이 보장되어있는 BFS의 장점만을 이용해 탐색하는 과정이다. 시간을 조금 걸릴 수 있지만,메모리의 사용량을 줄이고, 최적해를 찾을 수 있다는 장점이 있다. 반복적인 깊이 우선 탐색에 따른 비효율성이 클 수 있지만,실제 비용이 크게 늘지는 않는다.각 노드가 10개의 자식 노드를 가질 때, BFS대비 약 11%의 정도의 추가 노드 생성 양방향 탐색 초기 노드와 목적 노드에서 동시에 너비 우선 탐색을 진행하는 방법으로,초기 상태와 목표 상태를 기준으로 너비 우선 탐색을 번갈아 가면서 한 단계씩 탐색 범위를 확장한다. 중간에 만나는 노드가 생길 때까지 진행하기 때문에,너비 ..
그래프 탐색 방법 맹목적 탐색 (uniformed search)정해진 순서에 따라 상태 공간 그래프를 점차 확장 (open) 해가면서 해를 탐색하는 방법 탐색 과정:시작 시, 확장 (open) 공간에는 초기 상태 노드만 존재반복:만약 확장 (open) 공간이 비었다면, 목표 노드에 도달하는 해는 존재하지 않음확장 (open) 공간에서 하나의 노드 선택하여 제거If: 선택된 노드가 목표 상태라면 탐색을 종료하고 결과 반환Else: 선택된 노드에서 확장할 수 있는 모든 노드를 확장 (open) 공간에 추가 이때 이미 방문한 노드에 대해 처리를 해주지 않는다면 탐색이 무한 반복될 수 있다. 예를 들어,순환 그래프의 경우 탐색이 무한 반복되는 경우가 발생할 수 있다. 따라서 빈 탐색 완료된 (closed) 노드..
주제 Do you know? 게임 Do you know? 게임은 파리올림픽에 출전한 선수들의 이름을 맞추는 게임입니다. 선수들의 이름을 맞출 수 있는 힌트 단어를 플레이어에게 보여주고 플레이어는 해당 힌트 단어와 연관된 선수의 이름을 맞추는 게임입니다. 문제 정의 힌트 단어, 유사 단어 플레이어가 선수들의 이름을 맞추는 데 필요한 단어들은 반드시 선수들의 이름과 유사하고 관련성이 높은 단어이어야 합니다. 그러므로 이 게임을 성공적으로 만들기 위해서는 유사 단어, 즉 선수의 이름과 텍스트 유사도가 높은 단어를 찾는 것이 핵심 문제입니다. 난이도 게임을 좋아하는 사람이라면 난이도의 중요성은 말하지 않아도 알 것입니다. 유사 단어를 추출한다고 해도 그 단어들을 난이도에 맞게, 플레이어가 '재미있게' 플레이 할..
Model-Driven Engineering Model-Driven Engineering (MDE)An approach to software development where models rather than programs are the principle outputs of the development processThe programs executing on a hardware/software platform are generated automatically from the modelsSoftware engineers no longer should be concerned with programming language details or the specifics of execution platformsM..
