https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net DFS 문제다. BFS를 풀려고 BFS 문제집에서 찾은 문젠데 DFS여서 뻘짓했다^!^ 알파벳을 지나가면서 같은 알파벳을 또 밟을 수는 없는 문제이므로 방문 배열을 해당 알파벳을 밟았는지 확인하는데 사용했다. 고로 방문 배열은 26칸으로 선언했다. #include #include using namespace std; // 상하좌우 탐색을 위함 int dr[4] = { -1, 0, 1, 0 ..
골드
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리와 DFS 문제다. 입력으로 받은 부모 노드의 정보를 이용해 루트 노드의 번호를 저장한다. -1 이외의 값이 들어오면 부모와 자식의 노드를 저장하는데 부모는 유일하기 때문에 부모 노드를 인덱스로 이용했다. 지울 노드의 번호를 입력 받고 지울 노드가 루트 노트라면 0을 출력 후 바로 종료한다. 단말 노드의 개수를 카운트 하기 위해서는 DFS를 이용한다. 방문 검사 후 단말 노드거나, 자식 ..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디 문제다. 수의 곱과 합으로 최대값을 찾는 문제이므로 정렬을 먼저 했다. 처음에는 정렬 후 큰 수부터 곱과 합의 크기를 비교하고 큰 쪽으로 결과 값에 더해주는 방식으로 했다. 이 때 곱이 크면 인덱스를 하나 더 줄여주고, 합이 크면 현재 인덱스의 값만 더한다. (쓰다보니 필요 없는 부분인가 싶다) 간과한 점은 음수도 들어올 수 있다는 점이다. 음수의 경우 작은 음수끼리 곱할 수록 값이 커진..
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 이분 탐색과 두 포인터 문제다. 입력 받은 용액들의 특성값을 정렬한 후 양 사이드에서부터 합을 계산한다. 0과 가장 가까운 합을 찾는 것이기 때문에 합의 절댓값이 가장 작은 경우를 찾으면 된다. 두 용액의 합이 음수면 더 큰 용액들을 더한다. 즉, 왼쪽의 포인터를 오른쪽으로 한 칸 옯긴다. 두 용액의 합이 양수면 더 작은 용액들을 더한다. 즉, 오른쪽의 포인터를 ..
https://www.acmicpc.net/problem/20925 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net DP 문제다. 시작점을 입력에 맞춰 체크해줘야 한다. dp 배열은 시간과 위치로 설정했다. dp 배열을 순회하면서 현재 경험치가 0인 곳은 스킵했다. dp의 칸마다 움직일 수 있는 사냥터를 탐색하여 방학이 지나거나 경험치가 모자라는 경우를 제외했다. 이동하는 경우가 아닌 제자리에 머물러 있는 경우는 따로 고려를 했다. #includ..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 문제다. https://abbiddo.tistory.com/12 불!과 비슷한 문제다. 같은 상황에 출구가 정해져 있고, 돌이 있다는 점에서만 차이가 있기 때문에 설명은 생략 #include #include using namespace std; int n, m; char board[50][50]; bool gisit[50][50];// 고슴도치의 방문 체크 bool wisit[50][50];// 물의 ..
