CodeDrive

문제:

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력:

첫째 줄에 정수 N, r, c가 주어진다.

출력:

r행 c열을 몇 번째로 방문했는지 출력한다.

풀이방법:

시간 제한이 생각보다 많이 빡세기 때문에, 분할 정복을 사용하더라도 좀 더 효율적인 방법이 필요하다. 따라서 r, c 좌표를 통해서 해당 영역으로 찾아들어가는 방식을 사용하도록 한다.

모든 영역은 2^N-1 영역으로 4등분하며 순서대로 방문하기 때문에 r과 c가 이렇게 나눈 영역에서 어느 곳에 속하는지 알면 된다.

우선 나눠지는 순서대로 왼쪽 위를 0번째, 오른쪽 위를 1번째, 왼쪽 아래를 2번째, 오른쪽 아래를 3번째라고 하자

 1. 0번째 영역에 속하기 위해서는 r과 c가 모두 2^(N-1)보다 작아야 한다. 그리고 0번째 영역의 첫 숫자는 항상 0이기 때문에 시작 값에 대한 변화가 없다.

 2. 1번째 영역에 속하기 위해서는 r은 2^(N-1)보다 작으며, c는 커야 한다. 1번째 영역의 왼쪽 위 첫 숫자는 4^(N-1)*1에 해당한다. (총 숫자는 2^N*2^N= 4^N 개 있으며, 이를 사등분 하면 각 영역당 숫자는 4^(N-1)개 있다.)

 3. 2번째 영역에 속하기 위해서는 r은 2^(N-1)보다 크며, c는 작아야 한다. 첫 숫자는 4^(N-1)*2이다.

 4. 3번째 영역에 속하기 위해서는 r과 c가 모두 2^(N-1)보다 커야 한다. 첫 숫자는 4^(N-1)*3이다.

위 4개 비교를 통해서 각 영역에 들어가기 위해 r과 c를 2^(N-1)보다 크다면 그 값을 빼주고, N=1이 될 때까지 반복한다.

최종적으로는 r과 c는 0아니면 1에 해당하는 제일 작은 Z를 얻을 수 있고, 해당하는 영역의 숫자를 answer에 더해 출력해주면 된다.

문제링크:

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

문제:

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이의 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이의 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력:

