매일 조금씩

문제 https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 풀이 정수 삼각형과 유사한 문제이다. land와 동일 사이즈의 배열을 생성하여 행과 열을 순회하면서, 해당 index에서 가질 수 있는 최대 점수를 저장해나간다. 마지막 행의 최대 값이 답이 된다. 2021.11.08 - [Problem Solving/BOJ] - [BOJ 1932] 정수 삼각형 (Java) [BOJ 1932] 정수 삼각..

문제 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 dp 문제로 각 위치마다 최대값을 저장해나간다. 마지막 행에서 가장 큰 값이 답이된다. 2021.11.08 - [Problem Solving/BOJ] - [BOJ 1932] 정수 삼각형 (Java) [BOJ 1932] 정수 삼각형 (Java) 문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄..

문제 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로 영역을 확장해 나..

문제 https://programmers.co.kr/learn/courses/30/lessons/42628# 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 풀이 최소힙, 최대힙을 각각 두 개 만들어서 풀었다. size가 0이 되었을 때는 큐를 clear 해줘야한다. 안 그러면 일부 남은 데이터로 인해 오류가 발생한다. 소스코드 import java.util.*; class CustomQueue{ int size; PriorityQueue minHeap; PriorityQueue maxHeap; public CustomQueue(){ this.size = 0; this.minHeap = new PriorityQueue(new Comparator(){ @Override public int..

문제 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 MST 만드는 문제로 보여서 크루스컬 알고리즘으로 풀었다. 가중치가 적은 간선부터 사이클이 만들어지지 않을 경우, 연결해 나간다. 소스코드 import java.util.*; class Edge implements Comparable{ int nodeA; int nodeB; int weight; public Edge(int nodeA, int nodeB, int weight){ this.nodeA = nodeA; this.nodeB = nodeB; ..

문제 https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 Greedy 알고리즘을 이용해서 푼다. 예제 데이터는 아래와 같다. int[][] route = [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] route[i][0] = i번 차의 진입 시점 route[i][1] = i번 차의 진출 시점 직관적으로 봤을 때 아래와 같이 카메라를 설치 하면 되는 것을 알 수 있다. -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 풀이 처음에 방문 체크를 HashSet을 이용했었고 예제가 맞아서 제출을 했지만 1번, 2번 테스트 케이스에서 런타임에러가 발생하였다. 원인은.... 바로 중복 티켓이 허용된다는 것이다. 다음과 같이 from-to가 동일한 티켓이 포함될 수있다. Tickets: [["ICN", "SFO"], ["SFO", "ICN"], ..