• 서론 • 지난번 게시글에서는 요트 다이스 최적 선택 알고리즘을 구현한 방법을 소개하며, 평균 점수 200점대 초반이라는 준수한 성능을 보였다고 언급했었다. 게임 플레이 에이전트를 만들었으니, 통계와 분석을 진행해 보는 것이 당연한 수순이다. 이번에는 평균 점수뿐만 아니라 다양한 데이터를 추출하여 시각화해 보았다. • 점수 분포 살펴보기...

• 서론 • 왜 하게 되었는가 요트 다이스의 룰을 차용한 Pancht라는 게임에 AI 대전 모드를 넣게 되었다. 이 AI는 숙련된 플레이어의 실력에 준하는, 또는 그 이상의 실력을 갖춰야 고티어 플레이어와 유의미한 대결이 가능할 것이다. 숙련된 플레이어의 의사 결정을 모방해서 로직을 직접 작성하는 방법도 있겠지만 코드가 매우 복잡해질 것으로 예상되...

• Spready 스팀 페이지 • • Spready 플레이스토어 • • Spready Demo 플레이스토어 • 게임 소개 Spready에 대해 간단한 소개부터 하자면, 4개 챕터로 이루어진 색칠하는 3D 퍼즐 게임이다. 각 스테이지에는 캔버스가 배치되어 있다. 플레이어는 크레파스와 지우개를 사용해 모든 캔버스를 ...

4781번: 사탕 가게 문제 링크: 4781번: 사탕 가게 개요 각 테스트케이스마다 사탕 n개의 칼로리와 가격이 주어졌을 때, m만큼의 돈으로 얻을 수 있는 최대 칼로리를 출력하는 문제이다. 0/1 배낭 문제의 형태를 띠고 있지만 각 사탕을 무제한으로 구매할 수 있고, 가격이 정수가 아니라는 점을 고려해야 한다. 풀이 n과 m 입력받...

1395번: 스위치 문제 링크: 1395번: 스위치 개요 세그먼트 트리를 이용해 쿼리를 수행하고 부분합을 출력하는 문제이다. 그러나 원소의 개수와 쿼리의 개수가 최대 100,000으로, 평범한 세그먼트 트리로 풀이하면 시간 초과를 맞이하는 미래가 찾아온다. 이 문제는 ‘느리게 갱신되는 세그먼트 트리’ 알고리즘을 이용할 것이다. 평범한 세그...

1017번: 소수 쌍 문제 링크: 1017번: 소수 쌍 개요 수의 리스트가 주어지면, 리스트에 있는 모든 수에 대해 두 수를 합해 소수가 되도록 짝을 지어줄 수 있는지 여부(A)를 확인해야 한다. 또한 첫 번째 수와 짝지었을 때 A가 되는 모든 수를 오름차순으로 출력해야 한다. 이 문제에서 주어진 리스트는 하나 뿐이지만 두 그룹으로 나누어...

16916번: 부분 문자열 문제 링크: 16916번: 부분 문자열 개요 문자열이 두 개 주어지면, 두 번째 문자열이 첫 번째 문자열의 부분 문자열인지만 판단하면 되는 간단해 보이는 문제이다. 쉽게 떠오르는 방법인 브루트 포스로 풀면 문자열 길이가 n일 때 시간복잡도가 O(n^2)이 되는데, n이 최대 100만이므로 시간 초과를 피할 수 없다....

2696번: 중앙값 구하기 문제 링크: 2696번: 중앙값 구하기 개요 문제가 시킨 일인 수열이 주어지면 홀수 번째 수를 읽을 때마다 중앙값을 출력하는 작업만 착실하게 수행하면 되는 문제이다. 하지만 매번 수열을 정렬하고 중간 인덱스 값을 출력하는 방식으로는 시간초과를 피할 수 없다. 따라서 우선순위 큐를 두 개 이용해서 풀이할 것이다. ma...

14621번: 나만 안되는 연애 문제 링크: 14621번: 나만 안되는 연애 개요 주어진 그래프에서 노드들을 연결하는 최단 거리 트리의 총 거리를 구하는 문제이다. 최소 스패닝 트리 알고리즘 중 크루스칼 알고리즘을 이용해 풀이하겠다. 최소 스패닝 트리에 대해 [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 포스...

17387번: 선분 교차 2 문제 링크: 17387번: 선분 교차 2 개요 두 선분의 양 끝 점이 주어지면 교차 여부를 출력하는 문제이다. ccw 알고리즘을 이용해 두 점이 만드는 선분에 대해 다른 한 점이 어느 방향에 위치하고 있는지를 알아낼 수 있고, 이를 이용해 교차 여부를 확인할 것이다. 풀이 ccw 함수 int ccw(int ...