CodeDrive

문제:

<그림1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림2>는 <그림1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력:

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5<=N<=25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0 혹은 1)가 입력된다.

출력:

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

풀이방법:

 이 문제는 크게 두 부분으로 나누어서 풀어야 한다. check에 <그림2>와 같이 배열을 만드는 부분, 그리고 <그림2>를 탐색하며 각 단지번호의 갯수를 세는 부분으로 나누어서 풀었다.

 첫 부분은 dfs를 사용해서 값을 할당했다. <그림1>의 배열을 탐색하면서 값이 1이고 check가 아직 0인(방문을 하지 않은) 값을 만나면 그 값으로부터 dfs를 시작하도록 한다. check에 count 값을 할당하면서 다음 dfs 값으로 이동하였다. 이 때 상하좌우로 이동할 수 있었는데 깔끔하게 이동할 수 있도록 dx와 dy라는 배열을 만들어서 하나의 반복문으로 이동을 간단하게 만들었다.

 이렇게 한 단지를 다 탐색하고 나면 다시 처음상태로 돌아가서 다시 값이 1이고 check가 0인 곳을 찾고, 위와 동일하게 check에 count에 1이 증가한 값들을 할당해주면 된다.

 <그림1>을 모두 탐색하고 난다면 check에 <그림2>와 같이 지도를 얻을 수 있다. 그러면 이 check를 count의 갯수만큼 탐색하며 단지번호의 갯수를 세도록 한다.

문제링크:

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

문제:

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49),65,61,37,58,89,145,42,20,4,16,37, ...}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57,74,65,61}의 네 개의 수가 남게 된다.

입력:

첫째 줄에 A(1<=A<=9999),P(1<=P<=5)가 주어진다.

출력:

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

풀이방법:

 DFS를 사용해서 풀어야 하는 문제이다. check라는 배열을 250000이라고 설정하고(최대 나올 수 있는 값은 9^5+9^5+9^5+9^5 이기 때문이다.) dfs로 하나씩 들어가면서 해당하는 값에 count를 할당한다. 이렇게 계속해서 값을 구하다가 check가 0이 아닌 값을 만난다면 그 값부터는 반복된다는 뜻이므로 그 check의 count에 1을 뺀 값이 정답이 되게 된다.

 이 문제로 예시를 들면 check[57]에 count를 1을 할당. ->check[74]에 2를 할당 -> check[65]에 3을 할당 -> check[61]에 4를 할당 -> check[37]에 5를 할당 -> check[58]에 6을 할당 -> check[89]에 7을 할당 -> check[145]에 8을 할당 -> check[42]에 9를 할당 -> check[20]에 10을 할당 -> check[4]에 11을 할당 -> check[16]에 12를 할당 -> check[37]에는 이미 5가 할당되어 있음. 따라서 57, 74, 65, 61만 남아야 하므로 답은 5-1인 4가 된다.

문제링크:

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

문제:

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열(3,2,7,8,1,4,5,6)을 배열을 이용해 표현하면 다음과 같다. 

