Dino Rudy

치즈 2636번 solved.ac 골드 5 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제 해석 및 풀이 이 문제는 공기 중에 노출된 치즈가 몇 시간 뒤에 완전히 녹는지와 완전히 녹기 직전 단계에서 몇 개의 치즈가 남았는지를 구하는 문제입니다. 문제의 조건에서 가장 테두리 부분은 치즈가 놓여있지 않고 공기가 있는 부분입니다. 이 문제에서는 시간마다 없어지는 치즈를 구해 그 치즈를 없애야 합니다. 이 문제를 접근하기 위해서는 공기에 노출된 치즈를 알아야 하는데..

평범한 배낭 12865번 solved.ac 골드 5 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 해석 및 풀이 이 문제는 zero-one knapsack 문제로 knapsack문제는 Dynamic Programming 알고리즘을 배울 때 대표적으로 등장하는 문제입니다. knapsack문제는 배낭에 주어진 무게를 넘지 않는 선에서 최대의 만족도를 갖는 문제를 구하는 문제인..

말이 되고픈 원숭이 1600번 solved.ac 골드 4 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 해석 및 풀이 이번 문제는 원숭이가 0,0에서 출발해 오른쪽 맨 아래인 H-1, W-1로 이동할 때 걸리는 최소 이동 횟수를 구하는 문제입니다. 보통의 쉬운 bfs문제는 상하좌우 이동을 하며 최단경로를 찾는 문제인데 하지만 이 문제는 벽 부수고 이동하기 문제처럼 특수한 이동을 합니다. 바로 k번 이하로 말처럼 (체스의 ..

트리순회 1991번 solved.ac 실버 1 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 해석 및 풀이 이진트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력해야 하는 문제입니다. 이진트리는 최대 차수가 2로 하나의 노드는 최대 2개의 자식노드를 가지는 트리입니다. 문제의 예시에서 순회에 대한 힌트가 있습니다. 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 ..

아기 상어 16236번 solved.ac 골드 4 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 해석 및 풀이 이번 문제는 아기 상어라는 귀여운 제목의 문제입니다. 아기 상어 문제는 삼성 SW 역량테스트 기출문제로 백준에서 SW 역량테스트 기출문제집을 보면 확인하실 수 있습니다. 아기 상어의 초기 몸집은 2로 자신보다 작은 물고기만 먹을 수 있으며 자기와 몸집이 같거나 작은 물고기가 있는 곳은 지나갈 수 있으며 자신보다 몸집이 큰..

빵집 3109번 solved.ac 골드 2 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 문제 해석 및 풀이 빵집 문제는 원웅이가 가스관과 자신의 빵집을 연결할 수 있는 파이프라인의 최대 개수를 구하는 문제입니다. 왼쪽 첫 번째 열에는 가스관이 있고 가장 오른쪽 열에는 원웅이의 빵집이 있습니다. 이 문제에서 중요한 점은 파이프라인은 겹칠 수 없고, 최대로 연결할 수 있는 파이프 라인을 구해야 합니다. 첫 번째 열에서 각 행마다 파이프를 연결할 수 있으며 중간..

알파벳 1987번 solved.ac 골드 4 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 해석 및 풀이 알파벳 문제는 가장 왼쪽 위에서 출발하는 말이 상하좌우로 이동하여 지날 수 있는 최대 칸 수를 구해야 하는 문제입니다. 주어진 조건으로는 한번 지난 알파벳을 지날 수 없는 조건이 있습니다. 현재 주어진 입력의 제한은 1== 0 && rr = 0 && cc < C && !cantGo[map[rr][cc] - ..

Z_1074 solved.ac 실버 1 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 문제 해석 및 풀이 Z 문제는 2차원 배열이 주어졌을 때 Z탐색을 진행하고 탐색을 진행할 때 주어진 r 행과 c열을 몇 번째로 방문하느냐를 구하는 문제입니다. Z탐색을 구현하려고 하면 구현할 수 있겠지만 행과 열의 크기는 최대 2^15으로 32768입니다. 이렇게 되면 2차원 배열의 최대 크기는 32768*32768로 1073741824 약 10억을 ..

연구소 14502번 solved.ac 골드 5 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해석 및 풀이 이번 문제는 연구소에 있는 바이러스가 퍼지는 것을 최대한 방지하기 위해 3개의 벽을 추가로 세워 확보할 수 있는 최대의 안전구역의 수를 구해야 합니다. 이 문제는 딱 3개의 벽을 세워야 한다고 명시되어있습니다. 벽의 위치가 같다면 순서는 중요하지 않음으로 바이러스(2)와 벽(1)이 있는 곳을 제외한 곳 중 3곳을 뽑아 벽을 설치하고 BFS 탐색..