WannaBeDeveloper

1103번: 게임 www.acmicpc.net 이 문제는 1부터 9까지의 숫자와 구멍이 있는 직사각형 보드에서 게임을 할 때 최대 몇 번의 동전을 움직일 수 있는지를 구하는 문제이다. 동전을 움직이는 규칙은 위와 같다. 이 문제를 해결하기 위해서는 왼쪽 위에서 시작하는 DFS를 수행해 동전의 이동 횟수의 최댓값을 구해야한다. DFS는 재귀 함수로 구현할 수 있다. 우선 함수 구현 전에 각 지점을 방문했음을 나타내는 N*M 크기의 visitied 행렬(초기값은 False)과 동서남북 방향을 나타내기 위한 dx, dy가 필요하다. 이제 DFS 함수를 구현해보자. 우선 DFS 함수는 인자로 방문하고자 하는 지점의 좌표 (x, y)를 받는다. 이 지점을 방문했다는 의미로 visited에서 해당하는 지점의 값을 ..

9466번: 텀 프로젝트 www.acmicpc.net 이 문제는 텀 프로젝트를 수행하기 위해 학생들 간에 프로젝트 팀을 구성할 때, 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 구하는 문제이다. 단, 모든 학생은 프로젝트를 함께하고 싶은 학생을 한 명만 선택할 수 있고, 프로젝트 팀을 구성하기 위해서는 학생을 s_1, s_2, ... ,s_r이라 할 때 s_1은 s_2를, s_2는 s_3를, ..., 그리고 s_r은 s_1을 선택해야 (s_1, s_2, ... ,s_r)이 한 팀을 이룰 수 있다. r=1인 경우, 즉 s_1이 자기 자신을 택하는 경우도 포함한다. 이 문제는 설명이 복잡하지만 결국 구하고자 하는 것은 학생들을 그래프의 정점, 프로젝트를 함께하고 싶은 학생을 선택하는 것을 그래프의 간선이..

10026번: 적록색약 www.acmicpc.net 이 문제는 빨강, 초록, 파랑으로 색칠한 그림이 주어졌을 때 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 문제이다. 구역이란 어떤 사람이 봤을 때 모두 같은 색으로 이루어진 영역을 말한다. 즉, 적록색약이 아닌 경우에는 빨강, 초록, 파랑을 구별해 같은 색으로 이루어진 구역의 수를 구하는 반면, 적록색약인 경우에는 빨강과 초록을 하나의 색으로 취급해 같은 색으로 이루어진 구역의 수를 구하면 된다. 여러 해결 방법이 있지만, 여기서는 적록색약이 아닌 경우와 적록색약인 경우 각각에 대해 바라본 그림에 대응하는 행렬을 만들어 각 행렬에 그래프 탐색을 이용해 구역의 개수를 구하는 방식으로 문제를 해결한다. 우선 위에서 말한 행렬 두 개..

2583번: 영역 구하기 www.acmicpc.net 이 문제는 M*N 크기의 모눈종이가 있고 여기에 K개의 직사각형을 그릴 때 K개의 직사각형의 내부를 제외한 나머지 부분이 여러 개의 영역으로 나누어지는데, 이때 영역의 개수와 각 영역의 넓이를 구하는 문제이다. 이를 해결하기 위해서는 우선 모눈종이의 각 칸이 하나의 entry에 대응하는 M*N 행렬 paper를 만들고, 직사각형의 내부의 칸에 대응하는 entry의 값을 1로, 나머지 entry는 0으로 한다. 이때 문제에서 나오는 input은 직사각형의 왼쪽 아래의 좌표와 오른쪽 위 좌표가 주어지는데, 실제로 paper의 각 entry는 하나의 칸에 대응하고, entry의 행과 열은 각각 모눈종이 내 해당 칸의 왼쪽 아래 점의 y좌표, x좌표와 같다...

1987번: 알파벳 www.acmicpc.net 이 문제는 각 칸에 대문자 알파벳이 하나씩 적혀 있는 R*C 크기의 보드가 있을 때 좌측 상단 칸에서 출발한 말이 지금까지 지나온 칸에 적힌 알파벳과 같은 알파벳이 적힌 칸을 지날 수 없을 때 최대 몇 칸을 지날 수 있는지를 구하는 문제이다. 이를 해결하기 위해서는 좌측 상단 칸에서 DFS를 시행하되, 현재까지 지나온 칸에 적힌 알파벳들을 따로 저장해둬 다음에 지날 칸에 적힌 알파벳이 이 알파벳 중 하나가 되지 않는 경우에만 해당 칸으로 진행하도록 함수를 작성한다. 그리고 백트래킹을 사용해 결과값을 반환하기 전에 현재 지난 칸에 해당하는 알파벳을 지워 후에 다른 경로를 통해 DFS를 시행할 때 정상적으로 해당 칸에 대한 방문을 할 수 있도록 한다. 이를 코..

