본문 바로가기

알고리즘 문제87

[백준] 9655번: 돌 게임 (Java) 1. 문제설명돌 게임은 탁자 위에 돌 N개가 있을 때 상근이와 창영이가 턴을 번갈아가면서 돌을 1개 또는 3개 가져가고, 마지막 돌을 가져가는 사람이 이기는 게임이다. 게임은 상근이가 먼저 시작하고, 이기는 사람을 구하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식REF) https://propercoding.tistory.com/21문제에서 “두 사람이 완벽하게 게임을 했을 때”가 조건이기 때문에 최적의 전략을 사용해야 한다.N=1: 상근이가 돌 1개를 가져가므로 상근이의 승리N=2: 상근이가 1개를 가져가면 창영이가 남은 1개를 가져가므로 창영이의 승리N=3: 상근이가 3개를 가져가므로 상근이의 승리N=4: 상근이가 1개 또는 3개를 가져가면 창영이가 3개 또는 1개를 가져가므로.. 2024. 8. 27.
[백준] 9095번: 1,2,3 더하기 (Java) 1. 문제설명정수 n이 주어졌을 때, n을 1, 2, 3의 조합으로 나타내는 방법의 수를 구하는 문제이다.시간 제한: 1초메모리 제한: 512MB 2. 접근 방식DP 방법을 사용한다.dp[i] 는 i를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 저장한다.dp[i] 는 dp[i-1], dp[i-2],dp[i-3] 의 합으로 계산한다. 3. 올바른 접근 방식 및 해결 방식https://lotuslee.tistory.com/43 4. 최종 코드import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(.. 2024. 8. 26.
[백준] 1010번: 다리 놓기 (Java) 1. 문제설명도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강의 흐르고 있다. 다리를 짓기로 하고, 짓기에 적합한 곳(사이트)이 서쪽에 N개, 동쪽에는 M개가 있다.(N≤M) 한 사이트에는 최대 한 개의 다리만 연결될 수 있고, 다리를 최대한 많이 짓기 위해 서쪽의 사이트 개수만큼(N개) 다리를 지으려고 한다.다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 문제이다.시간 제한: 0.5초메모리 제한: 128MB 2. 접근 방식조합의 개념을 사용한다.$_nC_r$ : 서로 다른 n개의 원소에서 r(단, $0$_nC_r = {_{n-1}C_{r-1}} + {_{n- 1}C_{r}}$`int dp[][]` 배열을 사용하여 조합의 값을 저장한다.DP의 Top-Down .. 2024. 8. 26.
[백준] 2748번: 피보나치 수 2 (Java) 1. 문제설명0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 2번째 부터는 다음 점화식을 만족한다.F(n) = F(n-1) + F(n-2)   (n ≥ 2) n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다. 시간 제한: 1초메모리 제한: 128MB 2. 접근 방식DP - Bottom-Up 방식0, 1번째 피보나치 수를 먼저 계산하고 배열에 저장한다.반복문을 통해 2~n번째 피보나치 수를 순차적으로 계산하고 저장한다.배열의 n번째 값을 반환한다.DP - Top-Down 방식재귀 호출을 통해 n-1, n-2번째 피보나치 수를 계산하고, 두 값을 더해 배열[n]에 저장한다.배열의 n번째 값을 반환한다. 3. 틀린 이유피보나치 수를 저장하는 배열의 타입을 int로 선언했다.예를 들어 n이 .. 2024. 8. 26.
[백준] 1743번: 음식물 피하기 (Java) 1. 문제설명음식물이 통로 중간 중간에 떨어져 있고, 음식물은 근처(상하좌우)에 있는 것끼리 뭉치게 되어 큰 음식물 쓰레기가 된다. 떨어진 음식물 중에 제일 큰 음식물의 크기를 구하는 문제이다.시간 제한: 2초메모리 제한: 128MB 2. 접근 방식음식물 쓰레기가 있는 위치를 load배열에 저장한다. 음식물이 있는 곳을 1로 저장한다.(0, 0) 위치부터 통로를 BFS 탐색한다.큐를 사용해 인접한 상하좌우를 탐색하여 연결된 음식물의 크기를 계산한다.BFS를 통해 구한 음식물의 크기(trashSize)를 maxTrashSize와 비교하여 최댓값을 갱신한다.  3. 최종 코드import java.io.*;import java.util.*;public class Main { static int n, m;.. 2024. 8. 25.
[백준] 1991번: 트리 순회 (Java) 1. 문제설명이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 문제이다.시간 제한: 2초메모리 제한: 128MB 2. 접근 방식루트 노드를 ‘A’로 설정하고, 이진 트리의 노드 정보를 입력받는다.노드 삽입각 노드에 대해 부모 노드와 자식 노드 정보를 입력받고, 해당 부모 노드를 트리에서 찾아서 왼쪽과 오른쪽 자식 노드로 연결한다.자식이 존재하지 않으면, 자식 노드를 null로 설정한다.재귀적으로 호출하여 트리의 모든 노드를 연결한다.전위 순회: 루트 노드부터 시작하여, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 방문한다.중위 순회: 왼쪽 자식 노드를 먼저 방문한 후, 루트 노드를 방문하고, 마지막으로 오른쪽 자식 노드를 방문한다.후위 순회: 왼쪽 자식 노드, 오른쪽 자식 노드를 .. 2024. 8. 25.
[백준] 16954번: 움직이는 미로 탐색 (Java) 1. 문제설명크기가 8x8인 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 체스판 가장 왼쪽 아래 칸에서 가장 오른쪽 윗 칸으로 이동하는 게임을 진행한다. 이 게임에서 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 아래에 행이 없다면 벽이 사라진다. 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 1초 동안 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.캐릭터가 목표 지점까지 이동할 수 있는지 없는지 구하는 문제이다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식캐릭터를 (7, 0) 위치에서 출발시킨다. BFS 수행.캐릭터가 이동할 수 있는 위치(상하좌우, 대각.. 2024. 8. 24.
반응형