Ikjo's Technology blog

문제 설명 25331번: Drop 7 Drop7은 7×7 크기의 격자에서 진행하는 싱글 플레이어 게임이다. 처음에는 격자가 비어있고, 플레이어는 매 턴마다 1 이상 7 이하의 정수 하나가 적힌 공을 받아 7개의 열 중 한 곳에 떨어뜨려야 한 www.acmicpc.net 접근 방법 해당 문제는 원티드 주관 코딩테스트 대회 2022년 2회차 문제로서 당시 시간적 여유가 있었음에도 불구하고 문제 해결을 위한 아이디어가 떠오르지 않아 제대로 접근조차 하지 못했었던 문제였습니다. 그래서 아쉬운 마음에 코딩테스트 이후에 따로 시간을 내서 재도전 해보았습니다. 우선 문제를 해결하기 위해 접근했었던 방법을 단계별로 나타내면 다음과 같습니다. 1. 각 열별로 공 떨어트리기 - 떨어뜨린 공은 이미 배치되어 있는 공 바로 ..

문제 설명 25330번: SHOW ME THE DUNGEON 올 여름 출시된 RPG 게임 "SHOW ME THE DUNGEON"은 주인공 시루가 몬스터에게 침략당한 마을을 구하는 내용의 게임이다. 배경이 되는 나라는 $0, 1, 2, \cdots, N$번의 번호가 붙어있는 $N+1$개의 마을로 이루 www.acmicpc.net 접근 방법 해당 문제에서는 캐릭터(시루)의 체력과 마을별 몬스터의 공격력과 주민의 수가 주어졌을 때 시루가 해방시킬 수 있는 주민들의 최대 수를 요구하고 있습니다. 접근 방법 1 : 순열 - 시간 초과 처음 이 문제에 접근했었던 방식은 시루가 각각의 던전들을 순서를 고려하면서 방문하는 모든 경우의 수(순열)를 구함으로써 해방시킬 수 있는 주민들의 최대 수를 구하는 것이었습니다. (..

문제 설명 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 회고 해당 문제는 BFS를 이용하여 풀이할 수 있었는데, 익은 토마토를 기점으로 익지 않은 토마토들이 점차 확산되어가며 익어간다는 점 그리고 익는데 며칠이 걸리는지를 구해야 한다는 점에서 BFS를 떠올릴 수 있었습니다. 이때 DFS를 사용하지 않았던 이유는 익은 토마토들이 여러 개 있을 때 익은 토마토들을 기점으로 동시 다발적으로 익지 않은 토마토들로 확산되어 갈텐데 DFS는 우선적으로 하나의 익은 토마토를 기점으로 확산시..

문제 설명 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 회고 제가 해당 문제를 풀기 위한 접근 방법은 다음과 같았습니다. 주어진 2차원 배열에 대해 임의의 3개의 벽 세우기 바이러스 확산시키기 안전 영역 크기 구하기(기존 값과 대소 비교 후 더 큰 값 할당) 변경된 2차원 배열 초기화하기 1번으로 돌아가 다시 임의의 3개의 벽 세우기(기존 3개의 벽과 완전히 중복되지 않는 3개의 벽) 위 단계에서 제가 가장 구현하기 까다로웠던 부분은 "임의의 3개의 벽을 세우는 것"이었습니다. 사실 DFS나 BFS를 통해 임의의 ..