CodeDrive

문제:

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 RxC인 격자판으로 나타냈고, 1x1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r,c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r,c)는 r행 c열을 의미한다.

공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r,c)에 있는 미세먼지의 양은 Ar,c 이다.

1초 동안 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.

 - (r,c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.

 - 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.

 - 확산되는 양은 Ar,c / 5 이고 소주점은 버린다.

 - (r,c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)x(확산된 방향의 개수) 이다.

2. 공기청정기가 작동한다.

 - 공기청정기에는 바람이 나온다.

 - 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.

 - 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.

 - 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청저기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력:

첫째 줄에 R, C, T (6<=R,C<=50,1<=T<=1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c(-1<=Ar,c<=1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c 가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력:

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이방법:

크게 두 함수로 구성되어 있다. 미세먼지가 확산되는 것을 나타내는 Spread와, 공기청정기가 작동하는 Clean()으로 구성되어 있었다. 매 초마다 Spread와 Clean이 반복된다.

Spread에서는 확산 될 때, 동시에 모든 곳에서 주변으로 퍼지기 때문에 nextD라는 빈 배열을 만들어서 이 곳에 값을 더하는 방식으로 했다.

Clean에서는 브루트포스 방식으로 진행했다. 공기청정기는 두 개의 인덱스를 차지하게 된다. 윗 부분에서는 반시계방향으로 회전하기 때문에 r의 인덱스가 0일 때, 윗 공기청정기 인덱스일 때, c의 인덱스가 0일 때, c-1일 때 공기청정기의 영향을 받는다.

아랫 부분에서는 시계방향으로 회전하면 r의 인덱스가 아랫 공기청정기 인덱스일때, r-1일때, 그리고 c의 인덱스가 0일 때, c-1일 때 영향을 받는다.

함수를 구성하고 나서 채점을 돌렸는데 Python에서는 시간초과가 발생하고, Pypy에서는 통과했다. 너무 비효율적으로 코드를 짠 것 같다.

문제링크:

https://www.acmicpc.net/problem/17144

문제:

N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

입력:

첫째 줄에 2,000,000 이하의 자연수 N이 주어진다.

출력:

첫 줄에 구하고자 하는 수를 출력한다.

풀이방법:

몫과 나머지가 같다고 가정한 뒤에 역으로 그 자연수 값을 찾도록 하면 된다. 나머지가 나올 수 있는 경우의 수는 N일 때 0~N-1까지 있다. 따라서 몫과 나머지가 같은 수는 i*(N)+i, i는 0부터 N-1까지의 수로 구할 수 있다. 이는 반복문 하나만 사용하면 구할 수 있다.

문제링크:

https://www.acmicpc.net/problem/1834

문제:

어떤 수 X가 주어졌을 때, X의 모든 자리수가 역순이 된 수를 얻을 수 있다. Rev(X)를 X의 모든 자리수를 역순으로 만든는 함수라고 하자. 예를 들어, X=123일 때, Rev(X) = 321이다. 그리고, X=100일 때, Rev(X) = 1이다.

두 양의 정수 X와 Y가 주어졌을 때, Rev(Rev(X) + Rev(Y))를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 수 X와 Y가 주어진다. X와 Y는 1,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 문제의 정답을 출력한다.

풀이방법:

 파이썬에 문자열을 뒤집는 방법은 크게 두가지가 있다. 첫번째는 문자열을 배열로 바꾼 뒤에 reverse로 뒤집고 다시 join을 사용해서 문자열로 만드는 방법이다. 이 방법은 번거로운 작업이 많이 필요하다. 두번째는 슬라이싱의 특징을 이용하는 방법이다. [ : ]와 같이 사용하면 해당 문자열의 전체를 의미하게 된다. 이 때 [ : :-1]와 같이 사용하면 뒤에서부터 해당 문자열의 전체를 가져오게 된다. 즉 문자열을 뒤집게 된다. 따라서 이를 이용해서 문제가 요구하는 조건대로 연산을 진행하면 답을 구할 수 있다.

문제링크:

https://www.acmicpc.net/problem/1357

문제:

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 A,B,C가 빈 칸을 사이에 두고 순서대로 주어진다. A,B,C는 모두 2,147,483,647 이하의 자연수이다.

출력:

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

풀이방법:

 주어질 A,B,C의 값이 매우 크므로 pow 연산을 활용하는 것은 시간초과가 발생하게 될 것이다. 따라서 효율적인 연산이 필요하다. 그러면서 사용하게 되는 것이 모듈러 연산의 분배법칙이다.

 모듈러  X=x1*x2라고 가정하자. 그러면 X mod y = (x1 mod y)*(x2 mod y) mod y 가 성립한다. 이 것과 10^n*10^m=10^(n+m)임을 사용하면 시간복잡도를 O((logN)^2)까지 줄일 수 있다.

 우선 지수를 2의 지수 단위로 분할한다. 이 문제의 예시와 같은 경우 11은 8+2+1로 482는 256+128+64+32+2와 같이 분할할 수 있다. 즉 10^11 mod 12 = (10^8 mod 12)(10^2 mod 12)(10^1 mod 12) mod 12 이고, 10^482 mod 12 = (10^256 mod 12)(10^128 mod 12)(10^64 mod 12)(10^32 mod 12)(10^2 mod 12) mod 12가 된다.

  2의 지수를 사용하는 것에는 이유가 있다. 10^1부터 DP 방식을 사용하면 나머지의 값들도 쉽게 구할 수 있기 때문이다. 10^2 mod 12 = (10^1 mod 12)(10^1 mod 12) mod 12 이고 10^4 mod 12 = (10^2 mod 12)(10^2 mod 12) mod 12 ...와 같이 구하면 된다.

 위와 같이 dp table을 다 채우고 난 뒤에 해당하는 값들만 곱한뒤에 다시 c로 나누면 나머지를 출력하면 된다.

문제링크:

https://www.acmicpc.net/problem/1629

문제:

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

입력:

첫째 줄에 자연수 S(1<=S<=4294967295)가 주어진다.

출력:

첫째 줄에 자연수 N의 최댓값을 출력한다.

풀이방법:

최대한 많은 서로 다른 수를 사용하며 그 합들이 S가 되도록 만들기 위해서는 1부터 차례대로 값을 더하는 것이 가장 많이 사용할 수 있다. 즉 예를 들어 11을 만들기 위해서는 1+2+3+4+1=11과 같이 사용하는 것이 N이 최대가 된다. 하지만 1을 중복해서 사용했다. 그래서 이 1을 4에다가 붙여서 다음과 같이 식을 구성하고 이 것이 최댓값이 되게 된다. (1+2+3+5=11)

 따라서 S를 알 때, 자연수 N의 최댓값을 구하기 위해서 일반화를 할 수 있다. 1+2+ .... + n의 합은 S를 넘지 않는다. 즉 1+2+ .... + n +a =S가 되게 되는 것이다. 이 a를 항상 n에 붙임으로써 N의 최댓값을 구할 수 있다. 즉 1부터 n까지의 합이 S와 근접할 때 N의 최댓값이 된다.

 1+2 + .... + n = ((n+1)*n)/2 이므로 이를 활용해서 m을 추정할 수 있고 이 값을 하나씩 감소시키며 n을 찾을 수 있다.

문제링크:

https://www.acmicpc.net/problem/1789

문제:

두 정수 N과 F가 주어진다. 지민이는 정수 N의 가장 뒤 두 자리를 적절히 바꿔서 N을 F로 나누어 떨어지게 만들려고 한다. 만약 가능한 것이 여러 가지이면, 뒤 두 자리를 가능하면 작게 만들려고 한다.

예를 들어, N=275이고, F=5이면, 답은 00이다. 200이 5로 나누어 떨어지기 때문이다. N=1021이고, F=11이면, 정답은 01인데, 1001이 11로 나누어 떨어지기 때문이다.

입력:

첫째 줄에 N, 둘째 줄에 F가 주어진다. N은 100보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수다. F는 100보다 작거나 같은 자연수이다.

출력:

첫째 줄에 마지막 두 자리를 모두 출력한다. 한자리이면 앞에 0을 추가해서 두 자리로 만들어야 한다.

풀이방법:

N을 입력 받은 뒤에 가장 뒤 두 자리를 00으로 만드는 것으로부터 시작한다. 이후 이 값이 F로 나누어지면(나머지가 0이면) 이 값을 출력하고, 나누어지지 않는다면(나머지가 0이 아니라면) F로 나눈 것의 몫에 1을 더한 것에 F를 곱한 것이 최솟값이면서 나누어 떨어지는 수가 된다. 이 때 한자리면 앞에 0을 추가해줘야 하므로 미리 string으로 바꿔서 이를 방지한다.

문제링크:

https://www.acmicpc.net/problem/1075

문제:

 NxN 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 게임 판의 크기 N(4<=N<=100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력:

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수를 2^63-1보다 작거나 같다.

풀이방법:

 dp를 사용해서 값을 누적시키면서 진행하면 답을 구할 수 있다. 갈 수 있는 경로의 수만 알면 되므로 dp[i][j]로 갈 수 있는 경우의 수를 누적시키면서 n,n으로 진행해나가면 된다. 따라서 시간복잡도는 O(N^2)이 될 것이다. dp[i][j]로 갈 수 있는 방법은 크게 두 가지다. 해당 위치를 기준으로 왼쪽에서 오거나 위쪽에서 오는 경우이다. 해당 칸에서 이동이 가능한지 알아보고 가능하다면 값을 더해주는 방식으로 진행하면 된다.

문제링크:

https://www.acmicpc.net/problem/1890

문제:

풀이방법:

 문자열처리를 해야하는 문제이므로 정규표현식을 사용했다. 정규표현식에서 '\d+'는 숫자를 의미하고, '\D+'를 의미하므로 문자열을 숫자와 숫자가 아닌 것들로 분할하는 작업을 먼저 했다. 문자들을 가져온 배열을 보면 * 과 #이 붙어있는 경우가 있을 수 있으므로 길이로 이를 파악하였다. 길이가 2면 특수문자가 붙어있고, 아니면 문자만 있는 것으로 판단했다. 그 이외에는 해당하는 명령어에 따라서 점수를 부여해주면 된다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/17682

문제:

풀이방법:

 컬럼의 길이가 최대 8이므로 가능한 모든 경우의 조합을 다 따져보아도 문제가 없을 것이라고 생각했다.(최대 2^8=256개이기 때문이다.) 따라서 우선 check 함수를 통해서 유일성을 만족하는지 파악을 했다.

 유일성을 만족하는 조합을 기준으로 서로 비교하면서 최소성을 만족하는지 확인하였다. 이들을 집합이라고 생각한다면 (1)은 (1,2)의 부분집합이 되게 된다. 따라서 set에서 부분집합인지 확인해주는 내장함수는 issubset을 사용해서 부분집합인지 확인하였다. 그리고 해당하는 조합이 있다면 remove를 통해서 제거해줬다.

 그리고 남은 answer의 길이를 구함으로써 후보키의 갯수를 얻을 수 있다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42890

문제:

풀이방법:

 오름차순으로 정렬한 뒤에 1스테이지부터 차례대로 실패율을 구해 나갔다. n+1 스테이지를 구할 때에는 n스테이지까지 실패한 사람들은 포함시키면 안되므로 idx 값을 두어서 포함되지 않도록 하였다. 이렇게 구한 값들을 answer_rate에 dict 형식으로 저장을 한다. dict 타입으로 저장을 하고 items으로 이 값을 가져오면 스테이지에 대한 정보와 그 스테이지의 실패율을 튜플값으로 묶어서 알 수 있기 때문이다. 따라서 실패율을 기준으로 정렬을 하고 출력은 스테이지에 대한 정보만 출력하도록 하면 된다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42889