제약조건 만족 문제 : 주어진 제약조건을 만족하는 조합 해를 찾는 문제 1) 백트래킹 탐색 깊이 우선 탐색으로 변수에 허용되는 값을 하나씩 대입 만족하는 것이 없으면 이전 단계로 돌아가서 다른 값을 대입 2) 제약 조건 전파 : 인접 변수 간의 제약 조건에 따라 각 변수에 허용될 수 없는 값들을 제거하는 방식

* 게임 트리: 상대가 있는 게임에서 자신과 상대방의 가능한 게임 상태를 나타낸 트리 1. Mini-Max 알고리즘 Max 노드: 자신에 해당하는 노드. 자기에게 유리하도록 최대값 선택 Min 노드: 상대방에 해당하는 노드. 최소값 선택 단말 노드부터 위로 올라가면서 최대-최소 연산을 반복하며 자신이 선택할 수 있는 방법 중 가장좋은 값을 결정 2. α-β 가지치기 검토해 볼 필요가 없는 부분을 탐색하지 않도록 하는 기법 깊이 우선 탐색으로 제한 깊이까지 탐색하면서 α-β 자르기 α: Max 노드에 대해 정하는 값으로 현재까지 확보한 자식의 값 중 최대값 β: Min 노드에 대해 정하는 값으로 현재까지 확보한 자식의 값 중 최소 예) Min의 현재 노드가 4라면 4보다 작은 값들을 선택할 것이지만, 부모..

탐색 : 문제의 해가 될 수 있는 것들의 집합을 공간으로 간주, 문제에 대한 최적의 해를 찾기 위한 공간을 찾는 것 상태 공간 : 초기 상태로부터 도달할 수 있는 모든 상태들의 집합 문제의 해가 될 가능성이 있는 모든 상태들의 집합 상태 공간 그래프 : 상태 공간에서 각 행동에 따른 상태의 변화를 나타낸 그래프 맹목적 탐색 : 정해진 순서에 따라 상태 공간 그래프를 생성해 가며 해를 탐색하는 방법 깊이 우선 탐색 너비 우선 탐색 반복적 깊이심화 탐색 양방향 탐색 1) 깊이 우선 탐색(depth-first search, DFS) 백트랙킹이 주로 이 방법 사용 깊이 방향으로 탐색 메모리 공간 사용 효율적 최단 경로 해 탐색 보장 불가 ( 무한 루프 가능성) 2) 너비 우선 탐색(breadth-first se..

휴리스틱 탐색이라고도 한다. 휴리스틱 = 신속하게 어림짐작하는 것 예) 최단 경로 문제에서 목적지까지 남은 거리 짐작 종류언덕 오르기 방법best-first 탐색빔 탐색A* 알고리즘1) 언덕 오르기 방법 (hill climbimg method)현재 노드에서 휴리스틱에 의한 평가값이 가장 좋은 이웃 노드 하나를 확장해 가는 방법국소 최적해(local optimal solution)에 빠질 가능성이 있다 -> global optimal solution을 구하지 못할 수도 있다. -> 이웃 중에서 가장 좋은 걸 찾기 때문 2) 최상 우선 탐색 (best-first search)확장 중인 노드들 중, 휴리스틱에 의해 목표 노드까지 남은 거리가 가장 짧은 노드를 우선적으로 탐색 3) 빔 탐색 (beam searc..

문자열을 여러개의 토큰으로 분리시켜 저장시킬 때 사용. 1. 생성자 1) 띄어쓰기를 기준으로 분리 StringTokenizer st=new StringTokenizer(문자열); 2) 구분자를 기준으로 분리 StringTokenizer st=new StringTokenizer(문자열,구분자; 3) default: false true라면 구분자도 토큰에 포함시킴. StringTokenizer st=new StringTokenizer(문자열,구분자,true/false); 2. 메소드 1) nextToken() : 다음토큰을 String 타입으로 반 2) nextElement() : nextToken()과 동일하지만 Object 타입으로 토큰을 반환 -> 다른 타입으로 변환 가능

Virtual Memory 1. 디스크를 위해 메인메모리를 캐쉬로써 사용 2. 프로그램들은 메인 메모리를 공유한다 -> 각각은 고유한 가상주소 공간을 가지고, 다른 프로그램들로부터 보호된다 3. CPU와 OS는 가상주소를 물리주소로 변환한다 Virtual Memory에서 block은 page라고 부른다. 변환 miss가 되면 page fault라고 부른다. Address Translation 페이지 크기가 4K(4KB=2^12) Page Fault Penalty - page fault가 일어나면 페이지를 디스크로부터 fetch해와야 한다. -> 수백만 cycle이 걸림 -> os 코드에 의해 이루어짐 - page fault rate을 최소화하는 방법 1. fully associative 사용 2. 교체 ..