0과 1의 쉼터

문제https://www.acmicpc.net/problem/2583풀이K개의 직사각형을 제외한 나머지 영역의 개수와 넓이를 구하는 문제다.우선 문제의 예제를 살펴보자.K개의 직사각형에 대해 표시하면 다음과 같다. 왼쪽아래 좌표와 오른쪽위 좌표가 주어지는데 그림을 회전시켜보자.일반적인 배열의 논리적 표현과 같다.그러면 사각형의 넓이는 어떻게 구할까?전체적으로 행과 열을 축소시키면 된다.즉, 이 문제에서 다룰 범위는 M, N에 대해 (0, 0) ~ (N - 1, M - 1)가 된다.K개의 좌표를 입력받아 블럭표시를 해주자.이제 블럭( BLCOK )이 아니고, 방문한적 없는( EMPTY )영역들에 대해 BFS를 진행하면된다.bfs(i, j)는(i, j)에서 bfs를 하고, 하나로 연결된 영역의 넓이를 반환한..

문제https://www.acmicpc.net/problem/17071풀이수빈이와 동생이 각각 N, K에서 이동할 때 몇 초 후에 서로 만날 수 있는지 계산하는 문제다.수빈이는 다음과 같이 움직일 수 있다.X - 1X + 12X동생은 다음과 같이 움직일 수 있다.N + KK는 경과 시간이자. 동생이 움직일 수 있는 거리를 의미한다. 풀이에서는 step으로 표현하겠다.만약 N == K인 경우 수빈이와 동생은 제자리에서 만나므로 탐색이 불필요하다. 걸린 시간은 0초다.bfs로 N부터 탐색을 시작하자.큐가 비어있거나, k(동생의 이동 위치)가 500,000이하라면 탐색을 계속해야 하므로 동생의 이동거리부터 계산하며 조건식에 포함시켜주자.본격적으로 풀이를 하기전에 시간복잡도에 대해 생각해보자.수빈이는 X - 1..

문제https://www.acmicpc.net/problem/28288풀이가로, 세로가 5 * N으로 이루어진 일정을 참고해, 각 열에 존재하는 'Y'의 비율 가장 많은 요일을 출력하는 문제다.만약, 각 일정이 가지는 Y의 수가 동일한 경우 ','를 구분자로 같이 출력해주면 된다.우선, 문자열 결합을 쉽게 하기 위해 StringJoiner를 사용했다.이후 입력받은 char 배열에 대해 각 열에 존재하는 Y의 개수를 cnt 배열에 기록해주자.동시에 최대 개수를 따로 기록해주자.이제 cnt 배열에서 기록한 최대 개수와 동일한 개수의 Y가 존재하는 일정을 구분자와 결합해 출력하면 된다.소스코드보기

문제https://www.acmicpc.net/problem/2482풀이바텀업보다 탑다운 방식으로 접근하면 쉬워지는 문제다. 원형을 이루는 N개의 색상환 표에 대해 인접하지 않은 색을 K개 선택하는 경우의 수를 구해야 한다.경우의 수가 너무 커지지 않게 1e9 + 3으로 나눈 나머지를 출력해야 한다. dp[N][K] : N개의 색상에 대해 인접하지 않는 K개의 색을 선택하는 경우의 수문제를 단순화해보자. 다음이 성립한다.dp[N][1] = Nif K > N / 2, dp[N][K] = 0문제에서 주어진 그림을 예시로 설명하겠다.우선 빨강색(N번째)을 선택해보자.N번째 색을 선택할 때, 인접한 N - 1번(다홍색)은 선택할 수 없다. N - 2번(주황)을 선택해야하고, 이 때 K - 1개의 색을 선택하면 ..

PS 문제집을 따라 푸는 분들을 위해 제작한 노션 페이지 입니다.기존 또는 앞으로의 PS에 대해 문제집이 존재하는 경우 아래의 노션 페이지에서 관리할 예정입니다.감사합니다. https://held-sparrow-180.notion.site/164c96bf505e807b957cf4062faabdc1?pvs=74

문제https://www.acmicpc.net/problem/2011풀이대문자 알파벳을 1 ~ 26으로 암호화한 문자열에 대해 해석 가능한 경우의 수를 출력하는 문제다.우선 주어진 입력의 유효성부터 판별해보자.입력이 0인 경우 암호를 해석할 수 없다. 0을 출력하고 종료하자. 이제 점화식을 세워보자.dp[i] : i번째 까지 해석 가능한 경우의 수N이 1의 자리인 경우, dp[1] = 1탐색 대상의 수( N[i - 1] )가 0보다 크다면, 기존 경우의 수만큼 가질 수 있다. dp[i] = dp[i - 1]N[i - 2], N[i - 1]로 이루어진 두 자릿수가 10 이상, 26이하라면, 두 수를 하나의 수로 볼 수 있다. dp[i] = (dp[i] + dp[i - 2]) % MOD소스코드보기

문제어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.예를 들어, {1,1,5}는 {3,1,4,1,5,9}의 부분 수열이지만, {1,5,1}의 부분 수열은 아닙니다.또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.길이가 0인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.양의 정수로 이루어진 길이가 N인 수열 {A1,⋯,AN}이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 M인 수열 {B..

문제은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S1,S2,⋯,S, S_2, S_N번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a$a$개, 뒤에서 b$b$개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b번 과일, 총 N−(a+b)$N-(a+b)$개가 꽂혀있는 탕후루가 됩니다. (0≤a,b; a+b이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가..

문제오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  visited[R] 입력첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ ..

문제오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 만들어 지는 트리를 너비 우선 탐색 트리라고 하자. 너비 우선 탐색 트리에 있는 i번 노드의 깊이(depth)를 di라고 하자. 시작 정점 R의 깊이는 0이고 방문 되지 않는 노드의 깊이는 -1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 i번 노드의 방문 순서를 ti라고 하자. 시작 정점의 방문 순서는 1이고 시작 정점에서 방문할 수 없는 노드는 0..