코딩테스트 썸네일형 리스트형 [백준] 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의 값은 회전 및 전진하며 자신이나 벽과 닿은 경우.. 더보기 [백준] 2589 보물섬 / 자바(Java) 문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 해설 BFS를 사용하면 될 듯한 문제입니다. 단 문제의 조건에서 최단거리 중 가장 먼 곳의 거리를 구해야합니다. 다행히 각 섬별로가 아닌 단 한 가지 경우만 찾으면 되므로 2차원 배열에 지도 정보를 넣고 각 땅 별로 BFS를 통해 갈 수 있는 최대 거리를 구해 각각을 비교하는 방식으로 해결할 수 있는 BFS의 기본을 익힐 수 있는 문제였습니다. 코드 import java.io.BufferedRe.. 더보기 [백준] 2565 전깃줄 / 자바(Java) 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 해설 어느 전기줄들을 제거해야 교차되는 전기줄이 없을까 확인하는 문제입니다. 풀이방식을 어떻게 잡을지 몰라 고민했지만 DP를 사용해 해결하였습니다. DP배열의 의미는 dp[i] => i번째 까지에서 교차되지 않으려면 설치하는 최소 전기줄 수 로 하였습니다. 제거가 아닌 설치를 기준으로 생각해서 좀 더 문제를 해석하기 쉽도록 되었습니다. 같은 위치에는 2개이상의 전기줄이 연결될 수 없으므로 입력 값을.. 더보기 이전 1 2 3 4 5 6 ··· 9 다음
