그리디
씨름 선수(그리디)
현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했습니다.”
만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다.
[[172, 67], [183, 65], [180, 70], [170, 72], [181, 60]]
-> 3▣ 입력설명
매개변수 body에 N(5<=N<=100,000)명의 키와 몸무게 정보가 차례로 주어집니다. 각 선수의 키와 몸무게는 모두 다릅니다.
▣ 출력설명
씨름 선수로 뽑히는 최대 인원을 반환하세요.
일단 키 순서대로 내림차순 정렬
- 첫번째 사람은 무조건 뽑힘
- 이 사람보다 몸무게가 많이 나가야 뽑힘
- 새로 뽑힌 사람 몸무게보다 많이 나가야 뽑힘
-> 몸무게 최댓값을 구해놓고 이 값보다 크면 뽑힌 인원++
import java.util.*;
class Main {
public int solution(int[][] body){
int answer=0;
Arrays.sort(body, (a,b)->b[0]-a[0]);
int maxW=0;
for(int[] x : body) {
if(x[1]>maxW) {
maxW=x[1];
answer++;
}
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution(new int[][]{{172, 67}, {183, 65}, {180, 70}, {170, 72}, {181, 60}}));
}
}최대 수입 스케쥴
<코드 외워두기!>
현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.
각 기업이 요청한 D와 M의 정보를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.
단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.
[[50, 2], [20, 1], [40, 2], [60, 3], [30, 3], [30, 1]]
-> 150
[[50, 2], [40, 2], [20, 1], [10, 1]]
-> 90▣ 입력설명
매개변수 nums에 N(1<=N<=10,000)개의 기업이 요청한 강연 M, D가 차례로 주어집니다.
▣ 출력설명
현수가 최대로 벌 수 있는 수입을 반환합니다.
우선순위 큐 사용
날짜 기준으로 내림차순 정렬
import java.util.*;
class Main {
public int solution(int[][] nums){
int answer=0;
PriorityQueue<Integer> pQ=new PriorityQueue<Integer>(Collections.reverseOrder());
Arrays.sort(nums, (a,b)->b[1]-a[1]);
int maxd=nums[0][1];
int j=0; // 이 부분 주의!
for(int i=maxd;i>0;i--) {
for( ;j<nums.length;j++) {
// 여기에서 j 초기화하면 쓸데없이 처음부터 돌아서
// 밖에서 초기화 한번만 시키고 break했던 부분부터 다시 돌게함
if(nums[j][1]<i) { break; }
pQ.offer(nums[j][0]);
}
if(!pQ.isEmpty()) { answer+=pQ.poll(); }
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution(new int[][]{{50,2}, {20,1}, {40,2}, {60,3}, {30,3}, {30,1}}));
}
}재귀함수
재귀함수
자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.
3
-> 1 2 3▣ 입력설명
매개변수 n에 정수 N(3<=N<=10)이 입력된다.
▣ 출력설명
1부터 N까지를 재귀함수가 출력합니다.
public class Main {
public void DFS(int n) {
if(n==0) return;
else {
DFS(n-1);
System.out.print(n+" ");
}
}
public static void main(String[] args) {
Main T = new Main();
T.DFS(3);
}
}재귀함수를 이용한 이진수 출력
10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다.
11
-> 1011▣ 입력설명
매개변수 n에 10진수 N(1<=N<=1,000)이 주어집니다.
▣ 출력설명
n의 이진수를 출력하세요.
public class Main {
String answer="";
public void DFS(int n) {
if(n==0) return;
else {
DFS(n/2);
answer+=(n%2);
}
}
public String solution(int n) {
DFS(n);
return answer;
}
public static void main(String[] args) {
Main T = new Main();
System.out.println(T.solution(11));
}
}DFS
여러 경우 중 최적의 경우 찾기
이진트리 순회(깊이우선탐색 : DFS)
아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.
전위순회 출력 : 1 2 4 5 3 6 7 (부->왼->오)
중위순회 출력 : 4 2 5 1 6 3 7 (왼->부->오)
후위순회 출력 : 4 5 2 6 7 3 1 (왼->오->부)아래 코드는 위에 있는 이진트리를 전위순회한 것입니다. 여러분이 아래 코드를 분석해보고, 중위순회, 후위순회를 출력해보세요. 그리고 스택에 스택프레임을 만들면서 분석도 해보세요.
▼ 전위순회
class Main {
public void DFS(int v){
if(v>7) return;
else{
System.out.print(v+" ");
DFS(v*2); // 왼쪽 자식
DFS(v*2+1); // 오른쪽 자식
}
}
public static void main(String[] args){
Main T = new Main();
T.DFS(1);
}
}▼ 중위순회
class Main {
public void DFS(int v){
if(v>7) return;
else{
DFS(v*2); // 왼쪽 자식
System.out.print(v+" ");
DFS(v*2+1); // 오른쪽 자식
}
}
public static void main(String[] args){
Main T = new Main();
T.DFS(1);
}
}▼ 후위순회
class Main {
public void DFS(int v){
if(v>7) return;
else{
DFS(v*2); // 왼쪽 자식
DFS(v*2+1); // 오른쪽 자식
System.out.print(v+" ");
}
}
public static void main(String[] args){
Main T = new Main();
T.DFS(1);
}
}중복순열 구하기
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
3 2
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
▣ 출력설명
첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.
import java.util.*;
class Main {
Stack<Integer> pm = new Stack<>();
static int n,m;
public void DFS(int L){
if(L==m) {
for(int x:pm) System.out.print(x+" ");
System.out.println();
}
else {
for(int i=1;i<=n;i++) {
pm.push(i);
DFS(L+1);
pm.pop();
}
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
n = scanner.nextInt();
m = scanner.nextInt();
T.DFS(0);
}
}순열 구하기(1)
10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
3 2
1 2
1 3
2 1
2 3
3 1
3 2▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
▣ 출력설명
첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.
import java.util.*;
class Main {
Stack<Integer> pm = new Stack<>();
static int n,m;
static int[] check;
public void DFS(int L){
if(L==m) {
for(int x:pm) System.out.print(x+" ");
System.out.println();
}
else {
for(int i=1;i<=n;i++) {
if(check[i]==0) {
pm.push(i);
check[i]=1;
DFS(L+1);
pm.pop();
check[i]=0;
}
}
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
n = scanner.nextInt();
m = scanner.nextInt();
check=new int[n+1];
T.DFS(0);
}
}순열 구하기(2)
10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
3 2
3 6 9
3 6
3 9
6 3
6 9
9 3
9 6▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.
▣ 출력설명
첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.
import java.util.*;
class Main {
Stack<Integer> pm = new Stack<>();
static int n,m;
static int[] check, nums;
public void DFS(int L){
if(L==m) {
for(int x:pm) System.out.print(x+" ");
System.out.println();
}
else {
for(int i=0;i<n;i++) {
if(check[i]==0) {
pm.push(nums[i]);
check[i]=1;
DFS(L+1);
pm.pop();
check[i]=0;
}
}
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
n = scanner.nextInt();
m = scanner.nextInt();
check=new int[n];
nums=new int[n];
for(int i=0;i<n;i++)
nums[i]=scanner.nextInt();
T.DFS(0);
}
}가장 가까운 큰수
자연수 N이 주어지면, N과 구성이 같으면서 N보다 큰 수 중 가장 작은 수를 출력하는 프로그램을 작성하세요.
구성이 같다는 말은 각 자릿수가 같은 숫자들로 이루어졌다는 의미입니다. 예를 들어 123과 231은 서로 구성이 같습니다. 하지만 123과 215는 구성이 다릅니다.
123 -> 132
321 -> -1
20573 -> 20735▣ 입력설명
매개변수 n에 자연수 N(1<=N<=9999999)이 주어집니다.
▣ 출력설명
N과 구성이 같으면서 N보다 큰 수 중 가장 작은 수를 반환합니다. 없으면 -1를 반환합니다.
import java.util.*;
class Main {
Stack<Integer> pm = new Stack<>();
ArrayList<Integer> nums = new ArrayList<>();
int[] check; // 위에서 사용했던 값인지
boolean flag; // 답 발견됐는지
static int answer, m, target;
public void DFS(int L){
if(flag) return;
if(L==m) {
answer=0;
for(int x:pm) {
answer=answer*10+x;
if(answer>target) { flag=true; }
}
}
else {
for(int i=0;i<m;i++) {
if(check[i]==0) {
check[i]=1;
pm.push(nums.get(i));
DFS(L+1);
pm.pop();
check[i]=0;
}
}
}
}
public int solution(int n) {
int tmp=n;
flag=false;
target=n;
while(tmp>0) {
int t=tmp%10;
nums.add(t);
tmp=tmp/10;
}
Collections.sort(nums);
m=nums.size();
check=new int[m];
DFS(0);
nums.clear(); // 여러 케이스 실행하기 위한 초기화
if(!flag) return -1;
return answer;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
System.out.println(T.solution(123));
System.out.println(T.solution(321));
System.out.println(T.solution(20573));
}
}조합 구하기
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.
4 2
1 2
1 3
1 4
2 3
2 4
3 4▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
▣ 출력설명
첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.
import java.util.*;
class Main {
Stack<Integer> combi = new Stack<>();
static int n, m;
public void DFS(int L, int s){
if(L==m) {
for(int x:combi) System.out.print(x+" ");
System.out.println();
}
else {
for(int i=s;i<=n;i++) {
combi.push(i);
DFS(L+1, i+1);
combi.pop();
}
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
n=scanner.nextInt();
m=scanner.nextInt();
T.DFS(0,1);
}
}BFS
최단 거리, 최단 횟수
이진트리 레벨탐색(넓이우선탐색 : BFS)
아래 그림과 같은 이진트리를 큐(Queue) 자료구조를 이용해 레벨탐색을 해보세요.
레벨탐색 출력 : 1 2 3 4 5 6 7
import java.util.*;
class Main {
ArrayList<Integer> answer = new ArrayList<>();
public ArrayList<Integer> solution(int n){
Queue<Integer> Q=new LinkedList<>();
Q.offer(1);
int L=0; // 레벨 나타내기 위한 변수
while(!Q.isEmpty()){
int len=Q.size(); // 현재 레벨 원소 개수
System.out.print(L+"레벨: ");
for(int i=0; i<len; i++){
int v=Q.poll();
System.out.print(v+" ");
answer.add(v);
for(int nv : new int[]{v*2, v*2+1}){
if(nv>n) { continue; }
Q.offer(nv);
}
}
System.out.println();
L++; // 다음 레벨로
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution(7));
}
}송아지 찾기(BFS : 상태트리탐색)
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.
▣ 입력설명
매개변수 s에 현수의 위치 S와 매개변수 e에 송아지의 위치 E가 주어집니다.
직선의 좌표 점은 1부터 10,000까지이다.
▣ 출력설명
점프의 최소횟수를 반환합니다. 답은 1이상입니다.
점프 횟수 = 송아지 위치의 레벨
5 - 0레벨
4 6 10 - 1레벨
3 9 7 11 15 - 2레벨
2 8 14 - 3레벨import java.util.*;
class Main {
public int solution(int s, int e){
Queue<Integer> Q=new LinkedList<>();
int[] check = new int[10001];
Q.offer(s);
check[s]=1;
int L=0; // 레벨 나타내기 위한 변수
while(!Q.isEmpty()){
int len=Q.size(); // 현재 레벨 원소 개수
for(int i=0; i<len; i++){ // 원소 개수만큼 for문 돌기!
int v=Q.poll();
// if(v==e) return L; // 여기에 하면 비효율적 (넣었다가 꺼내서 확인)
for(int nv : new int[]{v-1,v+1,v+5}){
if(nv==e) return L+1; // (넣을때 확인)
if(nv>0 && nv<=10000 && check[nv]==0) {
Q.offer(nv);
check[nv]=1;
}
}
}
L++; // 다음 레벨로
}
return 0;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
Main T = new Main();
int s = scanner.nextInt();
int e = scanner.nextInt();
System.out.println(T.solution(s, e));
}
}
