정리

백준 1092번: 배 - 정렬과 그리디 알고리즘을 활용하는 문제입니다. 크레인의 무게를 저장한 Arraylist와 박스의 무게를 저장한 Arraylist를 내림차순으로 정렬합니다. craneList.get(0)이 boxList(0)보다 작으면 박스를 모든 박스를 옮길 수 없으므로 -1을 출력합니다. 이중 while문을 통해 밖의 while문은 boxList.size() == 0 이 될 때까지(박스가 더 이상 없을 경우)까지 반복합니다. 안에 있는 while문은 1분에 옮길 수 있는 박스의 수를 계산합니다.

백준 2512번: 예산 - 이분 탐색 알고리즘을 써야하는 문제입니다. 이분 탐색을 사용하지 않고 상한액을 선형 탐색하면 시간초과에 걸립니다. - 이분 탐색 알고리즘은 예산의 상한액을 찾을 때 사용됩니다. 입력 받은 예산 요청액들을 배열에 저장한 뒤 sort() 를 통해 오름차순으로 정렬합니다. 예산 상한액은 0부터 배열의 마지막 값(가장 큰 값) 사이를 이분 탐색하면서 찾습니다. 예산 상한액보다 작은 요청액은 그 값을 그대로 더하고 예산 상한액보다 큰 요청액들은 예산 상한액을 더합니다. 총합이 총 예산보다 작을 때를 찾아서 상한액을 반환해주면 됩니다.

백준 10845번: 큐 - 자료구조 중 큐(queue)를 사용해서 푸는 문제입니다. - Java에서는 java.util.LinkedList 와 java.util.Queue 를 import 하면 라이브러리를 이용해서 쉽게 풀 수 있습니다. - 아래 코드에서 사용한 기능은 다음과 같습니다. add() : 큐에 데이터를 추가 isEmpty() : 큐가 비었는지 찼는지 확인 poll() : 큐에 가장 먼저 추가 된 데이터 출력 이후 큐에서 삭제 size() : 큐에 저장 된 데이터 수 출력 peek() : 큐에 가장 먼저 추가 된 데이터 출력

백준 10828번: 스택 - 문제명 그대로 자료구조 중 스택을 이용하면 되는 문제입니다. - Java에서 스택은 java.util.Stack 을 import 하면 쉽게 사용할 수 있는 자료구조입니다. 그래서 이번 문제에서는 util에서 제공해주는 스택을 사용한 코드와 제공해주는 스택을 사용하지 않고 직접 배열로 구현하는 코드 두 가지를 작성해 보았습니다. - 우선 util에서 제공해주는 스택을 사용한 코드입니다. - Stack 라이브러리 중에는 다음과 같은 기능이 있습니다. push() : 스택에 데이터 삽입 pop() : 스택에사 가장 위에 있는 데이터를 팝(반환하고 삭제) peek() : 스택에서 가장 위에 있는 데이터를 읽음(반환) isEmpty() : 스택이 비어있는지를 반환 size() : 스택..

백준 1024번: 수열의 합 - q = N / L, N을 L로 나눈 값을 q라고 지정해 주었습니다. 그 후 L이 짝수인 경우와 홀수인 경우로 나누어서 코드를 짰습니다. i) L = 짝수 만약 q를 1로 나눈 나머지가 0.5이면 해당 리스트를 출력합니다. ex) N = 18, L = 4, q = 4.5 3, (q-1.5) 4, (q- 0.5) 5, (q+0.5) 6, (q+1.5) ii) L = 홀수 만약 q를 1로 나눈 나머지가 0이면, q가 정수이면 해당 리스트를 출력합니다. ex) N = 18, L = 3, q = 6 5, (q-1) 6, (q) 7, (q+1) -while문의 탈출 조건은 L이 100을 초과하거나 q - (l/2 - 0.5) 값이 음이 되면 탈출합니다. q - (l/2 - 0.5) ..

백준 1010번: 다리 놓기 - 조합(Combination)을 이용하여 푸는 문제입니다. 다리를 지을 수 있는 경우의 수는 mCr 입니다. - int, long형을 사용하면 오버플로우가 발생해서 사용하면 안 됩니다. Java의 경우 BigInterger Class를 사용할 수도 있지만 저는 그냥 double을 사용했습니다.

백준 13305번: 주유소 - 주유소의 리터당 가격에 대한 배열(price배열)에서 내림차순에 어긋나는 부분이 있는지 확인합니다. 내림차순에 어긋나는 인덱스는 앞의 주유소보다 리터당 가격이 비싸므로 주유를 하면 안 되는 곳입니다. (단, 가장 첫 주유소와 가장 마지막 주유소 제외) 내림차순에 어긋나는 인덱스의 값은 바로 앞 주유소의 리터당 가격으로 바꾸어 줍니다. - 같은 인덱스 값을 가진 거리에 대한 배열과 가격에 대한 배열을 곱한 뒤 총합을 구해줍니다.

백준 2485번: 가로수 - 유클리드 호제법을 사용해서 푸는 문제입니다. 각 가로수 간의 거리를 구합니다. 거리들의 최대공약수를 구합니다. (거리 / 최대공약수 - 1)들의 합을 구하면 가로수의 최소수를 구할 수 있습니다. 유클리드 호제법에 대한 정보는 아래 게시물에서 참고할 수 있습니다. 2020/07/03 - [백준 BOJ] - 백준 2609번: 최대공약수와 최소공배수 더보기

백준 2609번: 최대공약수와 최소공배수 - 최대공약수와 최소공배수를 구하는 가장 널리 알려진 방법입니다. 이러한 방법을 for문을 이용하여 코드를 만들면 아래와 비슷한 코드를 만드실 수 있을 겁니다. 하지만 시간 초과에 걸려 통과하지 못합니다. - 이 문제는 "유클리드 호제법"을 사용하여 풀어야 합니다. 유클리드 호제법이란, 두 양의 정수 a, b (a > b)에 대하여 a = bq + r (0 ≤ r a = 18, b = 6 a = 18, ..

백준 1037번: 약수 - 약수의 개수 제곱수: 홀수 개 제곱수가 아닌 수: 짝수 개 - 이 문제에서 제곱수는 진짜약수개수=1이다. 따라서 array[0] * array[0] 을 출력해주면 된다. - 제곱수가 아닌 수인 경우에는 퀵소트(quickSort)를 통해서 오름차순으로 정렬 한 뒤, array[0] * array[진짜약수개수-1] 을 출력해주면 된다.