MungGu Story

오늘은 오랫만에 백준 문제를 하나 풀어봤습니다. solved.ac 기준, 골드5 티어 수준의 게리맨더링 문제입니다. 해당 문제는 모든 경우의 수에 대해 BFS, DFS 등의 탐색을 활용해서 N개의 구역 중 완벽하게 2개 선거구으로 나뉘는 경우에 한해 두 구역 인구수가 최솟값인 경우를 찾는 문제였습니다. 바로 제 소스코드를 보면서 문제풀이 보도록 하겠습니다. 백준알고리즘 17471번 문제, 게리맨더링 조합 및 완전탐색 swift 문제풀이 1) 문제 입력준비 및 변수 선언하기 먼저, 입력받기전, readLine() 입력 속도 최적화를 살짝 진행한 readInput 클로져 함수를 정의해두었습니다. 위 클로져는 양수값만 입력으로 들어올때 사용할 수 있습니다. 음수도 들어가는 경우, "-" 문자에 대한 flag ..

백준 10974번 모든 순열 예제설명 백준 10974번 모든순열은 N이 주어졌을 때 1부터 N까지의 수를 가진 모든 순열을 사전순으로 출력하는 문제입니다. 본 문제는 재귀 / 비재귀 방식으로 모두 풀 수 있는 문제입니다. 시간제한은 1초, 메모리제한은 256MB입니다. 모든ㄴ순열의 출력은 DFS, 백트래킹을 사용해서 출력해볼 예정입니다. N의 범위가 최대 8이므로, N!의 시간복잡도로도 충분히 풀리는 문제입니다. 최대 값인 8의 경우에도 최대 1억번의 연산에 미치지 않기 때문입니다. 위와 같이 N이 3일 경우, 1, 2, 3 세개의 숫자가 있는 모든 순열을 사전순, 개행단위로 출력해주면 되는 문제입니다. 이어서 swift언어와 DFS(깊이 우선 탐색) 백트래킹을 활용해서 문제를 풀어보도록 하겠습니다. 백..