2468번: 안전 영역 www.acmicpc.net 이 문제는 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 문제이다. 여기서 안전한 영역이란 강수량보다 해당 지역의 높이가 더 높아 물에 잠기지 않는 지점들의 집합 중 지점들끼리 서로 인접한 최대 영역을 말한다. 우선 특정 강수량이 주어진 경우를 생각해보자. 그러면 그 강수량에 대한 안전한 영역의 개수를 구하는 문제는 이전의 섬의 개수 문제와 거의 동일하다. 단지 안전한 영역을 찾기 위해 강수량보다 지점의 높이가 더 높은 지점에 대해서만 그래프 탐색을 한다는 점만 다를 뿐이다. 백준 4963번 : 섬의 개수 in Python 4963번: 섬의 개수 www.acmicpc.net 이 문제는 섬과 바다 지..

4963번: 섬의 개수 www.acmicpc.net 이 문제는 섬과 바다 지도가 주어질 때 섬의 개수를 세는 문제이다. 단, 두 정사각형이 같은 섬에 있기 위해서는 두 정사각형이 가로, 세로 또는 대각선으로 인접하고 있어야 한다. 이는 그래프 탐색을 이용해 쉽게 해결할 수 있다. 우선 깊이 우선 탐색이나 너비 우선 탐색 중 하나를 구현한 뒤, 지도 내 모든 정사각형을 방문하면서 만약 해당 정사각형이 섬의 일부인 경우 그 정사각형과 연결되어 있고, 섬의 일부인 모든 정사각형을 방문하는 그래프 탐색을 진행한다. 그러면 이후 그 섬을 다시 방문했을 경우 이미 방문한 섬이기에 섬의 개수를 셀 때 영향을 끼치지 않는다. 단, 보통 문제와는 달리 두 정사각형이 가로, 세로, 또는 대각선으로 인접한 경우 하나의 섬 ..

2098번: 외판원 순회 www.acmicpc.net 이 문제는 Traveling Salesman Problem(TSP)라 불리는, NP-complete 문제들 중 대표적인 문제로, 각 간선에 비용이 주어진 완전 그래프에서 모든 점을 한 번씩만 지나는 사이클 중 비용의 합의 최솟값을 구하는 문제이다. 위에서 말했듯이 이 문제는 NP-complete에 속해서 polynomial time 안에 해결하는 알고리즘이 알려진 게 없다. 그래서 입력의 크기가 작은 경우에만 적절한 시간 내에 해결이 가능하다. 이 문제는 이전의 할 일 정하기 1 문제처럼 DFS와 dynamic programming을 이용하면 상대적으로 효율적인 알고리즘을 만들 수 있다. 백준 1311번 : 할 일 정하기 1 in Python 1311..

1311번: 할 일 정하기 1 www.acmicpc.net 이 문제는 N명의 사람에게 N개의 일을 하나씩 담당하게 할 때 모든 일을 하는데 필요한 비용의 최솟값을 구하는 문제이다. 만약 단순히 모든 경우의 수를 고려해 일을 배분한다고 하면 N!가지의 경우의 수를 모두 고려해야 하므로 총 걸리는 시간은 O(N^N)으로 매우 비효율적이다. 그래서 이 문제는 dynamic programming을 활용해 보다 효율적인 알고리즘을 생각할 필요가 있다. 즉, 이전에 계산한 결과를 저장할 배열을 만들 필요가 있는데, 이 계산 결과라 함은 일을 맡긴 사람의 수 i와 각 사람마다 맡긴 일의 집합 S에 대해 가능한 비용 중 최솟값을 의미한다. 예를 들어 N = 6일 때 4명의 사람에게 1, 3, 4, 6이라는 일을 맡겼다..

2252번: 줄 세우기 www.acmicpc.net 이 문제는 키를 비교한 두 학생의 번호 쌍들이 주어졌을 때 학생들을 키 순서대로 세우는 문제이다. 구체젹인 예로 1 3이라는 번호 쌍이 주어진 경우 학생 1이 학생 3보다 앞에 서야 한다. 즉, 학생 1과 학생 3 사이에는 어떤 학생이 와도 상관이 없으나 학생 1이 학생 3보다는 반드시 앞에 있어야 한다는 의미이다. 이러한 문제를 해결하기 위해서는 위상 정렬을 알아야 한다. 위상 정렬이란 directed acyclic 그래프(각 간선의 방향이 존재하고 사이클이 없는 그래프)에서 임의의 정점을 방문하기 위해 그 정점으로의 간선을 모두 방문해야 한다는 조건이 붙은 경우의 그래프 탐색 방법을 말한다. 위 문제의 경우를 예로 들어보자. 만약 어떤 학생 1이 학..