Algorithm
-
BOJ) 소수 구하기알고리즘/백준 2020. 6. 24. 17:08
소수 구하기 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 소수를 구하는 문제를 풀어본지 오래돼서 에라토네스의 채 자체를 망각하고 있었다. 그래서 GCD를 통해 풀어야하나 생각하다가, 소수를 구하는 알고리즘이 있나 찾아봤다. 에라토네스의 채를 보고 존재가 다시 떠올랐다. 구현하는 방법은 까먹어서 방법을 익히기로했다. 1은 소수에 포함되지 않기 떄문에 2부터 시작하고, j에 해당하는 부분은 자신의 배수에 대해 표시를 해주는 것이다. 이후에, for문을 돌면서 소수를 찾아 출력해줬다. 하지만, for문을 다시 도는 부분이 불필요하다고 느..
-
BOJ) 카드알고리즘/백준 2020. 6. 24. 16:57
카드 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 풀이 문제를 보고 바로 떠오른 방법은 Map을 이용해서 푸는 방법이었다. Map을 통해 해당 카드가 몇 번 나왔는지 카운트 한 다음, value를 통해 key를 정렬하는 방법이다. 문제의 조건에 따라, 나온 횟수가 같은 경우에는 카드의 숫자가 최소인 것부터 정렬해서 리스트의 가장 앞 부분에 있는 값을 리턴했다. 바로 맞기는 했지만, 효율이 너무 좋지 않았다. 메모리와 속도 측면도 그렇고, Map을 사용하지만 어차피 Key값을 저장하기 위해서 List를 ..
-
BOJ) 랜선 자르기알고리즘/백준 2020. 6. 24. 16:50
랜선 자르기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 문제를 접했을 때 이분 탐색이라는 느낌이 강하게 들었는데, N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다는 조건이 있어서 이분탐색으로 푸는 것이라고 확신을 느꼈다. 랜선의 길이가 2^31 -1인 것에 대수롭지않게, int의 최대값이겠거니 하고 int형으로 모든 코드를 짰다. 하지만, 틀렸다고 뜨길래 설마하면서 int형의 최대 값을 찍어봤더니 80정도 차이가 났다.. 2^31 -1은 int가 아닌 long형이..
-
BOJ) 균형잡힌 세상알고리즘/백준 2020. 6. 23. 21:34
균형잡힌 세상 4949번: 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단 www.acmicpc.net 풀이 정규식을 활용하면 시간도 덜 들고 풀기 쉽지 않을까 싶어서 정규식을 활용했다. replaceAll에 들어가는 부분인 "[^[]()]" 이 부분은 [ ] 안에 있는 문자들에 대해서 검사를 한다. [ ] 안에 ^가 들어가 있다면 해당 문자를 제외한 모든 글자를 의미한다. 따라서, [ ^ [ ] ( ) ] ( 보기 좋기 위한 띄어쓰기는 양해 부탁드립니다..)는 괄호로 여닫는 문자가 아닌 문자들을 의미한다. replaceAll을 수행하고 나면 띄어쓰..
-
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..