Sujin's Log Sujin's Log

문제 N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요. 만약 N=8, M=6이고 수열이 다음과 같다면 1 2 1 3 1 1 1 2 합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다. 또 이중 for문을 돌면서 풀이하면 쉽겠지만 그렇게 되었을 경우 시간복잡도가 O(N^2)가 되기 때문에 만약 N이 0~100000000 M도 0~1000000정도 되는 경우에는 엄청난 크기가 되어버린다. 그래서 저번에 배웠던 슬라이딩 윈도우(https://suucong.tistory.com/74)알고리즘과 투포인터(https://suucong.tistory.com/7..

문제 12 15 11 20 25 10 20 19 13 15 와 같은 N개의 원소를 가지고 있는 배열과 변수 K가 주어졌을 때 연속된 K개의 합중에서 가장 큰 값을 구해라 예시 입력 10 3 12 15 11 20 25 10 20 19 13 15 예시 입력의 첫번째 수는 N개의 배열을 줄것이다라는 것이고, 두번째 수는 K를 주는 것이다. 예시 출력 56 처음에 내가 짰던 알고리즘은 이중 for문을 사용하였다. 그랬더니 또 Timeout Error가 발생하였다. 나는 이중 for문을 이용해도 시간복잡도가 O(N)일거라고 생각하였다. 저 예시 입력의 경우에는,,, 생각해보면 만약 N이 100000인데, K가 60000이다? 그러면 시간복잡도는 거의 O(N*N)이 되어버린다.. 그래서 타임아웃 오류가 발생하였던 ..

문제 A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요. (각 집합안의 원소는 중복되지 않는다.) 입력 예시 5 1 3 9 5 2 5 3 2 5 7 8 출력 예시 2 3 5 일단 내가 짠 코드는 이중 for문을 이용하여 n과 m이 각 리스트의 원소의 수라고 하였을 때 시간복잡도가 O(n*m)이었다. 그랬더니 리스트별로 데이터가 각 30000개일 경우 타임아웃 오류가 났다. 제한이 1000ms인데 1700ms인가.. (머쓱..) 투포인터 알고리즘을 이용한다면 시간복잡도가 O(n+m)이 되게 된다. 이 방법으로 타임아웃 에러를 해결할 수 있었다. 이중 for문 import java.util.ArrayList; import java.util.Scann..