매일 조금씩

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 7 7 3 10 8 15 8 18 1 16 0 15 2 20 7 25 4 20 4 19 4 24 5 30 2 27 6 26 5 24 2차 배열에 최대값을 저장하면서 더해나간다. 첫번째 값 dp[i][j] = num + dp[i-1][j]; 마지막 값 dp[i][j] = num + dp[i-1][j-1]; 나머지 값 dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]); 마지막 행의 최대값을 구한다. N이 1일 경우 for문 내에서..

문제 https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 N: 200,000,000 이하의 자연수 stations의 크기: 10,000 이하의 자연수 stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다. W: 10,000 이하의 자연수 시간 초과에 유의해서 풀어야 한다. N이 2억개이므로, N으로 순회를 한다면 시간초과가 발생한다. statio..

문제 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 bfs로 1번 노드부터 탐색하면서 각 노드 별로 depth를 저장하면 풀 수 있다. depth 저장 배열을 정렬시킨 후 max값을 count 한다. 소스코드 import java.util.*; class Solution { int[] depth; boolean[] visited; ArrayList[] nodes; public int solution(int n, int[][] edge) { // 자료 구조 생성 depth ..

문제 https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 집에서 학교 까지의 최단 경로의 수를 구하는 문제이다. 아래, 우측 방향으로만 이동할 수 있고 물웅덩이는 지나갈 수 없다. 행렬 크기 값이 보통 문제와 달리 반대로 주어지니, 헷갈리지 않도록 유의해야 한다. 처음에 dfs, bfs 로 시도했지만 정답은 맞지만 효율성에서 통과가 안된다. 해당 문제는 동적 계획법 카테고리에 있는 문제로, DP로..

문제 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 풀이 기본적으로 BFS와 DP방식으로 문제를 접근했다. BFS로 영역을 확장해 나..