코딩테스트 (66) 썸네일형 리스트형 [JAVA] 백준 11048 - 이동하기 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 🤔 문제 풀이 dp 문제 치곤 굉장히 쉬운 문제였다. 문제에서 이동할 수 있는 방향은 자기 자신을 기준으로 x+1 or y+1 or x+1, y+1 만 존재한다. 나는 먼저 map배열을 생성하여 좌표 별 사탕 개수 정보를 입력 받았고 dp 배열을 생성하여 현재 좌표에서 dp 배열 x-1, y and x, y-1 and x-1, y-1 좌표 값들의 최대 값을 구하고 현재 좌표에서 가져.. [JAVA] 백준 1238 - 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 🤔 문제 접근 처음 떠올린 풀이 방법은 N개의 마을에서 파티가 열리는 X번 마을까지의 최소 거리를 구하고 X번 마을에서 각각의 N개의 마을까지의 최소 거리를 구해 더한 뒤, 최소 값들 중 최대 값을 구하는 것이었다. A 마을에서 B마을까지의 최소 거리를 구하기 위해 최단 경로 탐색 알고리즘인 다익스트라 알고리즘을 사용했다. 하지만 위 풀이 방식으로 문제를 풀 경우 우.. [JAVA] 백준 9465 - 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 🤔 문제 접근 완전 탐색으로 풀려다가 실패한 문제이다. 스티커를 뗀 부분에서 맵을 벗어나지 않는 한도 안에 상하좌우에 있는 스티커가 같이 떼지는 형식이다. 이때 다음으로 고를 수 있는 스티커의 위치는 현재 뗀 위치의 행이 0인경우 sticker[1][i+1] or sticker[1][i+2] 이고 현재 뗀 위치의 행이 1인 경우엔 sticker[0][i+1] or sticker[0][i.. [JAVA] 백준 1932 - 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 🤔 문제 접근 전체 숫자들의 최대값 정보를 담는 2차원 배열 tree와 원래 숫자의 정보를 담는 2차원 배열 ori를 선언했다. tree.clone으로 ori도 생성을 간단하게 하면 되지 않을까 생각했지만 2차원 배열에 clone메서드를 사용하면 객체들을 담고 있는 주소의 주솟값데이터를 새로 생성해 복사하기 때문에, (2차원 배열에 clone을 사용하면 얉은 복사를 수행, 1차원 배열은 깊은 복사) tree [i][j]의 값이 바뀌면 ori [i][j] 의 값도 바뀌게.. [JAVA] 백준 2156 - 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 🤔문제 접근 DP 문제인 포도주 시식 문제이다. 문제를 딱 봤을 때, 이전에 풀었던 같은 DP문제인 계단 오르기 문제가 생각났다. 연속해서 3개의 와인을 고를 수 없는 것이나 각 와인을 골랐을 때의 최대 양을 구하는 것이 계단 문제와 같았다. 하지만 다른 점이 있다면, 바로 마지막 와인이 정해져 있지 않다는 것이다. 계단 문제 같은 경우 마지막 계단을 반드시 밟아야 했지만 해당 문제는 그런 것이 없.. [JAVA] 백준 1699 - 제곱수의 합 🤔문제 접근 처음에 점화식을 구하지 못하고 Math.sqrt(N) 을 한 값을 N에서 빼주고 answer+1 해주는 방식으로 단순 반복문으로 해결하려고 했다. 하지만 이 경우는 항의 최소를 구할 수 없는 방법이었다. 어떤 수 N은 N-1보다 작은 제곱수들 중 최소 제곱수들의 합 + 1이라는 규칙을 갖고 있다. 예를 들어 15는 (15-1) 의 최소 제곱수의 합 +1 (15-4) 의 최소 제곱수의 합 +1 (15-9) 의 최소 제곱수의 합 +1 이다. 문제에선 항이 최소일 때를 구하는 것이므로 이 중 최소 값을 구하면 된다. 🚨CODE import java.io.*; import java.util.*; public class Main { public static void main(String[] args).. [JAVA] 백준 6603 - 로또 🤔 문제 접근 dfs를 사용하는 조합 문제였다. 다만 숫자의 자리가 6자리로 고정되어있고 숫자의 구성이 사전 순으로 되어있음을 고려해야한다. 따라서 재귀 호출을 한 횟수가 6일 때 StringBuilder에 append 해주고 사전 순을 고려할 땐 이전에 고른 idx를 파라미터로 넘겨주어 해당 idx+1을 해주도록 했다. 다른 비슷한 문제들 같은 경우 boolean 타입의 visit 배열로 중복체크를 하지만 해당 문제는 어차피 이전에 고른 숫자 idx + 1을 골라주기 때문에 boolean으로 중복체크를 할 필요가 없었다. 🚨CODE import java.io.*; import java.util.*; public class Main { static StringBuilder sb = new StringBu.. [JAVA] 백준 1916 - 최소비용 구하기 🤔 문제 접근 다익스트라 알고리즘의 대표 문제인 최단 경로 문제와 매우 똑같은 문제이다. https://daneng4-codingstory.tistory.com/66 [JAVA] 백준 13549 - 최단 경로 다익스트라 알고리즘을 공부하며 대표 문제인 최단 경로 문제를 풀어보았다. BFS와 비슷한 느낌이 들었지만 각 노드의 가중치의 최소를 계속해서 갱신해주는 것이 새로웠다. 🤔 문제 접근 각 노 daneng4-codingstory.tistory.com 위 문제와 로직은 똑같고 도착 정류장의 최소 비용만 구해주면 된다. 다익스트라 알고리즘 문제를 풀 땐 항상 1. 갈 수 있고 방문하지 않은 노드 중 가중치(비용)가 최소인 노드부터 탐색한다 2. 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. 이 두.. 이전 1 2 3 4 5 6 7 8 9 다음
