[IT] 코딩테스트/[문제 및 풀이] 백준 썸네일형 리스트형 [백준] 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.. 더보기 [백준] 1600 말이 되고픈 원숭이 / 자바(Java) 문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 해설 원숭이가 2차원 판을 시작지점에서 도착지점까지 이동하는 최소 횟수를 구하는 문제입니다. 최소횟수를 얻으며 각 계산이 독립적이므로 완전탐색이 필요하므로 해결방법으로 BFS가 떠오릅니다. 여기서 K번만 가능한 체스의 나이트처럼 뛰는 횟수가 문제가 됩니다. 특정 위치의 방문 여부가 K가 남아있는가에 따라 다음 이동 가능 여부가 달라지기 때문에 이를 해결하기 위해서 dp배열을 .. 더보기 [백준] 1753 최단경로 / 자바(Java) 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해설 방향그래프에 맞추어 다익스트라 알고리즘을 이용해 해결한 문제입니다. 다익스트라는 최단경로 탐색 알고리즘으로 음의 간선이 없는 경우에 사용할 수 있는 문제입니다. DP문제로도 볼 수 있는 이유로 정점에서 다른 정점으로 가는 최단 경로는 다른 최단 경로들로 이루어져 있어 이전의 최단 경로들로 다른 최단경로들을 얻어낼 수 있습니다. 문제에서는 방향 그래프.. 더보기 [백준] 1937 욕심쟁이 판다 / 자바(Java) 문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 해설 판다가 돌아다닐 수 있는 가장 많은 칸을 찾는 문제입니다. 출발점이 정해져 있지 않으니 모든 점을 출발점으로 경로를 확인해야 합니다. 지나온 값의 총 합의 기반으로 경로를 정하지 않기 때문에 2차원 dp배열을 통해 연산량을 줄입니다. dp[i][j]는 (i,j) 위치를 지날 때 가장 많이 이동한 횟수 dfs를 통해 지도의 모든 위치에서 주변 4방을 탐색 후 자신보다 큰 위치(.. 더보기 [백준] 6198 옥상 정원 꾸미기 / 자바(Java) 문제 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 해설 각 빌딩별 오른쪽에 있는 자신보다 크거나 같은 빌딩과의 사이에 있는 빌딩의 수들의 합을 구하는 문제입니다. 각 빌딩별로 오른쪽을 탐색하면 확인하는 과정을 거친다면 O(n^2)의 시간복잡도를 가져 시간초과가 날 수 있습니다. 발상의 전환으로 각 빌딩별 자신을 볼 수 있는 빌딩의 수를 구한다면? 각 빌딩기준 왼쪽에 자신보다 큰 빌딩의 수를 구한다면 O(n)으로 해결이 가능하다 생각되.. 더보기 [백준] 4485 녹색 옷 입은 애가 젤다지? / 자바(Java) 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 해설 입구에서 출구까지의 모든 경로의 가장 낮은 숫자의 합을 구하는 문제입니다. 각 위치별 경로의 최소합을 얻기위해 dp 지도를 만듭니다. dp[i][j] 는 (i,j)위치까지 가는 경로의 최소합을 의미합니다. BFS를 통해 4방탐색으로 다음 위치는 이전 위치 + 진입 숫자보다 작은 경우 갱신하며 새로 큐에 넣는 방식을 통해 dp에 항상 최소값을 갱신할 수 있도록 구현했습니.. 더보기 [백준] 3109 빵집 / 자바(Java) 문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 해설 주어진 2차원 배열에서 1열과 마지막 열을 잇는 줄을 겹치지 않고 얼마나 많이 만들 수 있는가에 대한 문제입니다. 가장 많은 줄을 만들기 위해서 가장 위의 행부터 시작해 가능한 한 위쪽으로 줄을 만드는게 효율적이라 판단하는 그리디 방식을 통해 해결합니다. DFS를 통해 가장 위쪽을 통해 넘어가는 줄을 만들고 진행 여부를 2차원 배열에 표시해 해당 위치로 중복해서 넘어가지 않도록 지정해줍니다. 또한 중간.. 더보기 [백준] 3190 뱀 / 자바(Java) 문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 해설 2차원 배열에서의 구현을 4방탐색을 통해 해결하는 문제입니다. 조건들을 주의해서 확인해야합니다. 뱀의 회전 시간 및 여부는 입력이 정렬된 상태로 주어져 올바른 시간에 맞추어 진행하다 한번씩 꺽어주면 됩니다. 새로 진행할 부분의 위치를 head배열에 저장하고 진행시 사과가 없어 꼬리가 당겨져 몸이 지워질 부분을 tail배열에 저장합니다. head의 값은 회전 및 전진하며 자신이나 벽과 닿은 경우.. 더보기 이전 1 2 3 4 다음
