매일 조금씩

문제 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"], ..

문제 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 DFS 알고리즘을 이용해서 풀었다. 중복 체크는 HashSet을 사용하였다. dfs 함수 호출 후, 다시 visitied에 해당 값을 제거해줘야 한다. 소스코드 import java.util.*; import java.lang.*; class Solution { public int answer; public ..

gitignore 이란? 프로젝트 내 다양한 설정 파일, 컴파일된 파일 등 굳이 버전관리가 필요 없는 파일들이 있다. 해당 파일들이 git commit 목록에 계속 보여진다면 불편할 것이다. 이러한 문제를 해결하기 위해, gitignore 파일을 통해 버전관리가 필요없는 파일들을 제외할 수 있다. 프로젝트의 root에 .ignore파일이 위치해야 인식한다. gitignore 작성 방법 제외할 파일의 패턴을 작성한다. https://git-scm.com/docs/gitignore Git - gitignore Documentation The optional configuration variable core.excludesFile indicates a path to a file containing patter..

배낭 문제 배낭 문제란 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 짐을 쪼갤 수 있는 경우에는 Fractional Knapsack Problem 으로 부르며, Greedy를 이용해 풀 수 있다. 짐을 쪼갤 수 없는 경우의 배낭문제는 0-1 배낭문제라고 부른다. 이 경우에는 DP를 이용해 문제를 풀 수 있다. https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C 배낭 문제 - 위키백과, 우리 모두의 백과사전 배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 S지점에서 X라는 지점에 도착해서 X->A, X->B 로 갈라진다. 즉,..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP문제로, Index를 차례대로 증가시키면서 해당 Index 왼편에 올 수 있는 바이토닉 부분 수열의 최대 개수를 구한다. 이때 기준 Index에서 작은 Index를 체크하면서, 기준보다 작은 수의 바이토닉 수열 최대 개수 중에 최대 값을 구한 후 +1을 해주면 된다. 아래 문제의 왼쪽 편만 구한 것이다. ..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 기준 숫자에서 왼쪽과 오른쪽을 나눈다. left[i] = i번째 수의 왼편에 올 수 있는 오름차순 부분 수열의 최대 개수 right[i] = i번째 수의 오른편에 올 수 있는 내림차순 부분 수열의 최대 개수 left[i] + right[i] 의 최대값에 1을 더한 것이 답이 된다. (1을 더하는 이유는 left, right에 기준 숫자가 빠져있기 때문) 차례대로 index를 증가 또는 감소 시키면서 채워나..