qjatn0120

Minimax algorithm 게임의 진행 상태를 트리에서 정의할 수 있다. 현재 상태를 트리의 루트로 정의하자. 그리고 현재 상태에서 가능한 모든 행동을 해당 노드의 자식 노드로 정의할 수 있다. 만약 게임이 끝난다면 자식 노드는 존재하지 않는다. 아래는 틱택토 게임에서 3수 앞을 트리로 표현한 것이다. 내 말은 O, 상대의 말은 X이고, 내가 행동할 차례면 검은색 원으로, 상대가 행동할 차례면 회색 원으로 표시하였다. 위 트리에서 각 상태의 가치를 평가할 수 있다. 먼저 게임이 끝난 경우에는 가치를 쉽게 판단할 수 있다. 내가 이겼으면 1, 상대가 이겼으면 -1, 비겼으면 0으로 평가할 수 있다. 또한 행동할 수 있는 경우가 하나밖에 없다면, 다음 상태와 현재 상태의 가치는 똑같다고 할 수 있다. ..

게임이란? 에이전트를 구현하기 전에 먼저 게임을 어떻게 정의하고 구성하는지 알아둘 필요가 있다. 먼저 게임이 존재하기 위해서는 게임을 수행하기 위한 환경과 게임을 수행하는 주체가 있어야 한다. 마리오 게임으로 비교하자면, 마리오 게임 프로그램이 환경, 게임을 하는 사람이 주체에 해당한다. 주체는 본인의 행동을 환경에 전달한다. 행동은 마리오 게임이서 이동, 달리기 및 점프에 해당한다. 그러면 환경은 주체에게 행동 후의 상태와 행동으로 얻은 보상을 전달한다. 상태는 마리오 게임에서 현재 스테이지와 위치, 맵 모양 등에 해당하고, 점수는 행동으로 얻은 점수에 해당한다. 이때, 보상은 게임 시작부터 지금까지 얻은 총점수가 아니라 이 행동 하나만으로 얻은 점수로 정의한다. 또한 게임에서 가장 중요한 건 내 행동..

AI 게임 선정 포카전을 준비하기 위해 포스텍 알고리즘 동아리인 POSCAT의 인공지능 세미나를 진행하게 되었다. 이번 포카전에서 진행되는 게임으로 세미나를 진행하기에는 게임이 복잡할 것 같아 간단한 게임으로 세미나를 진행할 예정이다. 따라서 세미나에서 어떤 게임을 이용하여 연습할지를 정해야 했다. 포카전처럼 2인 대전 게임 형식이되 크게 복잡하지 않은 4목 게임(Connect 4)으로 선정하였다. State가 복잡하지 않고, action의 종류도 7가지로 적은 편이며 규칙도 간단하기 때문에 4목 게임으로 선정하였다. 4목 게임은 가로 7칸, 세로 6칸 크기의 판에서 진행되는 게임이다. 이 게임의 특징은 말을 놓을 '열'만 정할 수 있다는 점이다. 열을 정하고 나면, 해당 열의 빈칸 중 가장 아래에 있는..

