CodeAngie

문제 S의 문자들을 골라 T를 만들 수 있다. S에서의 순서대로 이어 붙여 새 문자열을 만드는 것을 반복하여 만들 수 있는 T의 최대 개수를 구하는 문제이다. 풀이 S에서의 순서가 유지돼야 함을 유의한다. S문자열에서 차례대로 문자를 살펴보며 T를 만들 수 있는 개수를 별도의 리스트에서 셀 수 있다. 예를 들어 S가 adabccb 이고 T가 abc일 때, 다음과 같이 셀 수 있다. T에 해당하는 알파벳이 순서대로 개수가 확보되어 있는지 확인할 수 있는 리스트를 생성한다. S의 1번째 a 문자는 T에 포함되며 이전 문자의 개수가 무한으로 현재 문자(a) 개수보다 많기 때문에 현재 문자에 1을 더한다. 2번째 문자인 d는 T에 포함되지 않으므로 넘어간다. 3번째 문자인 a는 첫번째와 마찬가지이기 때문에 a에..

문제 0과 1로만 이루어진 행렬 A,B가 있다. 이때 행렬 A를 B로 바꾸는데 필요한 최소 연산 횟수를 구하는 문제이다. 행렬 변환 연산은 3*3 부분 행렬에 있는 모든 원소를 0은 1로 1은 0으로 바꾸는 것이다. 만약 바꿀 수 없다면 -1를 출력한다. 풀이 N*M 행렬을 모두 순회하면서 (i,j)값이 A와 B가 다른 경우, A의 (i,j)부터 3*3 부분행렬을 뒤집어 (i,j)값이 동일하도록 바꾸어 준다. 이때 (i,j)를 시작점으로 3*3 부분행렬을 뒤집어주는 이유는 앞의 이미 B와 동일한 부분은 건들지 않으면서 뒤의 다른 부분은 다시 뒤집을 수 있기 때문이다. 가능한 모든 부분행렬을 한번씩 살펴봄으로써 뒤집어야하는 최소 횟수를 구할 수 있다. 알고리즘 for문을 통해 3*3 영역을 뒤집을 수 있는..

문제 모눈종이 위에 k개의 직사각형을 그릴 때, 직사각형이 그려지지 않은 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 m = 5, n = 7 인 모눈종이 위에 3개의 직사각형을 그렸을 때, 다음과 같이 3개의 영역으로 나누어질 수 있다. 각각의 넓이는 1, 7, 13이다. 이와 같이 직사각형에 포함되지 않는 분리된 영역의 각 크기를 오름차순으로 출력하는 문제이다. 풀이 먼저 주어진 직사각형을 모눈종이 영역에 표시한다. 이때 본 문제에서는 상하좌우 방향을 유의해야 한다. 여기서는 직사각형이 차지하는 공간이 중요한 부분임으로 임의로 row를 m, col를 n으로 보고, 왼쪽 아래 꼭짓점의 x1, y1좌표값과 오른쪽 위 꼭짓점의 x2, y2좌표값을 왼쪽 위, 오른쪽 아래로 가정하였다. (편의상 상하..

문제 로봇 청소기의 위치와 방향 정보, 방의 상태 정보가 주어졌을 때, 작동을 멈출 때까지 로봇 청소기가 청소하는 영역의 개수를 구하는 문제이다. 방은 n*m 크기이며, 가장 북서쪽 칸의 좌표가 (0,0), 남동쪽 칸의 좌표는 (n-1, m-1)이다. (i, j)가 0인 경우 청소되지 않은 칸이며, 1인 경우는 벽을 의미한다. 로봇청소기의 작동법은 다음과 같다. 현재 칸이 청소가 안되어 있다면 청소한다. 주변 4칸 모두 깨끗한 경우, 바라보는 방향을 유지한 채 한 칸 후진하고 1번으로 돌아간다. 만약 뒤쪽이 벽이라면 작동을 멈춘다. 주변 4칸 중 청소되지 않은 칸이 있는 경우, 반시계 방향으로 90도 회전한다. 바라보는 방향을 기준으로 앞쪽이 청소되지 않은 칸이라면 앞으로 한 칸 이동한다. 1번으로 돌아..

문제 x와 k가 주어졌을 때, 다음 식을 만족하는 k번째 y를 구하는 문제이다. x + y = x | y 여기서 |는 비트 연산자 OR를 의미한다. 풀이 x + y와 x | y가 같다는 것은 2진수로 바꾸었을 때, 1의 위치가 서로 다르다는 것을 의미한다. 예를 들어 x가 5(101) y가 2(10)이라면 101 + 10 = 101 | 10 = 111로 같다. 이때 y를 구하는 것임으로 x를 기준으로 y를 설명하자면, x가 1이면 y는 0을 가지고 x가 0일 때 y는 1 혹은 0을 가질 수 있다는 것이다. k번 째 y는 1 혹은 0이 들어가는 자리를 조절하여 구할 수 있다. 첫 번째 y는 x가 0인 곳에 1(1)이 들어가면 되고 두 번째 y는 x가 0인 곳에 2(10)가 들어가면 된다. 위의 그림에서 검..

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 풀이 DP를 사용하여 LIS를 구하는 기존 문제에 부분 수열의 길이뿐만 아니라 부분 수열을 요소까지 출력하는 문제이다. 따라서 증가하는 부분 수열의 요소를 담는 것을 함께 구현해야 한다. 증가하는 부분 수열의 요소를 담는 리스트를 생성하고 dp가 증가할 때 함께 업데이트 되도록 한다. 알고리즘 n과 a 수열을 입력받는다. 1로 초기화된 dp를 생성한다. 부분 수열의 요소를 담을 b 리스트를 생성한다. A 수열에서 뒤의 요소가 앞의 요소보다 크고 부분 수열의 길이도 더 길어질 때, 부분 수열의 길이를 업데이트 하면서 부분 수열의 요소도 업데이트 해준다. 가장 긴 부분 수열의 길이를 찾아 출력하고, 해당 위치와 동일한 부분 수열의..

문제 n개의 1차원 숫자 배열이 주어졌을 때, 연속된 부분합이 m으로 나누어 떨어지는 경우의 수를 구하는 문제이다. 풀이 부분합을 m으로 나누었을 때 나누어 떨어지는지가 문제임으로 나머지끼리의 연산을 통해 문제를 풀 수 있다. 특히 1차원 부분합은 누적합의 뺄셈을 통해 구할 수 있음으로 $ partSum = prefixSum[j] - prefixSum[i]$ $( i < j ) $ 나머지가 같은 누적합의 뺄셈 계산을 통해 m으로 나눈 나머지가 0이 되는 부분합을 구할 수 있다. 부분합을 구할 때는 항상 뒤에 위치한 j번째 누적합에 i번째 누적합을 빼야한다. (i < j) 즉, 나머지의 수가 같은 누적합의 조합을 통해 나머지가 0이 되는 부분합의 경우의 수를 구할 수 있다. $_nC_2 = \frac{n ..