분류 전체보기

문제 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 풀이 유클리드 호제법 회전하는 바퀴는 반지름 / (첫 번째 링과 i 번째 링의 반지름의 gcd) 로 구할 수 있다. 코드 #include using namespace std; int nums[100]; int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } int main() { ios_base::sync_with_stdio(0..

유저 인터페이스와 HUD 메뉴와 HUD 같은 유저 인터페이스를 만드는 아티스트와 프로그래머를 위한 정보와 안내서입니다. docs.unrealengine.com HUD(Heads-up Display)는 플레이어에게 게임에 대한 정보를 표시해 주기도 하고, 가끔 플레이어와의 상호작용도 한다. HUD는 게임의 계기판의 역할을 하며 정보를 보여주는데, 플레이어에게 점수, 생명력, 남은 시간 등 게임의 현재 상태를 알리는 역할을 한다. 유저 인터페이스와 달리 보통은 상호작용을 위한 요소는 아니다. 즉, 플레이어는 HUD를 클릭할 수 없다는 뜻으로, 정보를 알려주는 게임 인터페이스는 HUD로 설정해야 한다고 볼 수 있다. HUD는 GameMode에서 설정할 수 있다. 유저 인터페이스처럼, 플레이어 컨트롤러나 다른 ..

문제 풀이 유클리드 호제법 간단한 유클리드 호제법 문제이다. 아래는 a, b의 최대공약수를 반환하는 유클리드 호제법 함수이다. int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } 문제에서 주어진 분수를 먼저 통분하여 합을 계산한다. 합한 분자와 분모의 최대공약수를 구하여 각각에 나누면 기약 분수가 된다. 코드 #include using namespace std; int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % b; a = b; b..

문제 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 구현, 시뮬레이션 현재 order에서 움직일 기어들을 찾아서 방향에 맞게 회전시켜야 한다. 현재 order 기어의 오른쪽 기어들과 왼쪽 기어들을 나눠서 생각한다. // 현재 기어의 오른쪽 기어들 탐색 for (int current_gear = order_gear + 1; current_gear < 4; ++current_gear) { // 현재 기어와 현재 기어 바로 왼쪽 기어의 상태를 비교 if (gear[current_gear - 1][2] !=..

문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 구현, 시뮬레이션, 너비 우선 탐색 각 칸에 대해서 연합을 이룰 수 있는지 확인하기 위해, 각 칸의 상하좌우를 탐색하여 연합을 만든다. 연합은 시작 칸과 인접한 칸에서만 이루어지는게 아니라, 연합이 이루어진 칸에서도 인접한 칸을 비교하여 조건에 맞으면 연합이 이루어진다. 그러므로 각 칸을 bfs로 탐색하면서 연합을 이루는 칸이 어느 칸인지 탐색한다. 연합 벡터의 수가 2이상이라면, 인구 이동이 가능한 상태이므로 인구 이동을 실시한다. 이를..

문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 구현, 시뮬레이션 주사위의 각 면을 나눠서 생각하고, 현재 주사위의 아래쪽(D), 오른쪽(R), 앞쪽(F)에 해당하는 주사위 면을 설정하여 해결하였다. 각 면의 인덱스를 0, 1, 2, 3, 4, 5라고 하면 처음 상태에서 D는 0, R은 2, F는 4이다. 주사위를 4방향으로 움직이면 D, R, F는 밑의 코드처럼 변한다. // 주사위를 4방향으로 굴렸을 때, 아래, 오른쪽, 앞쪽의 주..

문제 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 구현, 브루트포스 알고리즘, 백트래킹 문제를 잘 읽어야 한다. 회전의 순서가 고정적인 것이 아니라, 배열의 최솟값을 구할 수 있도록 회전의 순서를 바꿀 수 있다. 회전의 순서를 정할 수 있도록, dfs를 이용하여 순열 알고리즘을 구현한다. // dfs를 이용한 순열 void dfs(bool select[], int map[], int cnt, int n, int k, vector v) { if (cnt == k) { sol..

문제 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 브루트포스 알고리즘, 너비 우선 탐색, 조합론, 백트래킹 학생은 전체 25명이다. 여기서 자리를 7개 선택하여 문제의 조건이 맞는지 확인하는 방식으로 답을 구한다. 학생의 수가 많지 않기 때문에 브루트포스로 구현해도 시간 초과는 발생하지 않는다. 자리를 선택하는 방법은 백트래킹을 사용한다. 자리 선택과 해제를 반복하며 자리를 7개 선택했다면 현재 상태가 문제의 조건을 만족하는지 확인한다. 문제의 조건은 다음과 같다. 선택한 자리 모두 상하좌우로 연결되어 ..

문제 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 풀이 수학, 다이나믹 프로그래밍, 조합론 격자상에서 각 칸에 도달할 수 있는 경로의 경우의 수는 다음과 같다. 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 0번 행과 0번 열은 모두 한가지의 방법만 존재한다. (x, y) 칸에 도달할 수 있는 경로의 수는 (x - 1, y) 칸과 (x, y - 1) 칸에 올 수 있는 경우의 수의 합이다. 중간 경로 K를 지나면서 마지막 칸에 도달하는 경우의 수는 (1번 칸에서..

문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 수학, 브루트포스 알고리즘, 조합론, 백트래킹 사전순으로 출력되어야 하므로 미리 입력받은 문자를 정렬시킨 후에 시작한다. 문자열의 길이는 최대 15로 모든 경우의 수를 탐색해도 시간 초과가 발생하지 않는다. 정렬된 문자열의 앞의 문자부터 선택과 선택해제를 반복하며, 선택된 문자열의 길이가 L이라면 정답 조건을 만족하는지 확인한다. 백트래킹으로 문자를 선택한다. void dfs(int index) { // 선택한 문자의 수가 L에 충족한다면 조건에 맞는지 검..