A. 2-3 Moves code 문제 설명 0번에서 \(n\)번으로 이동하려고 한다. 현재 위치가 \(x\)일 때, \(x+2\), \(x+3\), \(x-2\), \(x-3\)으로 이동할 수 있다. \(n\)번으로 이동하기 위한 최소 이동 횟수를 출력해야 한다. 알고리즘 일단 \(n\)이 1인 경우는 2칸으로 예외 처리를 하였다. 만약 \(n\)이 3의 배수가 아니라면, \(\frac{n}{3}+1\)번 이동해야 한다. 계속 3칸씩 오른쪽으로 이동하다가, \(n\)을 3으로 나눈 나머지가 1이면 2칸씩 2번, 나머지가 2이면 마지막에 2칸 1번을 뛰어야 하기 때문이다. \(n\)이 3의 배수라면 단순히 3칸씩 계속 뛰면 된다. 따라서 뛰어야 하는 횟수는 \( frac{n+2}{3}\)이 된다. \(n\..

A. YES or YES? code 문제 설명 입력으로 들어온 문자열이 대소문자 구분하지 않고 yes인지 확인하는 문제이다. 알고리즘 입력으로 들어온 문자열이 3글자인지 확인하고, 3글자라면 글자가 각각 y, e, s인지 확인한다. B. ICPC Balloons code 문제 설명 문자열로 팀이 어떤 문제를 풀었는지 입력으로 주어진다. (어떤 팀이 풀었는지는 의미가 없으므로 주어지지 않는다.) 문제를 풀면 풍선을 하나 주지만, 처음으로 문제를 풀면 풍선 두 개를 준다. 모든 팀이 받는 총 풍선의 개수를 출력해야 한다. 알고리즘 먼저 문자열의 길이 만큼의 풍선을 주게 된다.그리고 문자열에 있는 알파벳의 종류 개수만큼 추가적으로 풍선을 주게 된다. C. Cypher code 문제 설명 먼저 처음 자물쇠가 어..

A. Round Down the Price code 문제 설명 숫자 \( n\)이 주어진다. \(n\)이하의 \(10^k\)꼴 (\(k\)는 음이 아닌 정수)인 수 중 가장 큰 수를 구한 뒤 \(n-10^k\)를 출력하는 문제이다 알고리즘 단순 구현 문제이다. 반복문을 이용하여 \(n\)이 넘을 때까지 1에서 10씩 곱해나가고, \(n\)을 넘기면 10으로 나눈다. 이 수가 \(n\) 이하의 수 중 최대인 \(10^k\)꼴의 수이다. B. Polycarp Writes a String from Memory code 문제 설명 하루에 최대 3종류의 글자만 적을 수 있다. 문자열 \(s\)가 주어지고 맨 앞글자부터 마지막 글자까지 순서대로 적을 때, \(s\)를 적기 위해 최대 며칠이 걸리는 지 출력해야 한다..

A. When? code 문제 설명 정수 \(0 \le K \le 100 \)이 주어진다. 21:00 으로부터 \(K\)분 지난 시간을 hh:mm 형식으로 출력해야 한다. 알고리즘 60분 이상인 경우 hour에 1을 더해주고, minute를 60만큼 빼준 뒤 출력하면 된다. B. Number Box code 문제 설명 정수 \(1 \le N \le 10\)과 \(N \times N\)짜리 정사각 행렬이 주어진다. 행렬의 각 값은 1이상 9이하이다. 한 점을 정한 뒤, 상하좌우와 대각선까지 총 8방향 중 한 방향을 정해 \(N-1\)칸 움직인다. 만약 범위 바깥으로 나가면 행렬의 반대 방향으로 이동한다. 예를 들어, 맨 왼쪽에서 왼쪽 방향으로 이동하면 맨 오른쪽으로 이동한다. 이와 같이, 총 \(N\)칸을..

A. A to Z String 2 code 1. 문제 설명 a부터 z까지의 글자가 \( N \) 개씩 있는 문자열이 있다. 이 문자열의 \(K\)번째 글자를 구해야 한다. 2. 알고리즘 \( K\)에서 \(N\)씩 빼나가면서 몇 번째 글자인지 확인하면 된다. B. 1D Pawn code 1. 문제 설명 1차원 배열에 폰이 몇 개 있다. 여기에 총 \(Q\) 개의 명령을 내린다. 각 명령은 특정 폰을 오른쪽으로 한 칸 옮긴다. 이때 폰이 맨 오른쪽에 있거나 옆에 다른 폰이 있으면 움직일 수 없다. \(Q\) 개의 명령을 내린 후 각 폰의 위치를 출력해야 한다. 2. 알고리즘 문제에 주어진대로 시뮬레이션을 진행한 후, 시뮬레이션 결과를 출력하면 된다. C. Robot Takahashi code 1. 문제 설..

A. Six Characters code 1) 문제 설명 + 알고리즘 길이가 3이하인 문자열 \( s\)가 들어온다. 문자열 \( s\)를 \( \frac{6}{len(s)} \) 번 출력하면 된다. B. At Most 3 (Judge ver.) code 1) 문제 설명 \(N \leq 300 \)개의 숫자가 주어진다. 이 중 최대 3개의 숫자를 골라서 합이 \( W \)이하로 만들 때, 가능한 합의 경우의 수를 출력하는 문제이다. 2) 알고리즘 \( O(N^3) \) 으로 모든 가능한 합 계산하고, 중복 제외한 뒤 개수를 출력한다. C. Poem Online Judge code 1) 문제 설명 + 알고리즘 N개의 문자열과 정수 쌍 \( (S, T) \)가 주어진다. set으로 문자열 중복 체크해주고, ..

A. Tokitsukaze and Strange Inequality code 1) 문제 해설 길이가 \(n \leq 5000\) 인 순열 \(p\)가 주어질 때 \( 1 \leq a p_d \)를 만족하는 \( (a, b, c, d) \) 쌍의 개수를 구하는 문제이다. 2) 알고리즘 \(cnt[i][j] \)를 \( p_1\)부터 \(p_i\)까지의 수 중, \(j \) 이하인 수의 개수라고 정의하자. \( cmt\)를 전처리해 놓으면 특정 구간 \( [a, b]\)에서 \( k\) 이하인 수의 개수를 \( O(1) \) 안에 구할 수 있다. \(b, c\)를 고정해두고 생각해보자. 그렇다면 위 조건을 만족하는 \(a \)의 ..