본문 바로가기

알고리즘 문제147

[알고리즘 문제] 백준1138 - 한 줄로 서기 문제 해결방법은, 1. arr[입력크기]를 만들고 각 인덱스는 N키를, 인덱스의 값은 N키에서 왼쪽에 있는 자기보다 키가 큰 사람의 수. 2. arr[]에서 인덱스의 값이 0인 부분은 자신보다 키가 큰 부분. 3. 단, arr[0]부터 arr.length까지 반복하면서, 인덱스의 값이 0이면 M(입력받은 값)을 하나 빼준다. 그리고 M=0이면, 나보다 큰 값을 모두 건너왔음을 의미, 해당 인덱스에 N값을 넣어준다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; .. 2019. 6. 15.
[알고리즘 문제] 백준2529 - 부등호 문제는 다음의 부등호 기호 앞뒤에 서로 다른 숫자들을 넣었을 때, 부등호 기호를 만족하는 숫자조합의 최소/최대값을 구하는 문제이다. 대충 어떻게 푸는지는 알았는데, 생각보다 시간이 오래 걸렸다. 부등호 기호사이에 들어가는 숫자는 0~9이다. 0123456789 ~ 9876543210사이에서 부등호 기호를 만족하는 최소/최대값을 구해야 한다. 우리가 찾는 값은 최소/최대 2개의 값이기 때문에 모두 검사할 필요가 없다. 최대값은 9876543210부터 값을 감소하면서 부등호 기호 조건을 만족하는 첫번째 값이 최대값이 된다. 최소값은 0123456789부터 값을 증가하면서 부등호 기호 조건을 만족하는 첫번쨰 값이 최소값이 된다. 부등호 사이에 들어가는 숫자들을 구하는 방법은 재귀함수를 사용하였다. 숫자들은 모.. 2019. 6. 11.
[알고리즘 문제] 백준1049 - 기타줄 문제는 여러개의 브랜드에서 최소의 가격으로 원하는 만큼의 기타줄을 사는 문제이다. 먼저 각 브랜드마다 기타줄을 6개 세트 가격, 낱개의 가격으로 판매한다. 세트의 가격, 낱개의 가격을 입력받으면서 각각 최소값을 구한다. 이 최소값을 사용하여 6개를 사는데 세트의 가격과 낱개 * 6의 가격을 비교한다. 만약 세트인 경우가 더 싸면 N/6개를 구매하고, 더 비싸면 N/6*6개를 구매한다. 그리고 구매한 만큼 N개에서 빼준다(6으로 나누었을 때 나머지 값) 이렇게 하는 이유는, 만약 필요한 기타줄이 33개인 경우 30개까지 사는데 더 싸게 사기 위함이다. 다시 남은 N개를 가장 싸게 사는 경우를 생각한다. 한 세트를 사는 경우와 N*1개의 가격중 더 싼 가격을 선택하며 money에 더해준다. import ja.. 2019. 6. 9.
[알고리즘 문제] 백준1946 - 신입사원 문제는 신입사원들의 서류/면접 성적이 있을 때 이 성적을 사용하여 신입사원을 채용하는 문제이다. 만약 나보다 서류/면접이 모두 좋은 사람이 한사람이라도 있다면 나는 탈락이게 된다. 만약 나의 성적이 [ 4,6 ]인데, 둘 다 나보다 높은 경우 [ 3,5], [ 2,5 ]....가 있으면 나는 탈락되된다. 반대로 [ 2,7 ], [ 3,8 ]의 경우는 내가 하나의 성적은 다른 사람들보다 높게 되므로 이 경우는 합격하게 된다. 처음에는 2중 for문으로 한번 풀어봤다. 일단 모든 성적을 입력받은 다음에, N번을 기준으로 N을 제외한 지원자들과 비교해 보았다. 이렇게 하면 지원자의 수가 ~10만 인데, 10^2의 시간복잡도가 나온다. 당연히 시간초과 다음 방법은 처음에 입력받을 때, 서류성적을 index로 하.. 2019. 6. 7.

티스토리툴바