알고리즘 문제 풀이

[ 풀이 방법 ]1. 물고기의 수가 가장 적은 어항에 물고기 한 마리를 넣는 기능  - min_element()를 이용해 최소값 찾고, 최소값이 저장된 어항(board)의 물고기의 수를 1씩 증가시킨다. 2. 어항 쌓기 기능  - 시작 좌표(initX, initY)와 목표 좌표(targetX, targetY)를 설정하고 시작 좌표의 값을 목표 좌표로 옮겨 구현한다.      - 시작 좌표는 (N-1, 0), 목표 좌표는 (N - 2, initY + 1)에서 시작한다.      - 이후, 시작 좌표의 y좌표는 (이전 반복에서 값이 실제로 옮겨진 targetY의 최대값), 목표좌표의 y좌표는 (initY+반복 횟수)에서 시작한다.      - 2중 loop를 이용해 시작 좌표와 목표 좌표의 위치를 이동하며 ..

[ 풀이 방법 ] 1. 복제 마법 시전 기능 - AUX 배열(aux)에 현재 배열(board)에 저장된 물고기와 방향을 저장한다. 2. 물고기 이동 기능 - 물고기 구조체를 별도의 배열에 저장해둔 뒤 순회하며 물고기 이동을 구현 - 물고기 구조체(x, y 좌표와 방향, 상어에게 먹혔는지 여부 저장) - 물고기 구조체 배열(fish)과 물고기 위치를 저장한 2차원 배열(board) 모두에 물고기 이동 결과를 갱신. - 상어에게 이미 먹힌 물고기는 스킵한다. - 물고기의 방향으로 한 칸 이동 - 이동해야 할 위치가 board의 범위를 벗어나거나, 상어가 있거나, 물고기 냄새가 남아았는 경우 물고기 이동 불가 - 물고기 이동 불가한 경우, 물고기가 이동 가능할 때까지 45도 반시계 방향으로 물고기 방향 회전 ..

[ 풀이 방법 ] 1. 온풍기 방향으로 바람을 내보내는 기능 - 온풍기 위치에서 온풍기 방향으로 한 칸 이동한 칸부터 BFS 시작 - 온풍기 방향에 따라 벽의 위치 확인하여 탐색 가능한 칸만 탐색 (벽에 막히거나, 보드의 범위 벗어나거나, 이미 탐색했거나, 첫 탐색 위치로부터 5칸 이상 떨어진 경우 탐색 X) - 상, 하: 해당 칸과 해당 칸의 좌, 우로 한 칸 이동한 후의 칸에서 온풍기 방향으로 한 칸 이동하는 경우 탐색 - 좌, 우: 해당 칸과 해당 칸의 상, 하로 한 칸 이동한 후의 칸에서 온풍기 방향으로 한 칸 이동하는 경우 탐색 - 이미 탐색한 칸은 탐색하지 않기 위해 visited 배열 사용 - 첫 탐색 위치의 칸은 5(=k), 이후로는 --k 씩 해당 칸의 온도 증가 2. 온도 조절 기능 -..

조건을 만족하는 (i, j, k)를 찾기 위해 3중 loop를 돌린다면 O(n3)의 시간복잡도를 가지므로 시간 제한을 초과할 것이다. 따라서 DP를 이용해 (i < j, ai < aj)를 만족하는 i, j와 (i < k, ai < ak)를 만족하는 i, k를 따로 구하여 O(n2) 시간복잡도로 문제를 해결할 수 있다. [ 풀이 방법 ] 1. i를 선택하고, i < j와 ai < aj를 모두 만족하는 j의 개수를 구하는 기능 - loop를 돌며 dp[i][j]에 ai보다 큰 aj의 개수 저장 2. i를 선택하고 i < k와 ai < ak를 모두 만족하는 k를 구하여 결과를 구하는 기능 - loop를 돌며 ai와 ak를 비교하고 ak가 더 작다면 res에 dp[i][k-1](i와 k사이의 모든 조건을 만족..

성능이 가장 낮은 컴퓨터의 성능이 가질 수 있는 최대값 즉, 최적해를 구하는 문제이다. 따라서 decision problem의 형태를 가지며 이진 탐색을 사용해 풀 수 있다. [ 풀이 방법 ]  이진 탐색을 이용하여 성능이 가장 낮은 컴퓨터의 성능이 mid가 되도록 하는데 드는 비용의 합이 B보다 작은 경우 중 가장 큰 mid값을 찾는다. 이 때, B원의 값이 이미 매우 크므로 비용의 합을 구할 때, 비용의 합이 B보다 커지면 비용의 합을 구하는 프로세스가 바로 종료되도록 구현해야 한다.  [ 회고 ] 이진 탐색, 특히 decision problem에 대한 이해가 부족하여 풀이 방법과 구현 방법 생각이 어려웠다. 또한 B가 큰 값임을 알고 있었으나 자료형의 범위에 대한 생각없이, 아무리 큰 값이어도 lo..

[ 풀이 방법 ] 1. 주사위의 다음 이동 방향을 정하는 기능 - 처음엔 동쪽 방향으로 이동 - 이후로는 주사위 아랫면의 정수(A)와 보드의 해당 칸의 정수(B)를 비교하여 이동 방향을 결정한다. - A > B: 현재 방향에서 90도 시계 방향으로 회전한다. - A < B: 현재 방향에서 90도 반시계 방향으로 회전한다. - A = B: 현재 방향 그대로, 만약 다음 이동 시 보드 칸을 벗어난다면 이동 방향을 반대로 한다. - 주사위 구조체에 다음 이동 방향과 현재 위치를 저장하여 구현한다. 2. 주사위 이동 기능 - 1에서 정한 이동 방향으로 주사위를 한 칸 이동하는 기능 - 주사위의 위치 이동 + 주사위를 이동 방향으로 굴림 - 주사위 구조체에 위, 아래, 왼쪽, 오른쪽, 앞, 뒤에 적힌 정수를 저장..

각 단계에서 최선의 선택을 하여 문제를 풀 수 있는 그리디 문제이다. 그리디 문제라고 생각은 하였으나 각 단계에서 최선의 선택이 무엇인지, 어떻게 구현할 수 있을지 생각하지 못해 풀 지 못한 문제였다. [ 풀이 방법 ] 처음에 가지고 있는 카드와 현재 라운드까지 뽑았던 카드를 각각 저장하고,1. 동전을 사용하지 않고 다음 라운드로 진행할 수 있는 경우  - 처음에 가지고 있는 n/3 장의 카드 중 2장을 사용하여 카드에 적힌 수의 합이 n+1이 되도록 만들 수 있는 경우2. 동전을 1개만 사용하여 다음 라운드로 진행할 수 있는 경우  - 처음에 가지고 있는 n/3 장의 카드 중 1장과 현재 라운드까지 뽑았던 카드 중 1장을 사용하여 카드에 적힌 수의 합이 n+1이 되도록 만들 수 있는 경우3. 동전을 2..

A가 먼저 n / 2개의 주사위를 가져가고, B가 남은 n / 2개의 주사위를 가져가는 경우의 수는 최대 10C5=252이고, A와 B가 가져간 주사위를 모두 굴려서 나오는 결과의 합을 구하는 경우의 수는 최대 65, 약 7700이다. 따라서, 완전 탐색을 이용해 A와 B가 주사위를 n / 2개 씩 가져가는 모든 경우에 대해 A와 B가 각각 가져간 주사위를 굴려서 나오는 모든 결과의 합을 구한 뒤 서로 비교하여 A가 승리하는 횟수가 가장 많은 경우를 찾아 문제를 해결할 수 있다. (252 x 7700은 약 200000) [ 문제 풀이 ] 1. 가져갈 주사위를 고르는 기능 - 완전 탐색을 이용해 A가 먼저 n / 2개의 주사위를 가져가고, B가 남은 n / 2개의 주사위를 가져가는 경우를 모두 탐색한다. ..