문제 설명한 마을에 모험가가 N명 있습니다.모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높을수록 위험 상황에서 대처 능력이 떨어집니다.모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최대값을 구하는 프로그램을 작성하세요.몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정 그룹에 넣을 필요는 없다. 입력조건첫째 줄에 모험가의 수 N(1 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분출력조건여행을 떠날 수 있는 그룹 수의 최대값을 ..

그리디 알고리즘이란?현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘즉, 매 순간 가장 좋아 보이는 것을 선택하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.정렬 알고리즘과 짝을 이뤄서 출제되는 경우가 많다. 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심해볼 수 있다. 하지만 그리디 알고리즘을 모든 상황에 적용할 수 있는 것은 아니다.현재 상황의 최적의 해가 전체 상황의 최적의 해를 보장하는 것은 아니기 때문이다.그렇기 때문에 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한 방법인지 검토해야 한다.  대표적인 그리디 알고리즘의 문제로 '거스름돈' 문제가 있다.예제 1) 거스름돈손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구한다..

[문제 링크]https://www.acmicpc.net/problem/18870문제 설명수직 선 위의 N개 좌표에 대해서 좌표 압축을 적용해서 출력Xi 를 좌표 압축한 결과 X'i는 Xi > Xj를 만족하는 Xj 의 개수(Xj는 모두 서로 다른 좌표이다)입력: N(좌표개수), N개의 좌표(X1, X2, ..., XN)출력: 좌표압축을 적용한 결과(X'1, X'2, ..., X'N)ex1) 2  4  -10  4  -9 의 좌표값이 주어졌을 때, 좌표압축한 결과는 2 3  0  2  1  이다.         2 보다 작은 값은 -10  -9,          4 보다 작은 값은 -10  -9  2,         -10 보다 작은 값은 없고,        -9 보다 작은 값은 -10ex2) 1000  9..

[문제 링크]https://www.acmicpc.net/problem/11720문제 설명공백없이 쓰여진 N개의 숫자를 모두 합해서 출력입력 : N(숫자의 개수), N개의 숫자출력 : 숫자 N개의 합   문제 풀이N개의 숫자를 하나의 문자열로 입력받은 후, charAt() 함수를 사용하여 한 문자씩 가져와서 합을 구한다. 이 때, charAt() 함수로 반환된 값은 char형이기 때문에 해당 문자의 아스키코드 값을 반환한다.따라서 - '0' or -48을 해주어야 한다.(1) Scanner 사용import java.util.Scanner;public class Main1 { public static void main(String[] args) { Scanner sc = new Scanne..

[문제 링크]https://www.acmicpc.net/problem/1260 문제 설명그래프를 DFS, BFS로 탐색한 결과 출력방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문더 이상 방문할 수 있는 점이 없는 경우 종료입력: 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V, 간선이 연결하는 두 정점의 번호출력: DFS 수행결과, BFS 수행 결과   문제 풀이DFS는 재귀를 사용해서 구현BFS는 큐를 사용해서 구현(1) Array 2차원 배열 사용import java.io.*;import java.util.*;public class Main { public static int n, m, v; ..

[문제 링크]https://www.acmicpc.net/problem/10951문제 설명두 정수 A, B를 입력받아서 A와 B를 더한 값 출력여러 개의 테스트 케이스로 이루어져 있고, 테스트 케이스 횟수는 정해져있지 않다.입력 종료는 더이상 읽을 수 없는 데이터(EOF)입력: A, B출력: A+B   문제 풀이(1) Scanner 사용hasNext() 함수를 사용해서 EOF일 경우 False 반환, 값이 있는 경우 True 반환import java.util.Scanner;public class Main1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNex..