문제풀이 190

[PS] 프로그래머스 광물캐기 ( Greedy ) with JAVA

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 어려운 알고리즘이 필요한 문제는 아니었지만 적절한 풀이 발상이 쉽지 않은 문제였다. 곡갱이는 종류에 상관없이 광물을 5개까지만 캘 수 있고 한번 캐기 시작하면 교체할 수 없다. 곡갱이의 종류에 따라 피로도가 달라지므로 최소 피로도를 구하려면, 가장 성능 좋은 곡갱이(다이아)로 가장 피로도가 높은 광물집합( 광물 5개 이하로 구성된 )을 캐야 한다. 1) 곡갱이를 다이아-철-흙 순으로 곡갱이 큐에 넣는다. ( 성능순 ) 2) 나열된 광물을 앞에서부터 5개씩 끊어 광물집합 객체를 생성하고 우선순위 큐..

문제풀이/Greedy 2024.04.12

[PS] 프로그래머스 - 삼총사 ( 백트래킹 ) with JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/131705 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 N명의 학생 중에 3명의 조합을 찾는 문제이다. 조합의 모든 경우의 수를 완전탐색하는 알고리즘에는 백트래킹(BackTracking)이 있다. DFS와는 다르다. DFS는 모든 '노드'를 방문하는 완전탐색 시, 사용되는 알고리즘이다. 백트래킹은 모든 '조합'을 완전 탐색하는 경우 사용되는 알고리즘이다. 그럼 백트래킹을 사용하여 N명의 학생 중 3명의 조함(삼총사)를 찾는 코드를 구현해..

[PS] 프로그래머스 햄버거만들기 ( 자료구조 ) with JAVA

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 재료들이 배열에 차례대로 저장되어 있다. 햄버거를 만드는 패턴과 일치하는 케이스를 카운트 하면 된다. 배열에 저장되어 있는 재료들을 가장 왼쪽부터 차례대로 자료구조에 담으면서, 빵-야채-고기-빵 차례로 데이터가 나열되는지를 체크하면 된다. 자료구조는 리스트를 사용하였고 리스트에서 만들어진 햄버거 재료를 제거할 때, size가 가변적으로 변하니 인덱스 사용에 주의해야 한다. ◎ 코드 import java.util.*; class Solution { public int solution(int[] in..

[PS] 프로그래머스 - 과제 진행하기 ( 구현, 자료구조 ) with JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/176962 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 문제의 요구사항을 요약하면 다음과 같다. 1) 우선순위는 새로 시작한 과제가 높다. 2) 기존 진행중이던 과제는 우선순위가 낮다. 3) 멈추어둔 과제가 여러개이면 최근에 멈춘 순으로 시작 4) 과제를 끝낸순서로 이름을 배열에 담아 return 요구사항을 다음과 같은 알고리즘으로 구현하면 된다. 1) 우선순위큐를 사용하여 과제를 시간을 기준으로 오름차순 정렬한다. 2) 첫 시간부터 1..

[PS] 프로그래머스-요격시스템 (Greedy) with JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ◎ 문제풀이 폭격미사일은 X 좌표 범위(start,end)를 가지고 요격미사일은 특정 x좌표에서 발사될 때, 최소한의 요격미사일 발사로 폭격미사일을 요격해야하는 문제이다. 주어진 폭격미사일 범위를 end좌표로 오름차순 정렬하는 것이 중요하다. 요격미사일은 폭격미사일이 끝(end)나는 지점에서 최소한 한 개가 발사되어야 하기 때문이다. 그러므로 폭격미사일 배열을 end를 기준으로 오름차순 정렬해야..

문제풀이/Greedy 2024.04.08

[PS] BOJ12865 평범한 배낭 ( DP ) with JAVA

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net ◎ 문제풀이 무게 제한이 있는 배낭에 아이템을 넣는 경우, 가치의 최댓값을 구하는 문제이다. 2가지 경우를 생각할 수 있다. 1) 배낭에 넣는 경우 2) 배낭에 넣지 않은 경우 그래서 DFS로 2가지 경우를 완전 탐색해도 될거 같지만, DP로 문제를 풀어보겠다. 무게 제한이 7인 배낭에 아이템1( 무게 6 ), 아이템2( 무게 4) , 아이템3( 무게 3 ), 아이템4( 무게 5 )를 넣으려고 한다..

문제풀이/DP 2024.02.23

[PS] BOJ1446 지름길 ( DP ) With JAVA

1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net ◎ 문제풀이 DP 발상이 가능하면 쉽게 풀 수 있는 문제이다. 어느 한 지점에 도착할 수 있는 경우는 2가지이다. 1) 바로 옆에서 1 이동하는 경우 2) 지름길로 이동하는 경우 지름길로 이동하는 경우는 여러가지가 될 수 있다. 그러므로 여러 가지 경우 중에서 가장 최소인 비용을 기억(메모리제이션) 해놓고 다음 지점의 최소비용 구할 때 사용하면 된다. 0부터 목표지점 D까지 Bottom-Up 방식으로 1씩 dp 값을 구하는 방식으로 문제를 풀면 된다...

문제풀이/DP 2024.02.23

[PS] BOJ1052 물병 ( 비트마스킹 ) With JAVA

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net ◎ 문제풀이 비트마스킹을 발상하면 쉽게 풀 수 있는 문제이다. ( 비스트 마스킹 발상이 어렵다.. ) 지민이가 가지고 있는 N개의 물병은 1L 씩 채워져 있고, 2개씩 합쳐서 K개 이하로 만들 때, 구매해야 하는 물병의 개수를 구하는 문제이다. 예를 들어, 지민이가 물병을 13개 가지고 있고 한번에 2개를 옮길 수 있다고 가정해보자. 물병 13개를 합치면 3개의 물병이 남는다. ( 8L, 4L, 1L ..

[PS] BOJ16508 전공책 ( DFS ) With JAVA

16508번: 전공책 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 www.acmicpc.net ◎문제풀이 타이틀을 완성하도록 전공책을 선택할 때 가장 적은 비용을 고르는 문제이다. 나는 DFS 풀이를 발상하기는 했지만 완전탐색을 어떤 방식으로 할지 구현하지 못했다. 그러나 굉장히 단순한 풀이였다. 오히려 너무 단순해서 풀이방식을 떠올리지 못한 것 같다. 전공책을 선택할 수 있고 전공책을 선택 안 할 수도 있다. 선택하는 경우와 안 하는 경우로 DFS 탐색하며, 타이틀을 완성 여부를 체크하고 비용의 최소값을 구하면 된다. ◎ 코드 import java.io.*;..

[PS] BOJ1740 거듭제곱 ( 비트마스킹 ) with JAVA

1740번: 거듭제곱 3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수를 생각할 수 있다. 예를 www.acmicpc.net ◎ 문제풀이 3의 거듭제곱의 합 중 N번째로 작은 수를 구하는 문제이다. 비트마스킹을 처음 풀어본 사람이라면 발상이 어려운 문제이다. 대표적인 거듭제곱의 합은 이진수 표현식이다. 십진수를 이진수로 표현하면 2의 거듭제곱의 합으로 표현할 수 있다. 10101 은 2의 0승, 2의2승, 2의 4승의 합이다. 여기서 2를 3으로 바꾸어주면 3의 거듭제곱의 합으로 바꿀 수 있다. 1 : 1 -> 1 2 : 10 -> 3 3 : 11 ->..