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 영역을 뒤집을 수 있는..

문제 문자를 직접 타이핑하는 방법은 s초, 복사&붙여넣기 방법은 t초가 걸릴 때, 같은 말을 n번 반복해서 입력하는데 걸리는 최소 시간을 구하는 문제이다. 풀이 같은 말이 c번 적혀있고 추가로 c번 작성한다고 한다면 (2배로 만든다면) 위의 그림과 같이 s초씩 c번 작성하는 방법과 t초동안 한 번에 복붙하는 방법이 있다. 즉, 최소 시간을 만들기 위해서는 문자를 두배로 만들 때, 두 가지 방법 중 더 적은 시간을 소요하는 방법을 선택해야 한다. 같은 말을 n번 작성하는데 걸리는 시간을 계산할 때, 작성된 글 맨 마지막부터 그리디 알고리즘 방식으로 생각하면 쉽다. 남은 횟수가 홀수일 경우에는 복붙 방법을 사용할 수 없기 때문에 남은 횟수를 1 줄이고 s초를 더한다. 남은 횟수가 짝수일 경우에는 남은 횟수를..