알고리즘
-
BOJ) 단어 정렬알고리즘/백준 2020. 6. 23. 21:18
단어 정렬 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 넋두리 문제를 보고 풀지 말지 고민을 많이했다. 문제를 보자마자 우선순위 큐면 금방 풀리는 문제라고 떠올랐기 때문이다. 복잡한 과정 없이 자료구조 하나만 써서 풀리는 문제는 허무하다고 느끼지만, 요즘 슬럼프라서 틀리는 문제가 많아 그냥 풀었다. 사실 우선순위 큐 말고 ArrayList나 배열을 이용해서 풀어도 된다. sort 메소드를 사용할 때, Comparator만 아래와 같이 작성해주면 되기 때문에.. 하지만 제일 처음 떠올린게 우선순위 큐라 ..
-
BOJ) 케이크 자르기알고리즘/백준 2020. 6. 23. 21:12
케이크 자르기 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 � www.acmicpc.net 풀이 문제를 처음 봤을 때, 요즘 DP 문제를 많이 풀어서 그런지 Dp가 가장 먼저 떠올랐다. 하지만, 너무 복잡하고 생각할 것이 많아지면서 DP는 아니라고 생각하고 포기했다. 질문 게시판을 살펴보니까, 이분 탐색이라는 얘기가 많았다. 이분 탐색보다 더 좋은 방법이 있을까 생각해보다가, 그냥 이분탐색으로 풀게 되었다. 예전 카카오 문제 중에 돌다리 건너기(?) 문제와 유사하다고 생각한다. 돌다리 문제..
-
BOJ) 수 이어 쓰기 2알고리즘/백준 2020. 6. 23. 14:13
수 이어 쓰기 2 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 풀이 주어지는 n과 k의 범위가 각각 1억, 10억이어서 아무 생각없이 int 형으로 생각하고 문제를 풀어나가서 틀린 부분을 찾는데 시간이 조금 걸렸다. 왜냐하면, 입력 숫자가 1억인 경우에, 누적으로 문자열 길이를 저장하는 함수가 9억 9천만(....)*9 까지 더해주기 때문이었다. 일단, 숫자를 문자열에 그대로 붙였을 때, 1~9는 한 글자가 증가하고 10~99는 두 글자가 증가한다. 100~999는 세 글자가 증가하는데, 위의 규칙을 살펴보면 10^(n-1) ~ (10^..
-
BOJ) 상자넣기알고리즘/백준 2020. 6. 23. 13:44
상자넣기 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 �� www.acmicpc.net 풀이 일렬로 정렬된 상자들에서 앞의 상자 크기가 뒤에보다 작으면, 뒤에 상자에 넣어 정리하는 문제였다. dp로 푸는게 적합하겠다는 생각을 하고 코드를 작성했다. 박스를 순차적으로 탐색하면서, 이전의 박스들 중 가장 많이 저장된 박스에 담는 dp를 만들었다. 이때, 앞의 상자 크기가 뒤에 상자 크기보다 작아야한다는 조건을 걸어서 저장하면서, 쉽게 답을 구할 수 있었다. 코드 import java.io.BufferedReader; import java.io.I..
-
BOJ) 방 번호알고리즘/백준 2020. 6. 23. 13:39
방 번호 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 넋두리 작년에 풀었던 문제였는데, 코테 준비를 조금이나마 진행했으니까 더 좋은 방법으로 풀지 않을까 싶어서 풀어봤다. 저번에 풀었을 때 보다 시간이 아주 조금 늘었고, 메모리 사용량이 아주 조금 줄었다. 결과적으로는 똑같은 것 같다... ㅋㅋㅋㅋㅋㅋ 사실 크게 복잡한 문제가 아니라서 판단하기에 적합하지는 않지만, 그래도 조금 더 열심히 하자 코드 1 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util..
-
BOJ) 블랙잭알고리즘/백준 2020. 6. 23. 13:33
블랙잭 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 �� www.acmicpc.net 풀이 dp로 풀까 생각하다가, 고려할 사항이 많아질 것 같아서 모든 경우에 따라 최대 값을 구하기로 했다. 앞에서 부터 3장의 카드를 고르고, 해당 숫자가 m 이하일 경우에 최대 값을 갱신해줬다. 3중 포문은 돌리기 싫었지만, 좋은 방법이 떠오르지 않았다.. ㅠㅠ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..
-
BOJ) 연결 요소의 개수알고리즘/백준 2020. 6. 22. 01:47
연결 요소의 개수 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 풀이 최근에 이 문제랑 거의 유사한 문제를 풀었던 것 같다. 그래서 비교적 빠르게 풀 수 있었다. 우선, 노드의 갯수 N은 1000 이하기 때문에, int형 배열을 이용해도 메모리 제한에 문제가 없다고 판단했다. 또한, 간선의 갯수 M은 N×(N-1)/2 즉, 최대의 경우 499,500이라는 숫자가 나오기 때문에 따로 저장을 하지 않고 입력을 받는 즉시 로직을 수행하도록 설정했다...
-
BOJ) 치킨 쿠폰알고리즘/백준 2020. 6. 22. 01:41
치킨 쿠폰 1673번: 치킨 쿠폰 문제 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 www.acmicpc.net 풀이 입력 횟수가 주어지지 않은 상태에서 BufferedReader로 입력을 받는 것에 대해 새롭게 공부했다. EOF(End Of file, 파일의 끝)를 만났을 때, readLine() 메소드를 호출하면 null이 반환된다. 따라서, 입력 제한이 존재하지 않을 경우에는 문자열 변수에 입력을 해주고 null 체크를 하면 된다. 그리고 치킨 쿠폰 문제는 치킨 한 마리 먹기가 왜이리 힘든지 모르겠다.. 문제에서 놓친 부분은, 치킨을 쿠폰으로 시킬 수 있을..