CodeDrive

문제:

N x M 크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

입력:

첫째 줄에 두 정수 N,M(2<=N,M<=100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력:

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

풀이방법:

 최소의 칸 수를 구해야 하는 문제에서는 DFS가 적합하지 않은 경우가 많다. 따라서 이 문제는 BFS를 사용해서 풀어야 하는 문제다.

BFS(queue)를 사용해서 1이 있는 위치에다가 check에 거리를 할당하며 (1,1)에서 (N,M)으로 가도록 하면 된다. 예제 입력2를 통해 설명하면 다음과 같다.

초기 check 배열은 다음과 같이 모두 0이며 (1,1)에서 출발해야 하므로 0,0은 1으로 할당해두도록 한다. 또한 (1,1)를 queue에 넣어두도록 한다.

queue에서 (1,1)을 빼고 이 값을 기준으로 (1,2)와(2,1)가 1로 이동할 수 있으므로 2로 할당한다. 이 값들을 queue에 넣어준다.

(1,2)와 (2,1)를 빼고 이 값에서는 (2,2),(1,3)이 이동 가능하므로 3으로 할당하고 이 값들을 queue에 넣어준다.

따라서 이 방식대로 계속해서 queue에서 빼고, 넣는 작업을 반복한다

count=5일 때,

count=6일 때,

count=7일 때,

count=8일 때,

count=9일 때,

이렇게 계속하다보면 더 이상 queue에 남아 있는 값이 없게 되는데 이 것이 탐색의 끝을 의미한다. 따라서 탐색을 마치고 난 뒤에 (n,m) 값이 정답이다.

문제링크:

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

문제:

<그림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