개발개발

1. 문제 https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 2. 풀이 투포인터와 BFS를 모두 활용한다. 구해야 되는 것은 가장 작은 고도의 차이므로, 가장 높은 고도(high)와 가장 낮은 고도(low)를 설정해 그 고도 내에서 집배원이 모든 집을 방문할 수 있는지 본다. 투포인터를 이용해 low 값 과 high 값을 변경해가며 가장 작은 고도차를 찾는다. 고도 내에서 모든 집을 방문할수 있는지 확인 할 때 BFS를 사용한다..

1. 문제 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 2. 풀이 숫자가 A, B, C, D 총 네종류가 있고 합이 0이 되는 A, B, C, D 쌍을 구해야 한다. 이를 A와 B의 가능한 모든 합과 C와 D의 가능한 모든 합으로 나누어 구하고 A와 B의 합과 C와 D의 합 중 0이 되는 쌍을 찾는다. 즉, (A+B) + (C+D) 이런식으로 나누어 생각하는 것이다. A와 B의 합과 C와 D의 합은 가능한 모든 경우의 수를..

1. 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 2. 풀이 방법 1) 우선 순위 큐 사용 자바로 우선 순위 큐를 사용해 정렬 된 값을 바로 사용해서 하려고 했더니 시간 초과가 난다. 자바로 풀기 위해 다른 방법을 찾아 봤다. 방법 2) Deque 사용 숫자가 있는 위치와 숫자의 값을 모두 Deque에 넣어 풀이하는 방법이다. (1) 현재 숫자를 입력 받는다. (2) 현재 덱 내에 있는 수 중 뒤에서 부..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42587?language=java 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 2. 풀이 우선순위 큐를 사용해서 풀었다. 우선순위 큐를 사용하면 숫자가 오름차순으로 자동으로 큐에 정렬되는데, 이 문제에서는 우선순의 큐를 내림차순으로 정렬한다. pq가 빌 때 까지(= 모든 문서가 출력될 때 까지), for문을 돌아가며 pq 내의 가장 큰 값과 그때의 위치를 찾는다. pq 내의 가장 큰 값과 그때의 위치를 찾으..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42584?language=java 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 2. 풀이 문제의 조건을 그대로 구현하는 식으로 풀이를 했다. 3. 코드 class Solution { public int[] solution(int[] prices) { int[] answer = {}; answer = new int[prices.length]; for(int i = ..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 2. 풀이 map을 사용해서 풀이했다. map 형식으로 옷의 종류마다 개수를 세었다. 결과를 구할 때는, headgear: 2개 face: 3개 eyewear: 1개 각 종류의 옷을 선택하는 경우 + 해당 종류의 옷을 아예 안입을 경우를 고려해 옷의 종류 + 1을 모두 곱해준다. 즉, 위의 경우에서는 (2+1) * (3+1) * (1+1)을 한다. 마지막으로 모든 옷을 입지 않을 경우를 제외해서 -1을 해준다. 3. 코드 import java.util.HashMap; import java.util.Set; class Solution { ..

1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2. 풀이 입력 받은 수부터 연산을 수행해가며 가장 횟수가 적은 경우를 얻기 위해 DP 배열에 각 경우의 값을 저장한다. 입력 받는 수를 X라 했을 때, X/3, X/2 X-1로 총 3가지 연산이 가능하다. 세 연산이 모두 가능한 상황 일 경우 X-1이 가장 큰 연산횟수가 드는 것이 확실히며 X-1 연산은 모든 경우에 가능하므로 X-1 연산을 한 경우의 값을 DP 배열에 가장 먼저 저장한다. X-1 연산을 수행할 경우의 결과를 기본 값으로 두고 두 연산이 가능할 경우에 각각의 연산을 수행해 두 연산(..