문제 https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 풀이 예상 투포인터를 이용해서 startPoint와 endPoint의 차이로 길이를 구한다. 짝수의 길이 = endPoint - startPont - 홀수의 개수 풀이방법 (접근 방법 & 시간복잡도) 1. isOdd[] 배열에 홀수면 true, 짝수면 false 를 넣어준다. 2. count (홀수의 개수 카운트) 가 K 번 나올 때 까지 endPoint를 늘려준다. 3. count가 K개 이고, 다음 숫자가 짝수인 경우 ..
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 예상 투포인터를 이용해서 startPoint와 endPoint의 차이로 길이를 구한다. 풀이방법 (접근 방법 & 시간복잡도) 1. startPoint를 0부터 N까지 늘려간다. 2. 합이 S이상일 때 까지 endPoint를 증가시켜서 sum에 더해준다. 3. startPoint 값을 sum에서 빼준다. 예제를 예시로 들어보면, 10 15 5 1 3 5 10 7 4 9 2 ..
문제 https://www.acmicpc.net/problem/24956 24956번: 나는 정말 휘파람을 못 불어 '유사 휘파람 문자열'인 부분 수열의 개수를 $1\,000\,000\,007(= 10^9+7)$로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 예상 W, H, E 가 나올때 각각 카운트를 해서 공식을 이끌어내서 풀이를 할 수 있을 것 같았다. 앞보다는 뒤에서 보는게 카운트를 하는 것과 W 가 나올 때 마다 계산하기 쉬울 것 같아서 뒤에서부터 봤다. 풀이방법 (접근 방법 & 시간복잡도) 뒤에서부터 E가 나올 때는 e의 개수인 eCount를 하나 증가 해 주고 H가 나올 경우에는 현재까지 eCount로 만들 수 있는 개수를 keep에 저장해 둔다. keep은 이 H에서 만들수 있..
문제 https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net 풀이 예상 백준 1749 점수따먹기풀이 와 같이 2차원 배열의 누적합을 활용해서 3차원으로 늘린 풀이 방법이다. 행렬의 원소의 범위가 1~10이였기 때문에 가능한 풀이이고 2차원과 방법은 똑같고 2차원 배열에 하나를 더 붙혀서 1~10숫자의 카운트를 각각해주면 된다. 풀이방법 (접근 방법 & 시간복잡도) 시간복잡도 => O(N^2) import java.io.Buffere..
문제 https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 풀이 예상 2차원 배열 안에서 누적합을 이용한 풀이 풀이방법 (접근 방법 & 시간복잡도) 2차원 배열 안에서의 누적합은 아래와 같이 구할 수 있다. 주황색 칸을 구하기 위해서 왼쪽, 위쪽 칸을 더하고 왼쪽 위 대각선 칸을 빼주면 된다. 식으로 나타내면 sum[i][j] = num + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]; //본인자리숫자 + 왼쪽칸 + 위쪽칸 -..
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=3 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 예상 W => B => R 순서가 무조건 유지 되어야 하기 때문에 시작 라인(0)은 흰색, 끝 라인(N)은 빨간색으로..
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 예상 앨리스,, 밥.... 누가 이기는건지 처음에 너무 헷갈렸다 1~20 정도까지 누가 이기는지 그려가면서 표를 작성했었는데 전혀 감이 안와서 다른 사람 풀이들을 봤다. 그랬더니 중간에 하나가 잘못 계산을 했어서 규칙이 안보였는데 규칙을 찾았다 ^0^; 1/4/4/16/16/64/64 .. 씩 승리를 번갈아 가면서 한다는 점 풀이방법 (접근 방법 & 시간복잡도) 시간복잡도 => 스터디 사람들 도와줘~~ 💟 import java.io.Buffe..
문제 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 예상 석순과 종유석의 높이를 받을 때마다 해당 높이의 카운트를 늘려주는 것은 최대 20만x50만 번의 작업이 이루어 지기 떄문에 다른 방법을 찾아야 겠다고 생각했다. 그래서 높이에 따른 개수를 저장하고, 누적합을 통해서 구간에 포함되는 장애물의 수를 구한다. 풀이방법 (접근 방법 & 시간복잡도) 예제 입력 1번을 예시로 들면 입력 받았을 때, bottom[] 배열은 이렇게 되어있다. bot..
