1. 문제 2. 접근법처음엔 누적합 방식으로 접근하려고 했지만 감이 안잡혀 가장 생각나는 슬라이딩 윈도우 방식을 사용했다. [슬라이딩 윈도우를 사용하여 최소 고장난 신호등 개수 계산] for 루프를 사용하여 구간을 오른쪽으로 한 칸씩 이동하면서 각 구간의 고장난 신호등 수를 계산새로운 요소를 더하고, 이전 요소를 뺀다현재 구간의 고장난 신호등 수를 min_count와 비교하여 최소값을 갱신 3. 코드package week08;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Baek14465 { public ..

1. 문제  2. 접근법입력1번째 줄 : N, M2번째 줄 : N+1 크기의 배열 값3번째 줄 이후 : 1~3구간의 합, 2~4구간의 합, 5~5 구간의 합 누적합 알고리즘은 누적 합 배열을 만들고 원하는 구간의 값을 출력하는 것이 편하다. [기본 배열]012345054321 [누적 합 배열]012345059121415 1~3구간의 합은5 + 4 + 3 = 12이다.출력하기 위해서는 누적합 배열에서 [3] - [1-1] = 12 값을 출력 2~4 구간의 합은 4 + 3 + 2 = 9이다.출력하기 위해서는 누적합 배열에서 [4] - [2-1]  = 14 - 5 = 9  따라서 i, j로 취급하여누적합배열[i] - 누적합배열[j-1]을 하면 원하는 값이 나온다. 3. 코드package week08;impor..

1. 문제 2. 접근법배열 구간에서 특정 값이 나올 경우의 수를 구하는 문제이므로 투포인터 문제이다.A 배열에 1 1 1 1값들을 저장한 후Start_Pointer와 End_Pointer를 만들고 1. 현재 값이 M 값보다 같거나 클 경우 Start_Pointer를 뺀 후 증가시킨다.2. End_Pointer가 배열의 끝에 도달할 경우 종료3. 현재 값이 M 값보다 작거나 같을 경우 End_Pointer를 더한 후 증가 시킨다.4. 현재 값이 M 값과 같을 경우 count ++를 해준다.    3. 코드package week08;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import ja..

1. 문제 2. 접근법1. 배열을 [n+1][m+1] 만큼 선언해준다.2. 배열에 값을 채운다.3. K개 값을 받는다.4. x1,y2 ~ x2,y2의 값을 구한다. 01231124281632 ex] (1,1) 부터 (2,3)까지 합을 구한다.for(int i = x1; i 3. 코드package week08;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Baek2167 { public static void main(String[] args) throws IOException { Buffered..

1. 문제2. 접근법마리오는 받은 점수의 합을 최대한 100에 가깝게 만든다고 한다.하지만 100에 가까운 수가 2개라면 ex) 98, 102 마리오는 큰 값을 선택한다. 1. 반복문으로 1~10까지 sum에 점수를 더한다.2. if(sum > 100)이 되면3. 100 - (sum - mario[i]) 3. 코드package week08;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Baek2851 { public static void main(String[] args) throws IOException { BufferedReader buffered..

1. 문제  2. 접근법알고리즘 순서1. N 값 받기2. 크리보드의 4가지 역할을 사용하여 1...n번 눌렀을 때 dp배열에 최대 값을 저장3. dp[N] 값 출력 경우의 수 확인N = 1A (1) N = 2AA (2) N = 3AAA (3) N = 4AAAA (4) N = 5AAAAA (5) N = 6AA(전체선택)(복사)(붙여넣기)(붙여넣기) : AAAAAA (6)AAA(전체선택)(복사)(붙여넣기) : AAAAAA (6)AAAAAA (6) N = 7A (전체선택)(복사)(붙)(붙)(붙)(붙) : AAAAA (5)AA (전체선택)(복사)(붙)(붙)(붙) : AAAAAAAA (8)AAA (전체선택)(복사)(붙)(붙) : AAAAAAAAA(9)AAAA (전체선택)(복사)(붙여넣기) : AAAAAAAAA(8..

구간 합 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.코딩 테스트에서 사용 빈도가 높으니 꼭 알아야 한다.구간 합의 핵심 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다.배열 A가 있을 때 합 배열 S를 구하는 공식S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i] // A[0] 부터 A[i]까지의 합합 배열 S를 만드는 공식S[i] = S[i-1] + A[i]i에서 j까지 구간 합 구하는 공식S[j] - S[i-1]A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]S[1] = A[0] + A[1]S[5] - S[1] = A[..

배열배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다.배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다.배열의 특징인덱스를 사용하여 값에 바로 접근할 수 있다.새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.구조가 간단하므로 코딩 테스트에서 많이 사용한다.리스트값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다.노드는 컴퓨터 과학에서 값, 포인터를 쌍으로 갖는 기초 단위를 부르는 말이다.리스트의 특징인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순..