S E P H ' S

10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 (구간 합) 문제를 보자마자 풀이가 바로 떠올랐는데 골드 3이라는 난이도와 입력값들의 범위가 맘에 걸리긴 했지만 생각난 풀이로 풀어보기로 했다. 구간합 배열하나를 만든 후 i, j 범위 사이의 모든 구간합들의 차이를 구해서 그 값이 3이면 cnt를 늘리는 식으로 했는데 역시나 시간초과가 났다. 먼저 나눠져야 하는 M을 범위로 하는 배열에 구간합을 M으로 나눈 값의 개수를 담는다. 이때, 나머지가 0이면 나누어 ..

시간 복잡도 주어진 문제를 해결하기 위한 연산 횟수. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측함. 시간 복잡도 유형 1. 빅-오메가 (Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 2. 빅-세타 (Θ(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법 3. 빅-오 (O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 처음에는 단순히 입력으로 주어진 문자를 서로의 길이 만큼 반복해서 더한 뒤 대조를 하면 될줄 알았는데 그렇게 하니 메모리초과가 되며 런타임 에러가 발생했다. 그래서 문자열 반복해서 더해서 StringBuilder에 append하여 대조를 했더니 모든 테스트케이스를 통과할 수 있었다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Solution { public static void main(String[] args) throws Exception { Buffere..

10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 (이분 탐색) 단순하게 이분 탐색으로 풀어보려 했더니 중복된 숫자들이 있었다. 그래서 탐색을 할 정렬된 배열에서 찾고자 하는 수가 처음 등장하는 곳과 끝의 길이를 내면 되지 않을까 생각했다. 즉 하한(Lower Bound)값과 상한(Upper Bound)값을 찾으면 되는 것이다. 이분 탐색을 통해 처음 찾고자 하는 곳을 찾고 다시 한번 이분 탐색을 통해 찾고자 하는 값이 마지막으로 나오는 곳을 찾고 상한값에서 하한값을 빼면 ..