첫째 줄에 재료의 개수 N(1<=N<=10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력:

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

풀이방법:

각 재료에 따라서 넣고 빼고 하는 작업을 재귀로 구현을 했다. mix라는 함수를 재귀적으로 호출하고, sour와 bitter의 배열의 크기를 줄여나가면서 재귀를 진행한다. 이 배열의 길이가 0이 될 때까지 반복하며, 결과값을 global 변수인 answer에 모두 담고, min 값을 출력한다.

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

문제:

 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다.(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다.)

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력:

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1 이상 100 이하의 정수이다.

출력:

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이방법:

 bfs를 사용해서 풀수는 있을 것 같지만 dfs를 사용해서 풀었다. 재귀의 깊이가 얼마나 될지 모르고, deepcopy를 사용하기 위해서 sys와 copy를 import 했다.

 지역의 높이 정보 입력값을 받으면서 max 연산을 취해서 지역 내에 가장 높은 영역이 값을 얻도록 했다. (뒤에서 for 반복문에서 사용하기 위해) 입력을 다 받은 뒤에는 이 높이 정보를 deepcopy한 뒤 현재 rain에 맞게(1부터 시작한다.) 값을 빼주고 만약 0 이하로 떨어지게 된다면 0으로 만들고 나머지는 그대로 냅뒀다.

 이제 이렇게 비에 잠긴 영역들을 표시했으니 dfs를 사용해서 살아있는 영역의 개수를 구한다. 각 점을 탐색하며 0이 아닌 곳에서 dfs 탐색을 시작하며 탐색 되는 곳은 0으로 만들어줘서 방문했음을 알려준다. 이렇게 반복해서 하면 영역의 개수를 구할 수 있고 max 연산을 통해 최댓값을 구한다.

문제링크:

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

문제:

풀이방법:

트리 구조를 알고 있는지 물어보는 문제인 것 같다. 따라서 Tree라는 class를 만들고, 이 클래스는 x,y 좌표와 left, right를 만들어서 node 연결을 하도록 한다.

우선 부모 노드를 찾고, 자식 노드들을 알기 위해서 정렬을 하는 작업을 먼저 한다. y가 큰 순으로, x가 작은 순으로 정렬하도록 하기 위해 sorted의 key를 사용하였다.

이렇게 root를 찾고 남은 node들은 root부터 시작하여서 x 좌표를 비교해서 이 값이 left 혹은 right인지 확인을 한다. 만약 현재 node에서 이미 left나 right 값이 있다면 그 노드로 이동해서 다시 비교를 하고 지정해주는 작업을 계속해서 반복한다. 따라서 얼마나 많은 반복을 해야할지 모르기 때문에 while을 사용하였으며, 연결을 완료하면 break로 나오도록 하였다.

node 연결을 마친 뒤에 preorder와 postorder는 정의대로 재귀를 사용해서 배열에 담아서 return 하도록 한다. 다만 이 때 많은 node들이 있으면 python의 재귀 메커니즘상 런타임 에러가 발생한다고 한다.

(python은 재귀가 최대 1000회로 제한되어 있다.)

따라서 이를 해결하기 위해서 sys.setrecursionlimit()를 사용해서 최댓값을 넉넉히 늘려주도록 한다.

문제링크:

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

문제:

풀이방법:

진행되는 단계를 보면 재귀적으로 수행한다고 했으므로 재귀로 구성하는 것이 맞다.

전체적인 진행은 make라는 함수에서 된다. 

1, 2는 split()이라는 함수에서 진행된다. 2는 균형잡힌 문자열으로만 분리하면 되므로 ( 면 +1을 ) 면- 1을 해서 균형잡힌 문자열으로 분리를 한다.

 이렇게 분리를 한 뒤에 u가 올바른 괄호 문자열인지 확인해야 한다.(3) 이 작업은 check라는 함수에서 진행된다. split과 비슷하게 작동을 하지만 count가 음수로 내려간다면 올바른 괄호 문자열이 아니기 때문에 이 경우에 False를 반환하고 나머지는 True를 반환하도록 한다. 그리고 이를 문자열에 붙이고 v에 대해서 1을 다시 진행하도록 make(v)를 수행한다.만약 u가 올바른 괄호 문자열이 아니라면 수행하라는 작업을 그대로 수행하면 된다.

문제링크:

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

문제:

 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 두 정수 L, C가 주어진다. (3<=L<=C<=15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력:

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

풀이 방법:

 재귀적인 방법으로 암호를 만들고, 이 암호가 옳은 암호인지 판단하는 check라는 함수를 만들었다. 암호를 만들다가 길이가 L이 된다면 check로 옳은 암호인지 판단을 하고 맞다면 출력, 아니면 끝내도록 했다.

문제링크:

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

문제:

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력:

첫째 줄에 자연수 N과 M이 주어진다. (1<= M <= N < 8)

출력:

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이 방법:

재귀적인 방법으로 길이가 M이 될 때까지 계속해서 넣어준다. 대신 이 문제에서는 중복을 허용하지 않았기 때문에 이에 대한 조건도 있어야 하고 증가하는 순서로 출력해야 하므로 배열에 들어있는 끝 값보다 클 때만 넣어줘야 한다는 조건 역시 필요하다. 이 문제에 대한 시리즈가 여러개 있는데 이에 맞는 조건을 넣어주면 된다.

문제 링크:

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

문제:

입력:

출력:

풀이 방법:

문제:

예를 들어

F(2)= F(0)+F(1)=0+1=1

F(3)= F(1)+F(2)=1+1=2

F(4)= F(2)+F(3)=1+2=3

F(5)= F(3)+F(4)=2+3=5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

풀이 방법:

문제:

풀이 방법: