CodeAngie

문제 초기 유성 위치 정보가 주어졌을 때, 한 덩어리의 유성이 땅위에 떨어졌을 때의 모습을 출력하는 문제이다. 유성은 "X", 땅은 "#", 공기는 "."으로 주어진다.. 유성은 가장 위에 존재하며, 맨 밑 줄은 모두 땅이다. 그리고 땅 위에 공기층이 적어도 1칸 존재한다. 유성은 수직으로 낙하하며, 유성과 땅의 원형은 변하지 않는다. 풀이 열 별로 유성과 땅 사이의 거리의 최솟값을 구하고 해당 거리만큼 유성만 이동시킨 모습을 출력해야한다. 열 별로 유성과 땅의 거리는 상단(0)에서부터 가장 먼 유성(meteor)과 가장 가까운 땅(i) 사이의 거리이다. 모든 열을 탐색하면서 유성(X)이 나타났을 땐 meteor 값을 업데이트하고, 최초로 땅을 만났을 때 meteor값과 i값 사이의 거리를 도출하여 (i..

문제 n*n 크기의 새 집이 있다. 집 수리를 위해 파이프를 옮겨야 하는데, 파이프는 무겁기 때문에 밀어서 이동시켜야 한다. 파이프는 2개의 연속된 칸을 차지하는 크기이며 3가지 방향으로 회전이 가능하다. 파이프를 밀 수 있는 방향은 →, ↘, ↓ 방향 총 3가지가 있으며, 회전은 45도만 가능하다. 따라서 다음 그림과 같이 가로일 때 2가지, 세로일 때 2가지, 대각선일 때 3가지가 있다. 또한 벽(1)으로는 파이프를 이동시킬 수 없다. 가장 처음에는 파이프가 가로 방향으로 왼쪽 상단에 위치해 있다. 파이프의 한쪽을 (n,n)으로 이동시키는 방법의 개수를 구하여라. 풀이 DP를 사용해 문제를 풀 수 있다. 마지막 위치(n,n)에 파이프가 도달할 수 있는 경우의 수 문제를 (i,j)에 파이프가 도달할 수..

문제 n가지 종류의 동전이 있다. 각 동전의 가치가 제시될 때, 그 가치의 합이 k원이 되도록 하는 경우의 수를 구하는 문제이다. 이때 순서가 달라도 구성이 같다면 같은 경우의 수이다. 풀이 이 문제는 dp를 사용해 풀 수 있다. 가치의 합이 k원(1 ≤ k ≤ 10,000)이 되도록 하는 경우의 수 문제를 나누어 가치의 합이 y(1 ≤ y ≤ k)가 되도록 하는 경우의 수를 구하는 부분 문제로 볼 수 있다. 동전 x1을 사용하여 y가 될 수 있는 경우가 성립하는지 확인하는 것이다. 다시 말해 y - x1을 만들 수 있는 조합이 있다면 해당 경우의 수만큼 x1을 가지고 y값을 만들 수 있다. 이를 통해 다음과 같은 식을 세울 수 있다. dp[y] = dp [y] + dp [y-x1] 알고리즘 dp 리스트..

문제 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번으로 돌아..