CodeDrive

문제:

어떤 수 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

문제:

풀이방법:

시간단위로 값을 출력하는 HOUR를 사용해서 시간대를 표현하도록 한다. HOUR를 사용하면 2019-10-2 09:35 -> 9

2019-10-3 09:59 -> 9 와 같이 변환시켜준다. 따라서 이를 기준으로 GROUPBY를 하고 갯수를 세준다. 또한 9시부터 19시까지라고 시간이 정해져 있으므로 이에 대한 조건을 HAVING으로 넣어주도록 한다.

문제링크:

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

문제:

자연수 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

문제:

풀이방법:

 HAVING 절을 사용하는 예제이다. HAVING절은 WHERE절과 비슷하게 조건을 걸어줄 수 있다. 하지만 WHERE절에 조건을 걸 때에는 제약이 없지만 HAVING절은 GROUPBY에 사용한 컬럼에 대해서만 조건을 걸어 줄 수 있다. 따라서 NAME에 대해서 GROUPBY를 걸어주고 count가 1보다 크다는 조건을 걸어서 두 번 이상 쓰인 이름을 파악한다.

문제링크:

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

문제:

서로 다른 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

문제:

풀이방법:

NULL이라는 값을 다른 값으로 전부 바꿔야 하는 문제이다. NULL이라는 값을 다른 값으로 바꿔주는 함수가 NVL인줄 알고 문제를 풀었다. 그런데 오류가 발생해서 알아보니 NVL은 Oracle에서 지원하고, MySQL에서는 isnull이라는 함수라고 한다. 

 따라서 isnull(column, 채울값)과 같이 사용하면 column에 있는 null 값을 채울 값으로 전부 바꿔준다.

문제링크:

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

문제:

두 정수 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

문제:

풀이방법:

특정한 분류를 기준으로 값들을 묶어야 할 때 GROUPBY를 사용한다. GROUPBY절을 사용하면 이 절에 사용한 컬럼만을 SELECT절에 사용을 해야하며 COUNT와 같은 내장함수는 이 컬럼을 기준으로 작동한다. 따라서 GROUPBY ANIMAL_TYPE을 사용했으므로 SELECT에 ANIMAL_TYPE만을 사용해야 하며 COUNT도 CAT과 DOG의 수를 세어준다.

문제링크:

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

문제:

 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

문제:

풀이방법:

중복을 제거해주는 명령어인 DISTINCT를 사용해야 하는 문제이다. 우선 NULL인 경우는 집계하기지 않으므로 WHERE 조건절을 통해서 NULL이 아닌 값을 걸러내고 DISTINCT NAME을 통해서 중복되는 값을 지우고 이를 COUNT 하는 방법으로 진행했다.

문제링크:

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