[학교 수업]

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) 노드..

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..

Maximum sub-array Find the consecutive sub-array with maximum sum 이때 subarray란 전체 배열안에 연속된 부분 배열을 의미합니다. 즉, 전체 배열에서 부분 배열의 가장 큰 합을 구하는 문제입니다. 만약 배열에 음수가 없다면, 최대 부분 배열의 합은 전체 배열의 합이 될 것입니다.또한 배열에 양수가 없다면, 가장 큰 음수 하나이거나 조건에 따라서 빈 배열이 가장 큰 부분 배열의 합이 될 것입니다. 부분 배열의 길이가 0인 것을 허용하지 않는다면, 가장 큰 음수 하나가 가장 큰 부분 배열의 합이 될 것이고,부분 배열의 길이가 0인 것을 허용한다면, 빈 배열즉, 0이 가장 큰 부분 배열의 합이 될 것입니다. 이하에 적을 알고리즘은 부분 배열의 길이가 0..

Data Sharing volatile int ncount;void* do_loop(void *loop){ while(1) ncount++; return NULL;}int main(int argc, char *argv[]){ int status, sec; pthread_t thread_id; ncount = 0; sec = atoi(argv[1]); status = pthread_create(&thread_id, NULL, do_loop, NULL); if (status != 0){ perror("pthread_create"); exit(1); } sleep(sec); pthread_cancel(t..

탐색 (Search) 방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 과정 하노이 타워경로 찾기8-puzzle틱택토... 에이전트 (agent) 특정 환경 (environment) 내에 위치하여, 설계된 목적 (objectives) 을 만족 시키기 위하여, 자율적 (autonomous) 으로 유연하게 (flexible) 행동할 능력이 있는 컴퓨터 시스템 인공지능에서의 문제 풀이의 주체 지능형 에이전트는 센서로부터 인지된 주변 환경을 인지 (Perception) 하고 효과기 (actuator) 를 통해 외부환경에 적절한 행동을 취할 수 있는 로봇 / 기계 / 소프트웨어 에이전트의 종류Rational Agents (Rule base)"Do right thing."그냥 옳은 행동만을 하는 에이전트Simp..

Fibonacci Number 피보나치 수열은 다음과 같은 방식으로 전개되는 수열입니다.long fibonacci(int n){ return (n  위와 같이 피보나치 수열의 값을 재귀로 구하게 된다면 시간이 너무 오래걸린다는 문제가 있습니다.재귀적으로 짠 fibonacci()의 경우 아래와 같은 방식으로 호출이 일어납니다. 아래의 예시는 fibonacci(5)를 구하는 case입니다: 함수 호출을 총 15번하는 것을 볼 수 있습니다. 구하는 n의 값이 작은 경우 그리 크게 상관은 없지만, n이 커지게 된다면 2가지 문제점이 발생할 수 있습니다.재귀호출이 지나치게 많아져서 memory가 부족해 질 수 있다 → stack overflow느리다 → O(2^n)의 시간복잡도를 갖습니다 위 방식의 문제점은..