programing/Algorithm8 그리디 메소드 ( Greedy Method ) - 흔히 욕심쟁이 방법, 인공지능을 만들 때 손쉽게 사용 - 여러 가능성에 점수를 메기고 높은 쪽을 선택 - 오델로 같은 게임에서 모서리 쪽에 10점을 메기고 다른 자리에 9, 8, 7로 점수를 메기고 높은 점수를 먹을 수 있는 가능성을 택함 - 당장은 손해지만 나중에 이익을 보는 경로를 찾지는 못함 - 다른 알고리즘에 비하여 속도가 매우 빠름 2017. 3. 10. 백 트래킹 (back tracking) - 일종의 brute-force 알고리즘과 비슷함 - 대표적으로 8-queen 문제 - 모든 해를 찾도록 반복문으로 모든 경우를 살피도록 함 - 대신 도중에 절대로 해가 될 수 없는 경우를 미리 제거 2017. 3. 10. 다이나믹 프로그래밍 - 다음 두가지 조건을 만족하면 DP로 접근 1) 겹치는 부분 문제( overlapping subproblem ) 2) 최적 부분 구조( optimal substructure ) - 같은 문제를 구할 때마다 정답은 같이 때문에 각 문제를 한 번만 풀어야 함 - 따라서 정답을 한 번 구하게 되면 배열에 저장하여 다시 쓰도록 함 -> 메모이제이션 cf. 템플릿 메타 프로그래밍과 비슷함 (템플릿 메타 프로그래밍은 컴파일 타이밍에 미리 만들어져서 알아서 쓰게 됨 2017. 3. 10. 네트워크 연결된 차 위치 정렬 1. 네트워크로 연동된 차 위치를 일렬로 정렬 하려고 함단, 접속한 차의 댓수는 6 이하이고 앞부터 정렬 하려고 함나머지는 충돌만 안하면 신경 안써도 됨접속 안한차는 뺄까 했지만 그냥 놓아 둠 2. 일단 차의 처음 순서는 [mycar - 0 - 1 - 2 - 3 - 4](mycar가 조종하는 차라서 나머지 차와 다름)(0~4는 같은차) 3. 각자 내차에 대한 순서를 알고 있으므로 해당 위치의 차와 Swap 4. 연동이 시작되면 각 차들은 각자 자신의 순서에 맞는 위치로 이동 4-1 연동 후... 차의 인덱스는 각자 순서에 따라 인덱스가 정해져 있어서 mycar를 빼면 index 순서대로 정렬됨 5. 이동 하면서 동시에 각 차들은 자신을 뺀 다른 컴퓨터에 자신의 위치를 알려주어서 이동 시키도록 함 6. 충.. 2016. 12. 6. 이전 1 2 다음