📍문제 링크 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 - 슬라이딩 윈도우 📍문제 풀이 세 수가 일렬로 쭉 내려오는 수열이 있다. 내려올 때, 직선, 대각선으로 내려올 수 있다고 할 때 최댓값과 최솟값을 구하라 /* 1번 라인1 2 3 2번 라인4 5 6 3번 라인4 9 0 1 1 2 3 일 때 각 라인에서 가능한 최대 최소 123 최대123 최소123 2 1 2 3 4 5 6 일 때 각 라인에서 가능한 최대 최소..

📍문제 링크 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 📍알고리즘 분류 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 깊이 우선 탐색 📍문제 풀이 - 0과 1로 이루어진 좌표 평면이 주어질 때, 1은 땅이고 나머지(빈 공간과 0)는 바다이다 - 8 방면으로 연결되면 하나의 공간이라고 할 때, 섬의 갯수를 구하라 - 입력받는 방법이 조금 특이해서 shift로 하나씩 빼서 사용했다 - 1인 좌표에 대해 BFS를 실시하여 큐에 넣..

📍문제 링크 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 📍알고리즘 분류 - 구현 - 시뮬레이션 📍문제 풀이 - 좌표 평면에 미세먼지 분포가 주어진다 - 2 * 1 크기의 공간을 차지하는 공기청정기가 공기를 순환시킨다 - 동시에 미세먼지는 상하좌우로 확산한다 - N 초 후 공간의 전체 미세먼지 총량을 구하라 어려운 구현문제였다.. 1. 좌표 평면의 0열에서 공기 청정기 상부의 좌표 k 를 찾아서 저장하기 2. 순환 기능 구현 - 상하좌우 ..

📍문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - 음이 아닌 정수 N이 주어진다. - 이친수의 조건 1. 11이 2번 등장하지 않음 2. 1과 0으로 만 이루어짐 - N 자리의 이친수가 몇개 존재하는지 갯수를 출력하라 N = 1 일때는 1 N = 2 일때는 10 N = 3 일때는 100 101 이것을 종합해보면, N = i 일 때, i - 1의 이친수 들에 0과 1을 ..

📍문제 링크 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - 자연수 N이 주어질 때, 2 * N 배열에 원소를 채우는 경우의 수를 9901로 나눈 나머지를 구하라 - 원소는 가로나 세로로 붙을 수 없다 - 원소를 하나도 배치하지 않은 경우도 한 가지의 경우의 수로 친다 N =1 일 때의 결과를 N = 2 일 때 이용할 수 있다면, DP로 해결할 수 있다 """ N = 1 1. 0,0 좌표에 사자 배치 OX 2. 0,0 좌표에 사자 no배치 XO 3. no배치 XX ------------ N = 2 N = 1의 경우에다 밑에..

📍문제 링크 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 📍알고리즘 분류 - 누적 합 - 투 포인터 - 슬라이딩 윈도우 📍문제 풀이 수열이 주어지고 1 이상 수열의 길이 이하인 자연수 K가 주어질 때, 수열에서 K연속 숫자들의 합의 최대값을 구하라 이 문제는 간단하지만, 수열의 길이가 10만 까지 가능하기 때문에 O(N^2) 로는 해결할 수 없다 누적 합 (prefix sum) 을 이용하면 O(N) 에 빠르게 해결할 수 있다 1..

📍문제 링크 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 - 누적 합 📍문제 풀이 - 연속된 수열이 주어지고, 1 ~ 3 사이의 자연수 max가 하나 주어진다 - 연속된 수열에서 max 개의 연속하는 수를 3개 만들고, (겹치면 안됨) 그 합이 최대가 되는 수를 구하라 ⭐연속된 수열에서 구간 합을 빠르게 구하기 위해 누적 합 (prefix sum) 배열을 만들고 이용한다 - 예를 들어 1 2 3 ..

배열의 특정 구간에 대한 sum을 반복적으로 계산해야할 때 사용 📍구분 값을 변경하지 않는 경우 (immutable) 값을 변경하는 경우 (mutable) 1차원 prefix sum binary indexed tree (Fenwick tree) segment tree sqrt-decomposition 2차원 summed-area table (integral image) binary indexed tree (Fenwick tree) segment tree sqrt-decomposition 📍예시 (sum) A : array S : sum (계산의 편의상 0부터 시작) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A 1 3 11 6 7 10 14 9 18 16 5 4 2 8 19 S ..