최소 회수로 정렬하기(뒤집어 정렬하기), 정렬하는 회수 찾기 - 너비 우선 탐색 알고리즘 문제(Java 1.8)
2021.03.28
출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 문제 (Sorting Game) 정수의 배열이 주어질 때 연속된 부분 구간의 순서를 뒤집는 것을 뒤집기 연산이라고 부릅시다. 예를 들어 배열 {3, 4, 1, 2}에서 부분 구간 {4, 1, 2}를 뒤집으면 {3, 2, 1, 4}가 됩니다. 중복이 없는 정수 배열을 뒤집기 연산을 이용해서 정렬하려고 합니다. 필요한 최소한의 연산 수를 계산하는 프로그램을 작성하세요. 예를 들어 {3, 4, 1, 2}는 {3, 4}와 {1, 2}를 각각 뒤집고 전체를 뒤집으면 세번의 연산으로도 정렬할 수 있지만, {4, 1, 2}를 먼저 뒤집고 {3, 2, 1}을 뒤집으면 두 번의 연산만으로 정렬할 수 있습니다. 시간 및 메모리 제한 프로그램은 2초 안에 실행되어야..