재귀 썸네일형 리스트형 [백준] 1987 알파벳 / 자바(Java) 문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 해설 2차원배열에서 4방탐색을 통해 가장 많이 가는 횟수 찾기 문제입니다. 특이한 점은 다른 문제처럼 숫자가 아닌 알파벳으로 2차원 배열이 구성되어있고, 특정 위치의 방문여부가 아닌 특정 알파벳을 방문했는가에 따라 추가탐색의 가능 여부가 갈립니다. 문자열이 아닌 알파벳의 방문여부이기 때문에 map을 사용하지 않고 26까지 있는 1차원 배열을 통해 index 0의 값은 A, ind.. 더보기 [백준] 3109 빵집 / 자바(Java) 문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 해설 주어진 2차원 배열에서 1열과 마지막 열을 잇는 줄을 겹치지 않고 얼마나 많이 만들 수 있는가에 대한 문제입니다. 가장 많은 줄을 만들기 위해서 가장 위의 행부터 시작해 가능한 한 위쪽으로 줄을 만드는게 효율적이라 판단하는 그리디 방식을 통해 해결합니다. DFS를 통해 가장 위쪽을 통해 넘어가는 줄을 만들고 진행 여부를 2차원 배열에 표시해 해당 위치로 중복해서 넘어가지 않도록 지정해줍니다. 또한 중간.. 더보기 [백준] 2565 전깃줄 / 자바(Java) 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 해설 어느 전기줄들을 제거해야 교차되는 전기줄이 없을까 확인하는 문제입니다. 풀이방식을 어떻게 잡을지 몰라 고민했지만 DP를 사용해 해결하였습니다. DP배열의 의미는 dp[i] => i번째 까지에서 교차되지 않으려면 설치하는 최소 전기줄 수 로 하였습니다. 제거가 아닌 설치를 기준으로 생각해서 좀 더 문제를 해석하기 쉽도록 되었습니다. 같은 위치에는 2개이상의 전기줄이 연결될 수 없으므로 입력 값을.. 더보기 [백준] 1074 Z / 자바(Java) 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 해설 Z형태가 반복되는 형상에 재귀 및 분할정복이 필요하다 생각들었습니다. findz 함수를 통해 각 단계별로 r,c가 어느 사분면에 존재하는지를 구하고 그 단계의 사각형의 크기를 통해 그 사분면의 첫 숫자의 크기만큼 더해주어 마지막으로 사각형의 크기가 1인 경우에는 해당 사각형의 탐색 순서를 구할 수 있도록 하였습니다. 주의점 각 사분면단위로 계산하기 때문에 범위를 잘 판단해야한다.. 더보기 이전 1 다음
