문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 DFS를 사용하는 방법으로 문제에 접근하였다. 보드의 문자 - 'A'가 0 ~ 25인점을 이용하여 26의 크기를 가진 방문 여부 배열을 만들어주었고 DFS를 돌리며 매 DFS마다 칸 수를 최댓값으로 초기화 시켜주었다. 이후 DFS가 끝나면 최댓값을 출력해주면 된다. 코드 #include #include using namespace std; int n, m; int result =..
문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 골드4 BFS 문제이다. 문제를 이해하고, 접근하는 것 자체는 쉬웠는데 메모리초과, 시간초과 때문에 좀 힘들었던 문제이다. 풀이 첫번째로 말처럼, 원숭이처럼 이동할 수 있는 방향 배열을 만들어주었다. 그리고 tuple을 통해 x, y좌표와 현재 말처럼 이동할 수 있는 횟수(능력)을 Queue에 담아주었다. 이후 (0,0,0)부터 BFS를 돌면된다. 하지만 어떻게 BFS를 돌릴..
문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 백트래킹을 통해 순열을 구하는 문제이다. 연산자 끼워넣기 문제를 풀어봤다면 쉽게 풀 수 있었을 것이다. 필자는 문자열 -> 숫자로 변환하여 대소관계를 비교하려 하였는데 이 부분에서 시간을 많이 잡아먹었다. 그렇게 레퍼런스를 찾아보던 중 문자열끼리 대소관계가 비교가 된다라는 것을 듣고 바로 해결할 수 있었다. 풀이 연산자는 연산자 배열을 따로 만들어주어 관리해주었고, 순열을 돌리며 check..
문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 삼성 코딩테스트 기출문제라고 한다. 백트래킹 문제인데 역시 삼성 문제답게 구현하기가 힘들었다. 다른 사람들 풀이를 안보고 풀려고 노력했더니 코드도 더러워지고 푸는데 2시간이나 걸렸다. 코드가 더러운만큼 다른 사람들의 풀이도 참고해보고 리팩토링할 생각이다. 풀이 첫번째로 4개의 연산자에 대해 입력을 받고 그 연산자들 전부를 (수열의 크기 ..
