프로그래밍/백준 문제풀이26 백준 4375: 1 (JAVA) / 모듈러 연산 분배 법칙 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 수학 문제이다. 나머지 연산자를 사용하여 단순히 계속 나누면 타임 아웃이 발생한다. 이 문제를 풀려면 나머지 연산의 분배법칙에 대해 알아야 한다. (A + B) % p = ((A % p) + (B % p)) % p (A * B) % p = ((A % p) * (B % p)) % p (A - B) % p = ((A % p) - (B % p) + p) % p %연산은 위와 같은 분배 법칙이 성립한다. 4375에 적용해보면 1, 11, 111, 111.. 2022. 8. 12. 백준 1316: 그룹 단어(JAVA) / https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 단어가 그룹 단어인지 판별하는 check라는 함수를 따로 만들었다. 그룹 단어이면 1을 반환하고 아니면 0을 반환해 카운팅해주면 된다. i번째 문자를 ch라 할 때 ch가 다음 인덱스의 문자와 다르다면, 그 이후부터는 ch가 문자열에 있으면 안된다. 따라서 i+1부터 마지막까지 잘라낸 문자열에 ch가 포함되어 있는지 검사하는 것을 [마지막 인덱스 - 1]까지 실행하.. 2022. 8. 10. 백준 1920: 수 찾기 / 이진 탐색(binary search) https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 시간 단축을 위해 이분 탐색 알고리즘을 이용하였다. 수를 n개 입력 받아 정수형 배열에 담은 후 Arrays.sort()로 오름차순 정렬을 해준다. 그 후 수를 입력 받아 이분 탐색 함수로 넘겨 배열 안에 있는지 판별하는 것을 m번 반복하면 된다. *이분탐색(이진탐색, binary search) 정렬되어 있는 수 들 중에서 key값을 찾으려고 할 때.. 2022. 8. 9. 백준 1929: 소수 구하기(JAVA) / 에라토스테네스의 체 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 소수를 판별하는 알고리즘은 여러가지가 있다. 숫자 하나에 대하여 소수인지 판단할 때는 해당 숫자의 제곱근까지만 약수인지 아닌지 반복문을 돌리면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 특정 수를 나눴을 때 몫은 항상 그 수의 제곱근 이하이기 때문이다. 하지만 여러 개의 소수를 한꺼번에 판별해야할 경우는 에라토스테네스의 체를 이용한다. *에라스토스테네스의 체 소수를 판별할 범위만큼 배열을 할당하고 소수가 아니면 하나.. 2022. 8. 9. 백준 10816: 숫자 카드 2(JAVA) https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 전에 풀었던 숫자 카드는 해당 숫자의 카드가 있는지만 판별하면 되는거라서 HashSet의 contains로 쉽게 풀 수 있었다. 이번 숫자 카드 2 문제는 해당 숫자의 카드가 몇 개 있는지까지 저장해야해서 위와 같은 방법으로는 풀 수 없다. 그래서 떠올린 방법이 map을 이용하는 것이다. 물론 더 좋은 방법이 있을 것 같지만...일단 도전 key 값으로 카드의 숫.. 2022. 7. 19. 백준 1181: 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net Arrays.sort()를 이용하여 정렬하였다. 첫번째는 String 객체에 기본적으로 구현되어있는 Comparator에 의해 알파벳 순서로 정렬이 된다. 그 후 새롭게 문자열을 비교해서 반환하는 Comparator를 구현하면 길이가 짧은 순서로 정렬된다. 최종적으로는 길이 순으로, 그 중에서도 알파벳 순으로 정렬이 된다. 중복은 출력문에서 처리하였다. 앞에 위치한 문자열과 같다면 출력.. 2022. 7. 17. 이전 1 2 3 4 5 다음
