CodeDrive

문제:

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

문제:

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] != Y[i]인 i의 개수이다. 예를 들어, X="jimin", Y="minji"이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

 1. A의 앞에 아무 알파벳이나 추가한다.

 2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력:

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

풀이방법:

문자열을 비교하는 단순한 알고리즘을 사용하면 된다. 알파벳을 추가할 때 앞인지 뒤인지가 중요한 것이 아니라 추가하는 행위자체가 중요한 것이다. 따라서 즉 A와 B가 얼마나 다른지가 중요한 것이다. A를 한칸씩 밀어가면서 일치하지 않을 때마다 count를 하나씩 늘리고 이 것이 최소가 되는 count을 저장해주면 된다.

문제링크:

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

문제:

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 길이 n이 매개변수로 주어질 때 , n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution 함수를 완성해주세요.

풀이 방법:

 되추적 방법을 사용하는 대표적인 예시인 문제이다. 따라서 queens에서는 각 col별로 queen을 배치하는데 우선 promising이라는 함수에서 이전에 배치한 col을 기준으로 해당 인덱스에 queen을 배치할 수 있는지 판단해준다. 모든 방법을 다 판별해주는 방법도 생각할 수 있지만 그럴 경우 n이 커짐에 따라 많은 시간이 발생할 것이다. 따라서 promising이라는 되추적 판단을 해주는 함수로 인해서 많은 시간을 단축 할 수 있었다.

문제 링크:

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