문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 어떻게 풀 것인가? 처음에 문제를 이해하는 것이 많이 어려웠다. 주어진 문제에 따르면 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다..
문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 어떻게 풀 것인가? 문제를 처음 봤을 때 우선적으로 백트레킹을 이용한 순열과 조합을 떠올렸다. 하지만 중요한 한 부분을 놓쳐서 계속 문제를 틀렸는데, 이는 문제에서 "암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다." 라는 부분을 놓쳤다. 이에 그래서 모음의 갯수를 카운트하는 로직을 구성하여 문..
문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 어떻게 풀 것인가? DFS를 이용한 탐색을 사용하였다. 추후에 포스팅을 통해서 설명할테지만, 범위가 크다면 StackOverFlow를 피하기 위해서 재귀보다는 Stack을 이용한 DFS 방식을 사용하는 것을 선호한다. DFS를 이용하여 음식물 쓰레기의 영역 범위를 구하고 가장 큰 값을 반환하면 된다. 이는 코드를 통해서 보는 것이 훨씬 쉽다. 풀면서 ..
문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 어떻게 풀 것인가? BFS나 DFS를 이용한다면 간단하게 문제를 풀 수 있다. 탐색을 통해서 영역의 갯수를 구하고 그러한 수를 리스트에 넣어서 답을 도출하면 된다. 딱히 풀이 할 게 없지만, 몇몇 실수는 있었다. 변수의 갯수가 늘어서 간단한 것들을 놓쳤다. 풀면서 놓쳤던점 변수의 양이 늘어나면 실수를 한다는 점을 발견했다. 항상 꼼꼼하게 보자. 이 문제를 통해 얻어갈 것 ..
문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 어떻게 풀 것인가? Stack을 이용한 DFS를 활용하여 문제를 풀어야한다. DFS를 통해서 접근한 영역의 갯수와 영역의 넓이를 구한다면 아주아주 쉽게 문제를 풀 수 있다. 풀면서 놓쳤던점 DFS에서는 2가지의 방식으로 문제를 풀 수 있다. 바로 재귀와 Stack을 활용한 방법이다. 다만, 재귀를 통해서 문제를 푼다면 StackOverFlow가 발생한다. 이러한 부분을 처음에 놓쳐서 문제를 다시 ..
문제 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 어떻게 풀 것인가? 우선적으로 DP에 대한 풀이를 떠올렸다. 하지만 DP 즉 점화식으로 풀려고하니 좀 머리가 아프고 직관적이지 못하다는 생각이 들었다. 그래서 HashMap을 이용한 메모제이션 기법을 이용하기로 생각했다. 문제에서 주어진 재귀함수는 중복 계산이 많이 발생하므로, 메모이제이션(Memoization)을 사용하여 중복 계산을 피할 수 있다. 메모이제이션은 한 번 계산한 값을 저장해두고..
문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 어떻게 풀 것인가? 수학적인 요건이 필요한가? 싶어서 처음에는 당황스러웠다. 하지만 전형적인 DP스러운 문제였다. 자 우리가 원하는건 제곱수 항의 최소 개수이다. 그렇다면 주어진 N의 제곱수 최대 크기의 제곱근까지 번복해서 비교하여 작은 값을 넣는 것을 반복하면 되지 않을까? 말로는 어렵지만, 코드로 보면 단박에 이해가 될 것이다. 풀면서 놓쳤던점 DP..
