CodeDrive

문제:

풀이방법:

 숫자를 만난 순간부터 계속해서 숫자를 연속해서 탐지할 수 있도록 알고리즘을 구성해야 하고 따라서 DFS를 사용해서 해당 문제를 풀었다.

 maps를 탐색하다가 X가 아니고, 이전에 탐색한 곳이 아니라면 DFS를 수행하며, 연속된 영역을 탐색하는 동안 visited를 계속해서 갱신하도록 한다. 이와 같은 과정을 방문할 곳이 남아 있지 않을 때까지 수행하고, 각 영역의 넓이는 마지막에 정렬을 하도록 한다.(단, 정렬할 영역이 없다면 -1을 반환)

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/154540

문제:

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

입력:

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력:

첫 줄에 거리가 K인 가짓수를 출력한다.

풀이방법:

 DFS를 사용해서 시작점에서 도착점까지 이동하고, 한 번의 이동마다 거리를 하나씩 늘린다. 도착점에 도달한 경우 거리가 K와 같다면 answer를 하나 증가시키고, 그렇지 않다면 다시 되돌아 오는 과정을 수행한다. '다시 되돌아 온다' 라는 행동을 하기 위해 visited 배열을 사용하고, 그 위치로 이동한 경우에는 해당 좌표의 값을 1로 바꾸고, 다시 되돌아 온 경우에는 0으로 다시 바꿔주도록 한다.

문제링크:

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

문제:

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력:

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력:

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

풀이방법:

 보통 일반적인 소수 문제의 경우에는 에라토스테네스의 체를 사용해서 소수인 수들을 모두 찾고 하는 것이 빠른 경우가 많으나, 이 문제의 경우에는 N = 8 인 경우에 수가 엄청 커지게 되고, 시간이 오래 걸리게 된다.

 따라서 이 문제의 경우에는 dfs를 사용해서 한자리씩 붙여 나가면서 소수를 판정하는 방식을 사용하도록 한다. 문제의 특징으로 인해 75가 소수가 아니므로, 그 뒤는 판정할 필요가 없기 때문이다. dfs의 종료 조건은 숫자의 길이가 N이 될 때까지 진행한다.

문제링크:

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

문제:

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력:

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

풀이방법:

dfs와 DP를 같이 사용해서 이 문제를 풀었다. 기본적인 방식은 dfs를 사용해서 조건에 맞게 이동을 하며 최종 목적지까지 탐색을 한다. 그러다가 최종 목적지에 도달하면 재귀를 빠져나오면서 그 경로에 +1을 해주면서 다시 돌아오게 된다. 

이 과정을 가능한 모든 경우에 대해서 수행할 수 있기 때문에 최종적으로는 dp[0][0]에 저장되어 있는 값을 출력해주면 된다.

문제링크:

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

문제:

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력:

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력:

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

풀이방법:

dfs를 사용해서 이 문제를 풀 수 있다. dfs는 다음과 같이 구성되어 있다.

1. 한 점으로부터 시작해 상하좌우를 탐색한다. (처음은 1행 1열)

2. 상하좌우를 탐색할 때, 아직 방문하지 않았고, 처음보는 알파벳이라면 그 방향으로 다시 dfs를 탐색한다.

3. dfs를 시작하는 순간마다. 현재까지 가지고 있는 알파벳 수를 기억해서 최대 몇칸을 지날 수 있는지 확인한다.

4. 더 이상 이동하지 못하는 경우에 한 dfs를 빠져나오게 되며, 방문 기록과 알파벳 탐색 기록을 지운다.

최종적으로 3번을 통해 기록한 값을 출력하면 된다.

문제링크:

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

문제:

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력:

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이방법:

 nodes라는 이중배열을 사용해서 입력으로 주어지는 연결된 두 정점 사이의 관계를 기록한다. 그리고 항상 트리의 루트는 1이라고 정해졌기 때문에, 1부터 dfs를 사용해서 노드들을 탐색하면서 parent를 기록한다.

문제링크:

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

문제:

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A =>  < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력:

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력:

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

풀이방법:

 처음에는 itertools의 permutation을 사용해서 풀려고 했으나, 메모리 초과가 발생했다. 아무래도 경우의 수가 엄청 많기 때문에 발생한 것 같았다.

 따라서 백트래킹(dfs)를 사용해서 효율적으로 구하려고 했다. visited 배열을 만들어서 사용한 숫자, 그렇지 않은 숫자를 구분했고, 빈 문자열로 시작했기 때문에 length==0이라는 조건을 넣어주게 되었다. is_possible 함수를 통해 부등호를 만족하는 조건의 숫자들을 구했으면 이를 answer 배열에 넣도록 한다. 

 이 때, answer 배열들의 숫자들은 작은 숫자부터 생성하기 시작했기 때문에 맨 처음에는 "부등호를 만족하는 가장 작은 숫자", 맨 마지막에는 "부등호를 만족하는 가장 큰 숫자"가 들어가 있게 된다. 따라서 이를 알맞게 출력하면 된다.

문제링크:

www.acmicpc.net/problem/2529

문제:

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력한다.

풀이방법:

 주어진 수가 1,000,000,000로 엄청 크게 주어졌기 때문에 A~B 사이의 수가 4와 7로 이루어져있는지 탐색하는 것은 시간초과가 발생할 것이다. 따라서4와 7로 구성된 숫자를 만들면서 이 숫자가 A~B 사이에 있는지 확인하도록 한다.

 A와 B가 큰 수로 주어질 수도 있기 때문에 깊이라는 개념을 사용해서 최대한 탐색할 수 있도록 했다. 깊이는 상한값으로 인해 최대 9까지 가능하다. 깊이라는 개념이 추가되었기 때문에 깊이우선탐색을 사용해서 값을 만들어내도록 한다.

 생성된 값이 주어진 범위 안에 들어 있으면 count를 1 올려주고 상한 값을 넘어가면 더 빠른 탐색을 위해서 0을 반환하도록 했다. 하한값에 보다 작은 값에 대해서는 조건이 없는데, 그 이유는 앞서 말했던 A와 B가 큰 수로 주어졌을 때, 그 범위 내까지는 이동하도록 하기 위함이다.

문제링크:

www.acmicpc.net/problem/1527

문제:

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력:

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력:

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

풀이방법:

 위키피디아에 따르면 이분 그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 즉 한 변의 양 끝은 빨강과 파랑으로 서로 달라야 한다는 것이다.

 dfs로 정점을 탐색하며, visited에다 색을 기록한다. dfs로 탐색하는 도중에 visited에 서로 다른 색이 들어오게 되면 이분그래프가 아니므로 False를 반환하도록 한다.

문제링크:

www.acmicpc.net/problem/1707

문제:

2048 게임은 4x4 크기의 보드에서 혼자 즐기는 게임이다. 

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 디시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

이 문제에서 다루는 2048 게임은 보드의 크기가 NxN이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 쵣 5번 이동해서 만들 수 있는 가장 큰 불록의 값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 보드의 크기 N (1<=N<=20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력:

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

풀이방법:

최대 5번만 이동하면 되기 때문에 dfs를 사용해서 모든 경우를 탐색하고, 그 중 가장 최댓값을 찾아내도록 하면 된다.

반복문을 사용해서 상하좌우로 이동하게 만들었다.

문제링크:

www.acmicpc.net/problem/12100