SW문제해결 기본 - Array 1.2 BabyGinGame
=> 순열, 정렬, 대표문제 - BabyGinGame해결
Exhaustive Search(완전 검색)이란?
-
문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
1. Brute-force 혹은 Generate-and-Test 기법이라고도 불림 2. 모든 경우의 수를 테스트 한 후, 최종 해법을 도출함 3. 일반적으로 경우의 수가 상대적으로 작을 때 유용함 4. 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작음 5. 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 Algorithm을 사용하고 해답을 확인하는 것이 바람직함
Baby-gin Game
0~9사이의 숫자 카드에서 임의의 카드 6장을 뽑았ㅇ르 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplete이라고 함
6장의 카드가 run과 triplete로만 구성된 경우를 Baby-gin으로 부름
입력 예)
- 667767은 두 개의 triplete이므로 Baby-gin이다.-> 666,777
- 054060은 한 개의 run과 한 개의 triplete이므로 역시 Baby-gin -> 456,000
- 101123은 한 개의 triplete이 존재하나 023이 run이 아니므로 Babygin이 아님 -> 123을 run으로 사용한다고 하더라도, 011이 run이나 triplete이 아님
6자리의 숫자를 입력 받아 Baby-gin 여부를 찾아내기.
먼저 완전 검색 방법으로 풀어보자.
-
고려할 수 있는 모든 경우의 수를 생성한다.
6개의 숫자로 만들 수 있는 모든 숫자를 나열한다(중복포함) ex) 2 3 5 7 7 7이 들어왔다면 모든 경우의 순열을 나열한다.
-
해답 테스트하기
앞의 3자리와 뒤의 3자리를 잘라, run과 triplete 여부를 테스트하고 최종적으로 Baby-gin을 판단한다.
이러한 방법을 완전검색이라고 한다.
그렇다면 완전검색을 통해서 문제를 해결하려고 할 때, 시간 복잡도는 어떻게 될까? 이를 알기 위해서는 순열에 대해서 알아야 한다.
순열이란?
- 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것.
-
서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현한다.
nPr -
nPr은 다음과 같은 식이 성립한다.
nPr = n * (n-1) * (n-2) * ・・・ * (n-r+1) = n!/(n-r)! -
nPn은 n!이라고 하면 Factorial이라 부름
n! = n * (n-1) * (n-2) * ・・・ * 2 * 1
{1,2,3}을 포함하는 모든 순열을 생성하는 함수
동일한 숫자가 포함되지 않았을 떄, 각 자리수 별로 loop 이용
-> 이거 한번 코드로 작성해보자.
public static void main(String[] args) {
int i,j,k = 0;
for(i=0;i<3;i++)
for(j=0;j<3;j++) {
if(j != i) {
for(k=0;k<3;k++) {
if(k != i && k!= j)
System.out.println(i+" "+j+" "+k);
}
}
}
}
따라서 완전 검색으로 숫자를 찾아낼 경우, O(n!)의 시간복잡도가 소요된다. 그렇다면, 입력 받은 숫자를 정렬한 뒤, 앞 뒤 세 자리씩 끊어서 문제를 해결해보자.
정렬
그렇다면 입력 받은 숫자를 정렬한 후, 앞 뒤 3자리씩 끊어서 run 및 triplet을 검사하는 것은 어떨까? 정렬을 하기 위해 정렬의 종류와 원리에 대해 알아보자.
대표적인 정렬 방식의 종류
- 버블정렬
- 카운팅 정렬
- 선택 정렬
- 퀵 정렬
- 삽입 정렬
- 병합 정렬
버블 정렬
인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식을 말한다. 시간복잡도는 빅 오 n^2으로 상당히 느리지만 코드가 단순해서 자주사용
특징.
- 첫 번쨰 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막까지 이동한다.
- 한 단계까 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
- 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양 같다고 하여 버블 정렬이라고 한다.
버블 정렬을 직접 구현해보자.
public static void main(String[] args) {
int []Array = {55, 7, 78, 12, 42};
//버블 정렬을 이용해서 오름차순으로 정렬
for(int i = 0 ; i < Array.length; i++)
{
for(int j = i+1; j<Array.length; j++)
{
if(Array[i]>Array[j]) {
int temp = Array[j];
Array[j]=Array[i];
Array[i]=temp;
}
}
System.out.println(Array[i]);
}
}
카운팅 정렬이란 ?
카운팅 정렬이란 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘이다. n은 리스트의 길이, k는 정수의 최대값이라고 하면, 시간 복잡도는 O(n+k)이다. 카운팅 정렬은 버블정렬과는 달리 교환하지 않는 방식을 사용한다. 이 정렬은 n이 비교적 적을 때만 가능하다는 것을 알아두자.
카운팅 정렬은 크게 세 가지의 과정을 보여준다.
- 배열 내의 각 항목이 몇 개씩 있는지 파악한다.
- 이전의 발생 회수만큼 이후의 배열 값에 더해준다.
- 정렬할 원소와 각 원소의 개수를 저장한 배열을 통해 정렬을 하는 과정이다.
카운팅 정렬의 특징은 다음과 같다. 정수나 정수로 표현할 수 있는 자료에 대해서만 적용이 가능하다. 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다. 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.
연습문제. 카운팅 정렬.
{0, 4, 1, 3, 1, 2, 4, 1} 이 배열을 카운팅 정렬을 이용해서 오름차순으로 출력하라.
(직접 코딩할 때는 위에서 밝힌 세 가지 과목중 1,2를 합칠 수 있으므로 사실상 2가지 과목이다.)
카운팅 정렬을 직접 구현해보자.
public static void main(String[] args) {
int i , j;
int[] Array = { 0, 4, 1, 3, 1, 2, 4, 1 };
// 1단계 :배열의 각 항목이 몇 개씩 있는지 파악해서 이전의 발생한 회수만큼 이후의 배열 값에 더한다.
// 1. 배열의 길이와 정수의 최대값을 구해보자.
int max = Array[0];
for (i = 0; i < Array.length; i++)
if (Array[i] > max)
max = Array[i];
int[] Counts = new int[max+1];
// 2. counts 배열 구하기
for(i = 0 ; i <= max; i ++) {
int number = 0;
for( j = 0 ; j < Array.length; j++) {
if(Array[j] == i)
number ++;
}
Counts[i] = number;
//System.out.println(Counts[i]);
}
//3. 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 카운트들을 조정한다.
//앞의 데이터를 뒤의 데이터에 계속 더한다.
for(i=1; i < Counts.length; i++) {
Counts[i] = Counts[i]+Counts[i-1];
}
//System.out.println(Counts[0]+" "+Counts[1] + " "+ Counts[2]+ " "+ Counts[3]+ " " +Counts[4]);
//2단계 path
//temp라는 data(Array)배열과 같은 크기의 배열을 만들고, counts배열 이용해서 배열을 정렬한다.
int []temp = new int[Array.length];
//여기 주의해야한다.
for(i = temp.length-1; i>=0; i--)
temp[--Counts[Array[i]]] = Array[i];
for(i = 0 ; i < temp.length; i++)
System.out.println(temp[i]);
}
여기가 관건이다.
for(i = temp.length-1; i>=0; i--) temp[--Counts[Array[i]]] = Array[i];
다시 돌아와 대표문제. Baby-Gin Game - (탐욕알고리즘?)
정렬을 통해 대부분의 옳은 결과를 낼 수 있지만, 사실 일부 input에 대해서는 정확한 답을 출력해 내지 못한다. 대표적으로 1,2,3,1,2,3,의 경우가 있는데, 이 경우 정렬하게 되면 1,1,2,2,3,3 와 같이 정렬되어, run과 triplete가 모두 아니게 되어 올바르지 못한 결과를 출력한다. 이러한 접근방식을 탐욕 알고리즘(Greedy Algorithm)적인 접근이라고 표현하기도 한다.
Greedy
이 탐욕 알고리즘은 최적 해를 구하는데 사용되는 근시안적인 방법이라고 할 수 있다. 선택할 수 있는 여러 경우 중 하나를 선택할 때 가장 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달 하는 방법이다. 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 통해 최종적인 해답을 만들었다고 해서 그것이 최적이라는 보장이 없는 계획법이다. 일반적으로 머리 속에 떠오르는 생각을 검즘 없이 바로 구현할 경우 탐욕 알고리즘적인 접근이 되는 경우가 있다.
=> 예제. 거스름돈 줄이기.
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
int []coins = { 500, 250, 100, 50, 10};
int []count = new int[5];
int i = 0;
int money = stdIn.nextInt();
while(money != 0)
{
if(money < 0) // 거스름돈을 많이 준 경우
{
count[i]--;
money += coins[i++];
}
else //거스름 돈을 더 주어야 하는 경우
{
count[i]++;
money -= coins[i];
}
}
for(i = 0 ; i < 5; i++)
System.out.printf("%d %d \n",coins[i], count[i]);
}
(왜 이렇게 구현했나 생각해봤는데. 이렇게 구하면 나눗셈 연산자를 사용하지 않고도 구현할 수 있다. 더하기 빼기로 구현한건다. 비효율적으로 보이지만, 사실 효율성으로 따지면 더 좋은 코드인 것이다.)
그렇다고 모든 문제를 다 탐욕 알고리즘으로 해결 할 순 없다. 해결되지 않는 경우도 있으며 그런 경우 다른 방법으로 해결해야 한다.
그러나 대표문제, Baby-Gin Game 문제는 탐욕 알고리즘을 통해 해결이 가능하다.
[1.2] 대표문제. Baby-Gin Game 해결하기
1. 각 카드가 있는 개수를 저장하는 배열을 만든다.
2. 만약 입력된 6개의 숫자가 `{4,4,4,6,4,5}`라고 가정하면, 배열에는 [0,0,0,0,4,1,1,0,0,0]으로 저장될 것이다. (문제에서 0~9 사이의 숫자카드라고 명시함.)
3. 먼저 카드를 0부터 확인하며 3이상의 수가 있는지 확인해 보는데, 이 경우에는 카드 4에 개수가 3이상인 4가 입력되어 있으므로 같은 카드가 3개 이상 존재한다는 뜻이다. 따라서 triplete가 존재한다는 의미이고, 해당 카드에 검사한 개수에 대해서는 제거한다.
- 계속 진행하면서 개수가 1이상 등장할 경우, 1이 등장한 카드를 포함하여 연속된 3개의 카드에 1이상의 개수가 있는지 판단하고 존재할 경우 run이므로 검사한 카드에 대해 개수를 1씩 제거한 뒤, run과 triplet가 나온 총 횟수가 2이면 BabyGin이라고 판단하면 된다.
import java.lang.reflect.Array;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
int i,j;
int input = stdIn.nextInt();
int[] c = new int[10];
int tri = 0, run =0;
for(i = 0 ; i < 6; i ++) { // 입력 받은 6자리의 숫자 중 각 자리 수를 판단한다.
c[(input%10)]++;
input /= 10;
}
for(i=0; i <10; i++) {
if(c[i] >= 3) { // triplet조사
c[i] -= 3;
tri += 1;
i--; //6개라고 가정한다면 한번 더 과정을 거쳐야한다.
}
if((c[i]>= 1) && (c[i+1] >= 1) && (c[i+2] >=1)){ // run 조
c[i] -= 1;
c[i+1] -= 1;
c[i+2] -= 1;
run += 1;
i--;
}
}
if(run + tri == 2)
System.out.println("Baby Gin");
else
System.out.println("Lose");
}
}
※ 입력 받은 정수를 각 자리수로
for(i = 5; i >= 0; i--){
data[i] = input%10;
input/=10;
}
정말 많은 것을 배울 수 있는 시간이었다.
정리하자면
완전 검색을 통해서 문제를 푼다면 ? -> 이러한 시간 복잡도를 확인하기 위해 순열을 배웠다. 순열을 통해 알아낸 결과 빅오 엔팩토리얼만큼의 시간 복잡도를 가진다.
그렇다면, 정렬을 해서 3자리씩 끊어서 생각해보면 되지 않을까? 그래서 버블정렬과 카운팅 정렬을 실습해가며 문제에 접근했다. 하지만 문제가 있다. 112233이라고 정력을 해버리면, Lose가 나오지만 사실 123123이 나오는 triplet2개로 Baby Gin이 나와야 한다. 이러한 접근방식을 설명하기 위해 탐욕알고리즘(그리디)에 대한 설명을 배웠다. 대개 머리 속에 떠오르는 생각을 검증없이 바로 구현할 경우 탐욕 알고리즘적인 접근이 되는 경우가 많다. 하지만 이 Baby-Gin Game은 탐욕 알고리즘을 통해서 해결이 가능하다.
이번 시간에 완전 검색 -> 순열 -> 정렬 -> 탐욕 알고리즘까지. 다뤄보았다.
참고자료
소프트웨어 아카데미 S/W Problem Solving Self Study Book 1. 2차시 순열, 정렬, 대표문제 -Baby Gin Game 해결
자바 입력 받은 정수 각 자리수 구하기 https://aristatait.tistory.com/54