선택정렬

선택정렬

  • 주어진 리스트에서 최소값을 찾는다.
  • 최소 값을 찾아서 대상과 교환을 한다.
  • arr.length – 1 만큼 반복한다. 마지막은 할 필요가 없기 때문에

예를 들어보자

min = 6

6 2 7 8 1

  • min과 2를 비교해서 더 작은 값을 min에다 넣는다. min=2
  • 7과 8 도 비교를한다. 2가 더 작기 때문에 min은 그대로 2다.
  • min과 1을 비교한다. 1이 더 작기때문에 min 1을 넣는다.
  • 6과 1을교환 한다.
  • 이를 반복한다.

소스를 보자!

private static void selectionSort(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) { //min이 클경우 대상이 작기 때문에 대상을 min에다 넣는다.
                min = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

버블정렬

버블정렬

  • 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

6 2 7 8 1

  • 6보다 2이 작기 때문에 교환

2 6 7 8 1

  • 6보다 7이 크기 때문에 교환 하지 않는다.

2 6 7 8 1

  • 7보다 8이 크기 때문에 교환 하지 않는다.

2 6 7 8 1

  • 8보다 1이 작기 때문에 교환

2 6 7 1 8

  • 다시 처음으로 돌아가 반복 한다.
private static void bubbleSort(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

조금 나은 버블정렬

버블 정렬은 각각 한번씩 i랑 i+1 을 비교하므로 만약 한번도 교환이 일어 나지 않았다면 정렬이 된 상태다.
그걸 이용해서 조금 더 나은 버블정렬을 구현할 수 있다.

private static void bubbleSort(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        boolean checked = false;
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                checked = true;
            }
        }
        if(!checked){
            break;
        }
    }
}

사다리 게임(모 회사 입사문제)

사다리 게임

slipp 사이트를 보다보니 사다리 게임 문제가 있어서 한번 풀어봤다.
내용은 즉 이렇다.

위 그림은 커피 내기를 할 때 유용한 사다리 게임입니다.
잘 생각해 보면, 사다리 게임은 가로선을 (높이, 왼쪽의 세로줄 번호) 형태로 나타낼 수 있습니다.
예컨대, 위 사다리 게임은 (1, 1), (6, 1), (9, 1), (3, 2), (5, 2) ....와 같이 표현할 수 있습니다.

보면 시작점만 (1,1) 이런 형태로 넣고 있다. 그래서 끝점 (1,2) 도 알아야 2에서 1로 갈 수 있을텐데…
그런데 가만보면 시작과 끝점 형태를 보면 (x,y) 시작점 , (x,y+1)이 끝점이 된다.
어떻게 하면 풀 수 있을까 하다가 깊이우선탐색 혹은 너비우선탐색에 쓰이던 인접행렬이 떠올랐다.
그래서 (1,1)을 넣을때 (1,2)도 같이 넣어 주면 된다고 생각했다.
일단 그래서 코딩을 시작했다.

temp[1][1] = temp[1][2]= 1;
temp[6][1] = temp[6][2]= 1;
temp[9][1] = temp[9][2]= 1;
temp[3][2] = temp[3][3]= 1;
temp[5][2] = temp[5][3]= 1;
temp[8][2] = temp[8][3]= 1;
temp[4][3] = temp[4][4]= 1;
temp[7][3] = temp[7][4]= 1;
temp[10][3] =temp[10][4]= 1;
temp[2][4] = temp[2][5]= 1;
temp[6][4] = temp[6][5]= 1;
temp[8][4] = temp[8][5]= 1;
temp[3][5] = temp[3][6]= 1;
temp[5][5] = temp[5][6]= 1;
temp[7][5] = temp[7][6]= 1;

일단 하드 코딩…
이런식의 코드가 완성되었다.
그리고 또 생각을 했다. 일단 체크는 했는데….흠!
가만보니까 (x,y) 중 y는 내가 현재 갈 위치를 말하는거 같았다.
일단 최초의 값(입력 값)을 index라 했고 만약 [x][index]의 값이 1이라면 선이 그어져 있다고 생각했다.
그리고 오른쪽으로 갈지 왼쪽으로 갈지 결정을 해야 되서 index-1이라면 왼쪽 그렇지 않다면 오른쪽으로 가야 된다.
그래서 나온게 일단 이거다.

for (int i = 0; i < temp.length; i++) {
    if(temp[i][index] == 1){
        if(temp[i][index - 1] == 1){
            index--;
        }else{
            index++;
        }
    }
}

테스트를 해봤다. 잘된다.
그런데 몇개 테스트하는중 이상한 걸 발견했다.
내 소스가 틀린것이다.
살펴보니까 단단히 문제가 있었다.
저기 사다리로 보면 (8,4)의 해당 하는 지점이다. (8,4)에선 오른쪽 왼쪽 전부 선이 그어져있다고 생각한다.
왜냐면 (8,3) 도 1이라 체크 해놨고 (8,5) 도 1이라 체크 해놨기 때문이다.
그래서 먼저 걸리는 선한테 그냥 가버린다.
문제다.
그래서 그냥 간단히 생각했다.
시작점과 끝점을 분리하자!.
그래서 이렇게 됐다.

for (int i = 0; i < arr.length; i++) {
    if (arr[i][index] == 1 || arr[i][index] == 2) {
        if (arr[i][index - 1] == 1 && arr[i][index] == 2) {
            index--;
        } else {
            index++;
        }
    }
}

끝점을 2로 표시 해두었다.
그래서 해당점이 끝점이라면 오른쪽으로 갈 수 없다.

  • 1 또는 2가 체크 되어 있다면
  • index – 1이 체크 되어있고 index 가 2라면 왼쪽으로 간다.
  • 그게 아니라면 오른쪽으로 이동한다.

이로써 된거 같다.

class Ladder {

    private int[][] arr;

    Ladder(int length) {
        arr = new int[length][length];
    }
    void add(int a, int b) {
        arr[a][b] = 1;
        arr[a][b + 1] = 2;
    }
    int start(int index) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i][index] == 1 || arr[i][index] == 2) {
                if (arr[i][index - 1] == 1 && arr[i][index] == 2) {
                    index--;
                } else {
                    index++;
                }
            }
        }
        return index;
    }
}
Ladder ladder = new Ladder(15);
ladder.add(1, 1);
ladder.add(6, 1);
ladder.add(9, 1);
ladder.add(3, 2);
ladder.add(5, 2);
ladder.add(8, 2);
ladder.add(4, 3);
ladder.add(7, 3);
ladder.add(10, 3);
ladder.add(2, 4);
ladder.add(6, 4);
ladder.add(8, 4);
ladder.add(3, 5);
ladder.add(5, 5);
ladder.add(7, 5);
System.out.println(ladder.start(3));

전체 소스다.
해당 소스가 문제가 된다면 삭제하겠습니다.

출처 : http://synapsoft.co.kr/jsp/recruit/14t.html