또는 Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 [그림1] 과 같이 나타냈다면, 임의의 노드 i에서 다른 노드 p로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프(3,2,7,8,1,4,5,6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클"이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N(2<=N<=1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력:

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

풀이방법:

 DFS를 사용해서 풀 수 있는 문제이다. 1번 노드부터 시작해서 노드를 방문할 때마다 check를 1로 바꾼다. check가 1인 노드를 만나면 dfs를 종료하고 answer를 하나 증가시켜 순열 사이클의 개수를 나타내도록 하였다. 

 처음에는 DFS 함수를 재귀적으로 구현하고 제출했는데 런타임 에러가 발생하게 되었다. 코드를 봐도 런타임 에러가 발생할만한 곳이 없었는데 찾아보니 자체 시스템 상으로 재귀의 최대 한도가 정해져 있는데 이를 넘어가면 런타임 에러가 발생한다고 한다. 따라서 이 한도를 수정해야하는데 sys 모듈에 sys.setrecursionlimit() 라는 함수를 사용하면 재귀의 깊이 한도(?)를 조절 할 수 있다고 한다. 따라서 이 값을 2000으로 설정하고 코드를 다시 제출해 보았는데 통과할 수 있었다.

문제링크:

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

문제:

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

 1. 국어 점수가 감소하는 순서로

 2. 국어 점수가 같으면 영어 점수가 증가하는 순서로

 3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로

 4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로(단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전        순 으로 앞에 온다.)

입력:

첫째 줄에 도현이네 반의 학생의 수 N(1<=N<=100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.

출력:

문제에 나와있는 정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력한다.

풀이방법:

 주어진 조건대로 정렬을 하면 되는 문제이다. 조건이 4개이므로 if를 여러 번 사용하면 정렬할 수 있다. 하지만 python의 sort 함수의 key를 사용하면 한 줄로 줄일 수 있다. sort 와 sorted 내장 함수에 key라는 파라미터가 있는데 이는 어떠한 기준으로 정렬을 할지 고를 수 있는 파라미터이다. 따라서 이 key와 lambda 함수를 잘 사용하면 이 문제처럼 복잡한 조건으로 정렬을 하려 해도 한 줄로 쉽게 정렬할 수 있다.

 'key='를 sort나 sorted의 ()안에 넣어주고 그 뒤에 함수나 기준값을 넣어주면 된다. 이 문제에서는 lambda 함수를 사용했으며 x는 students의 각 원소를 뜻하며 x[0]~x[3]는 이름부터 국어, 영어, 수학 점수를 뜻하게 된다. x: ( 값 ) 과 같이 사용하는데 () 안에 있는 값 순서대로 정렬을 한다. 따라서 국어는 감소하는 순서대로 이므로 -x[1]가 되고, 만약 같다면 그 다음 값인 x[2]를 기준으로(증가하는) 정렬을 하게 된다. 즉 -x[3]은 3번 조건을 , x[0]은 4번 조건을 만족한다.

문제링크:

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

문제:

2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오.

입력:

첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다.

출력:

첫째 줄에 주어진 수를 8진수로 변환하여 출력한다.

풀이방법:

2진수를 8진수로 바꾸는 수학적 방법은 2진수인 수 뒷부분부터 3개씩 끊어가면서 10진수 수로 변환을 하고 이를 이어붙이면 8진수 수가 된다.

즉 이 문제에서는 11001100이라는 예시가 있었을 때 뒤에서부터 3자리씩 끊으면 다음과 같다.

   11/001/100

따라서 이 수를 10진수 수로 변환하면 다음과 같다.

    3/1/4

답은 이 수들을 이어 붙인 314이다.

문제링크:

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

문제:

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 t(1<=t<=100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n(1<n<=100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1000000을 넘지 않는다.

출력:

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

풀이 방법:

조건에 주어진대로 수행만하면 되는 문제다. 주어진 n개의 수 중에 겹치지 않게 2개를 뽑고 그 값의 gcd를 구하고 배열에 더한 뒤에 sum을 하면 구할 수 있다.

문제 링크:

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

문제:

상근이와 선영이가 다른 사람들의 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다.. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", " BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작정하시오.

입력:

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력:

나올 수 있는 해석의 가짓수를 구하시오. 정잡이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

풀이방법:

하나의 숫자에 대해 두가지 경우가 있을 수 있다. 한자리 수 일 경우 (1~9, A~J) ,두자리 수일 경우 (10~26,K~Z)이다. 따라서 d[i]는 d[i-1] 와 d[i-2] 값을 합친 값임을 알 수 있다. (물론 조건에 맞는것만) 따라서 조건에 맞을 때마다 값을 더해주면 되는데 이 때, 몇 개의 예외처리를 해주면 된다.

 우선 index가 맨처음일 때, 두 자리일수가 없다. 따라서 이 경우에는 continue로 넘어간다.

 또한 i-1이 0일 때, 01,02,.....와 같은 경우는 두 자리수가 아닌 한자리수이다. 따라서 고려 대상이 아니다.

더하면서 매번 mod 값으로 나눠주면 쉽게 구할 수 있다.

문제링크:

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

문제:

3 x N 크기의 벽을 2x1,1x2 크기의 타일로 채우는 경우의 수를 구해보자.

입력:

첫째 줄에 N(1<=N<=30)이 주어진다.

출력:

첫째 줄에 경우의 수를 출력한다.

풀이방법:

홀수인 경우는 만들 수 없으니 제외를 하고 각 n은 이전 값의 3배에다가 더 이전의 값들의 2배씩을 더한 값들이다.

문제링크:

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

문제:

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=3^2+1^2+1^2(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=2^2+2^2+1^2+1^2+1^2(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 "11은 3개 항의 제곱수 합으로 표현할 수 있다."라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N이 주어진다. (1<=N<=100,000)

출력:

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

풀이 방법:

동적 계획법으로 쉽게 풀 수 있는 문제이다. 11은 다음과 같이 표현 될 수 있다. 11-3^2=1^2+1^2 와 11-2^2=2^2+1^2+1^2+1^2 와 같이 생각할 수 있다. 따라서 모든 수들이 이와 같이 증가한다고 가정을 하고 최소항을 사용한 경우에만 업데이트도록 해서 최소개수를 나타내도록 하였다.

문제 링크:

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

문제:

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

•   문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있따.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이 때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력:

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력:

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

풀이방법:

 풀 수 있는 방법은 다양하지만 시간 제한이 빡세게 걸려있던 문제였다. 따라서 일반 string에서 제공해주는 함수인 replace를 사용한다면 시간제한에 막혀서 해결하지 못할 것이다.

최대한 시간복잡도를 적게하면서 풀 수 있는 방법이 무엇일까 생각해보았는데 stack을 이용하는 것이였다. stack은 넣는 것과 빼는 것이 O(1)로 시간복잡도가 적게 발생한다. 또한 폭발 문자열만큼 stack의 끝 부분을 계속해서 확인하면 실시간(?)으로 뺄 수 있으므로 번거롭게 검토를 하는 과정또한 불필요할 것이다.

 따라서 string을 하나씩 answer라는 stack에 넣고 끝 부분이 bomb과 같아질 때마다 그 부분을 빈 리스트로 만들어줌으로써 pop과 같은 기능을 하도록 했다. 이 과정을 모두 마친 뒤에 answer라는 배열에 값이 남아있다면 이를 join으로 이어주고 비어있다면 남아있는 문자가 없는 경우이므로 FRULA를 출력하도록 하였다.

문제링크:

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