1. 문제 0과 1로 구성된 길이가 N인 수열 이 수열에서 최대 k번 0을 1로 변경할 수 있다. 최대 k번 변경을 해서 1로만 구성된 최대 길이의 연속 부분수열을 찾는 프로그램을 작성하시오. 최대 길이를 출력하시오. 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 이면 맨 마지막 두개 0을 1로 바꿔서 길이가 8인 연속부분수열을 만들 수 있으므로 최대 길이는 8이다. 2 - 1. 나의 풀이 1. lt와 rt 설정하고 반복문의 조건은 rt가 수열의 길이보다 작을때 까지 2. arr[rt]가 0 이면 count++한다 (count는 지금까지 0을 1로 변환한 회수이고 k보다 작아야한다.) 3. 만약 count > k이면 거기까지의 1로면 구성된 연속부분수..

1. 문제 연속된 자연수의 합 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하시오. 만약 N = 15이면 7 + 8, 4 + 5 + 6, 1 + 2 + 3 + 4 + 5 와 같이 총 3가지의 경우가 존재 2 - 1. 나의 풀이 반복문의 i 를 언제까지 돌리는지를 고민했다. N을 합으로 표현하므로 N/2 + 1까지 확인 하면 된다. (15이면 i가 8일 때 까지, i 이하의 숫자들을 누적합하고 뺄 것임) 1. sum에 누적합을 한다. 2. sum이 N보다 크면 lt 값을 sum에서 빼고 lt++한다. 3. sum이 N이면 count++ 하고 lt 값을 sum에서 빼고 lt++ 한다. 굳이 배열을 사용하지 않음. 즉, 4번 문제와 95% 비슷한 문제이고 반복문을 ..

1. 문제 N개의 수로 이루어진 수열이 주어진다. 이 수열에서 연속부분 수열의 합이 M이 되는 경우가 몇 번인지 구하시오. 2 - 1. 나의 풀이 결론: 풀지 못함 투 포인터로 풀려고 LT, RT를 설정했다. 반복문을 설정하는 과정에서 꼬였고, 애초에 로직을 잘못 생각했다. 즉, 내가 생각한대로 코드가 짜여졌어도 실패했을 것이다. 3 - 1. 강의 풀이 1. 투포인터를 설정했다. 2. 누적합 변수 sum에 저장을 계속한다. 3. sum과 m 이 같으면 (1) count를 증가 (2) sum에서 arr[lt]를 빼고 lt 값을 다음으로 넘긴다. 4. sum이 m 보다 크면 (1) sum에서 arr[lt]를 빼고 lt 값을 다음으로 넘긴다. 3번과 4번을 말로 풀어볼 때 같으면 이라는 조건 때문에 if로 접..

1. 문제 N일 동안의 매출 기록을 가지고 K일 동안의 최대 매출액이 얼마인지 구하시오 만약 12 15 11 20 25 10 20 19 13 15 가 있다면 11 20 25 로서의 3일간의 매출이 가장 높다. 2 - 2. 나의 풀이 첫번째 풀이 시도 1. k일 간의 매출을 구하는 메서드 (for문 사용) 2. 0 ~ n - k -1일 만큼의 k일 뒤 매출을 최댓값을 갱신하기 (for 문 사용) 2중 for문의 사용으로 시간 복잡도가 N^2 로서 시간 초과가 나서 오답처리 됐다. 두번째 풀이 시도 (Sliding Window에서 힌트를 얻음) 위 예시로 설명하자면 1. 12 15 11 같이 k 일간의 최대 매출액을 구한다. 2. 다음날 매출 값을 더하고 가장 빠른 날의 매출 값을 뺀다. for(int i ..

1. 문제 두 배열의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하자. 2 - 1. 나의 풀이 투 포인터를 사용하지 않았다. 1. 입력 값을 Set에 저장한다. 2. Set의 교집합 메서드 retainAll()을 사용한다. 3. Collections.sort() 를 사용해 오름차순 정렬한다. 2 - 2. 나의 코드 import java.util.*; public class twoPoint02 { public static ArrayList solution(Set a, Set b) { a.retainAll(b); ArrayList answer = new ArrayList(a); Collections.sort(answer); return answer; } public static void mai..

1. 문제 두 배열을 합치고 정렬하면 된다. 2 - 1. 나의 풀이 그냥 새 배열 만들어서 합치고 정렬하면 될거같긴 한데 제목이 투 포인터 알고리즘이라 먼저 강의를 보기로 했다. 3 - 1. 강의 풀이 1. 각 배열의 포인터 p1, p2를 만들어서 포인터가 가리키는 배열의 값을 비교한다. 2. 값이 작은걸 새 리스트에 넣고 해당 포인터를 ++ 한다. 3. 반복문은 p1이나 p2 중 하나가 기존 배열의 크기에 달하면 종료한다. while(p1 < n && p2 < m) 4. 첫 반복문이 끝나면 p1이나 p2중에서 값이 남은 배열을 찾아 새로운 리스트에 넣는다. 3 - 2. 강의 코드 import java.util.ArrayList; import java.util.Scanner; public class tw..