순열

- n개의 원소를 가지는 배열에서 r개의 원소를 선택하여 나열하는 문제. 여기서는 n == r 로 가정하겠다.


조건

- 

풀이전략

(1) 선택된 원소의 인덱스를 표현하는 selectedIndex배열을 선언.
(2) selectedIndex의 인덱스를 0 ~ n-1까지 증가시키며 인덱스에 위치할 수 있는
    후보군 인덱스 배열을 구한다 (getCandidates)
(3) 선택된 인덱스에 반복문을 이용하여 후보군에서 구한 인덱스를 대입한다 
(4) 백트래킹을 실행한다. (2) ~ (3) 반복


구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.ArrayList;
import java.util.List;
 
/**
 * n개의 원소를 가지는 배열의 모든 순열을 구하는 문제
 * @author troh
 *
 */
public class Stack백트래킹_순열 {
    // n개의 원소를 가지는 배열
    private static int[] arr = {1, 2, 3, 4};
    // 순열의 인덱스를 가리키는 배열
    private static int[] index = {-1, -1, -1, -1};
    
    public static void main(String[] args) {
        backTracking(index, -1, 3);
    }
    
    public static void backTracking(int[] selectedIndex, int k, int input) {
        // 결과 출력
        if(k == input) {
            System.out.printf("{");
            for(int i=0; i<=k; i++) {
                System.out.printf(" %d", arr[selectedIndex[i]]);
            }
            System.out.printf("}\n");
        } else {
            k++;
            /**
             * k인덱스에 대입할 수 있는 인덱스를 구하는 구함
             * 예를 들어 인덱스 0에는 { 0, 1, 2, 3} 
             * 모두 가능하지만 0번째 인덱스에 1을 선택했다면
             * 다음 인덱스 1에는 1을 제외한 {0, 2, 3}이 선택 가능함
             */
            int[] candidates = getCandidates(selectedIndex, k, input);
            for(int i=0; i<candidates.length; i++) {
                selectedIndex[k] = candidates[i];
                backTracking(selectedIndex, k, input);
            }
        }
    }
    
    /**
     * 현재까지 선택되지않은 순열 반환
     * @param a 현재까지 선택된 순열
     * @param k 배열의 최대 인덱스
     * @return
     */
    public static int[] getCandidates(int[] selectedIndex, int k, int input) {
        /**
         * 선택되지 않은 원소찾기
         */
        boolean[] selectedIndexCheck = new boolean[input+1];
        for(int i=0; i<k; i++) {
            selectedIndexCheck[selectedIndex[i]] = true;
        }
        
        /**
         * 선택되지않은 원소의 인덱스를 배열로 만들어서 반환
         */
        int[] nonSelectedIndex = new int[input-k+1];
        int tempIndex = 0;
        for(int i=0; i<input+1; i++) {
            if(selectedIndexCheck[i] == false) {
                nonSelectedIndex[tempIndex] = i;
                tempIndex++;
            }
        }
        return nonSelectedIndex;
    }
}
 
cs


저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

백트래킹 - PowerSet  (0) 2019.05.15
백트래킹 - NQueen  (0) 2019.05.15
Stack(3) - 계산기(문자열 수식), 백트래킹 기법  (0) 2019.04.04
Stack(2) - DP(동적 계획법), DFS(깊이우선탐색)  (0) 2019.03.23
Stack(1) - 스택과 memorization  (0) 2019.03.19

PowerSet

- n개의 원소를 가지는 배열의 모든 부분집합(2^n개)을 구하는 문제


조건

- n개의 원소의 부분집합은 총 2^n개

풀이전략

(1) n개의 배열의 각 원소가 부분집합에 포함되는지 여부를 나타내는 부분집합포함 배열 선언
   + 예를 들어 { 0, 1, 2, 3 } 의 부분집합 중 { 0, 2 } 를 부분집합포함 배열을 이용하여 나타내면 { 1, 0, 1, 0 } 이다

(2) 부분집합포함 배열의 인덱스를 0부터 3까지 증가시키면서 인덱스에 해당하는 원소를 포함하는 경우(1)와
    포함하지 않는 경우(0)을 각각 백트래킹을 실행한다. 

구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
/**
 * n개의 원소를 가지는 배열에서 모든 부분집합(2^n개)를 
 * 백트래킹 기법으로 구함
 * @author troh
 *
 */
public class Stack백트래킹_PowerSet {
    // n개의 원소를 가지는 배열
    private static int[] arr = {0, 1, 2, 3, 4};
    
    // arr의 각 인덱스가 부분집합에 포함되는지 0 또는 1로 표시하는 배열
    private static int[] inclusionArr = new int[arr.length];
    
    // 불포함, 포함 배열을 나타냄
    private static int[] candidates = {0, 1};
    
    public static void main(String[] args) {
        backTracking(inclusionArr, -1, inclusionArr.length-1);
    }
    
    /**
     * @param inclusionArr 부분집합포함 배열
     * @param incIndex inclusionArr의 인덱스
     * @param incLastIndex inclusionArr의 마지막
     */
    public static void backTracking(int[] inclusionArr, int incIndex, int incLastIndex) {
        // 부분집합포함 배열의 마지막까지 백트래킹이 실행되었다면 결과출력
        if(incIndex == incLastIndex) {
            System.out.printf("{");
            for(int i=0; i<inclusionArr.length; i++) {
                // 부분집합포함배열에 포함될 경우에만 원소를 출력
                if(inclusionArr[i] == 1) {
                    System.out.printf(" %d,", arr[i]);
                }
            }
            System.out.printf("}\n");
        } 
        else {
            // 부분집합포함 배열의 인덱스를 증가시킴
            incIndex++;
            
            // 해당 인덱스의 원소를 포함하는 경우와 포함하지않는 경우로 백트래킹 실행
            for(int i=0; i<candidates.length; i++) {
                inclusionArr[incIndex] = candidates[i];
                backTracking(inclusionArr, incIndex, incLastIndex);
            }
        }
    }
    
}
 
cs


배운점..

음.. 뭐 저번에 NQueen문제를 백트래킹으로 구현하며 너무 삽질을 많이해서 이번 문제는 풀만하게 느껴진 것 같다. 그래도 백트래킹 기법에 대해 좀 더 이해할 수 있는 문제였다.


저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

백트래킹 - 순열  (0) 2019.05.18
백트래킹 - NQueen  (0) 2019.05.15
Stack(3) - 계산기(문자열 수식), 백트래킹 기법  (0) 2019.04.04
Stack(2) - DP(동적 계획법), DFS(깊이우선탐색)  (0) 2019.03.23
Stack(1) - 스택과 memorization  (0) 2019.03.19

NQueen 문제풀이

- N*N의 체스판에서 모든 행에 대해서 각 행마다 하나의 퀸이 존재하도록 퀸을 배치하는 문제

조건

1. 모든 행에 대해서 각 행마다 하나의 퀸이 존재
2. 각 퀸은 같은 열 또는 대각선 상에 위치할 수 없음

풀이전략

먼저 5시간 정도 삽질한 내용을 적자면 ( 하.. 부끄럽다 .. )

(1). 체스판을 2차원 배열로 표현
(2). 퀸을 체스판(2차월 배열)에 위치시킬 수 있는지 검사( 배열 전체를 검사함 - 같은 행, 같은 열, 대각선상에 존재 )
(3). 위치시킬 수 있다면 체스판의 값을 업데이트 ( 2 - 퀸의 위치, 1 - 퀸을 놓을 수 없는 위치, 0 - 퀸을 놓을 수 있는 위치 )
(4). 다음 행의 노드 전부를 2번에서 구한 노드의 자식노드로 설정
(5). 자식 노드를 순회하며 (2)~(4) 번  순회

# 자식 노드 전부 퀸을 위치시킬 수 없다면 ? 
 - (2)의 수행결과를 롤백해야 함
 - 부모의 퀸을 +1열 옮겨서 다시 테스트해야함 ( 이부분에 대해 스택으로 삽질해보았지만 머리만 아팠다..)

접근 방법이 잘못되었다고 느끼기 시작했다... 
힌트를 얻고자 구글링하다가 친절하게 설명해주신 분을 발견 !!  감사합니다 ㅠㅠ

핵심을 말하자면 2차원 배열로 퀸의 위치를 표현하는 것이 아니라
행의 크기(N) 와 각 행에서의 퀸의 위치(cols)를 1차원 배열로 표현하여 분리해야 한다는 것 !

구현하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * @author troh
 */
public class Stack백트래킹_NQueen {
    private static int N = 4;
    private static int[] cols;
    
    public static void main(String[] args) {
        cols = new int[4];
        backTracking(0);
    }
    
    public static void backTracking(int level) {
        // 현재 레벨이 N이라는 것은 N-1까지 퀸을 배치했다는 것이므로 모든 퀸을 배치 완료했다는 것
        // 답을 출력
        if(level == N) {
            for(int i=0; i<N; i++) {
                System.out.printf("%d ", cols[i]);
            }
            System.out.println("");
        } 
        // 현재 레벨의 어느 위치에 퀸을 두어야 하는지 확인
        else {    
            for(int i=0; i<N; i++) {
                // 현재 레벨의 퀸은 i열에 위치시킴
                cols[level] = i; 
                // 현재 레벨이 유효한지 검사
                if(isPossible(level)) {
                    backTracking(level+1);
                }
            }
        }
    }
    
    public static boolean isPossible(int level) {
        for(int i=0; i<level; i++) {
            // 같은 열에 위치하거나
            // 또는
            // 대각선에 위치하거나 ( 가로차이와 세로차이가 같으면 대각선상에 있다고 판단 )
            if(cols[i] == cols[level] || Math.abs(level-i) == Math.abs(cols[level] - cols[i])) {
                return false;
            }
        }
        return true;
        
    }
}
 
cs


배운점 ..

5시간의 삽질로 인해 스택과 재귀함수에 대해 많이 생각해 본 것 같다. 그리고 알고리즘 구현에 잡다한 로직(2차원 배열의 수행결과 롤백)을 수행해야 한다면 문제를 다른 시각으로 생각해봐야 할 것 같다.


저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

백트래킹 - 순열  (0) 2019.05.18
백트래킹 - PowerSet  (0) 2019.05.15
Stack(3) - 계산기(문자열 수식), 백트래킹 기법  (0) 2019.04.04
Stack(2) - DP(동적 계획법), DFS(깊이우선탐색)  (0) 2019.03.23
Stack(1) - 스택과 memorization  (0) 2019.03.19

계산기(문자열 수식 계산하기)

계산기의 문자열 계산식을 스택을 사용하여 해결할 수 있다.

  1. Stack을 이용하여 중위표기법[각주:1]의 수식을 후위표기법[각주:2]으로 변경
  2. 후위표기법의 수식을 Stack을 이용하여 계산


1. 중위표기식을 후위표기식으로 변환하기

  1. 입력받은 중위표기식에서 토큰을 읽음
  2. 토큰이 피연산자이면 토큰을 출력
  3. 토큰이 연산자(괄호포함)일 경우
    1. 토큰이 스택의 top에 저장된 연산자보다 우선순위가 높으면 push
    2. 그렇지 않다면 토큰의 우선순위가 더 높을때까지 pop한 후 토큰의 연산자를 push
    3. top에 연산자가 없으면 push
  4. 토큰이 오른쪽 괄호 ')' 일 경우
    1. Stack top에 왼쪽 괄호 '(' 가 올 때까지 pop
    2. pop한 연산자를 출력
  5. 중위표기식에 더 읽을 것이 없다면 중지, 더 읽을 것이 있다면 1부터 반복
  6. Stack 남아있는 연산자를 모두 pop하여 출력


1-1. 중위표기식을 후위표기식으로 변환하는 알고리즘 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
 
public class Stack_중위표기법변환 {
    // 스택 내에서 연산자 우선순위 맵
    private static Map<Character, Integer> operPriorityMap;
    private static Stack<Character> operStack ;
    static {
        operPriorityMap = new HashMap<>();
        operPriorityMap.put('(', 0);
        operPriorityMap.put('+', 1);
        operPriorityMap.put('-', 1);
        operPriorityMap.put('*', 2);
        operPriorityMap.put('/', 2);
        
        operStack = new Stack<>();
    }
 
    public static void main(String[] args) {
        String input = "(6+5*(2-8)/2)";
        List<Character> output = new ArrayList<>();
        
        char[] inputChars = input.toCharArray();
        
        for(int i=0; i<inputChars.length; i++) {
            char c = inputChars[i];
            
            // 연산자
            if(isOperation(c)) {
                // 연산자 스택이 비었다면 push 
                if(operStack.isEmpty()) {
                    operStack.push(c);
                } // 연산자 우선순위 비교 
                else {
                    // 닫는 괄호일경우 여는 괄호 '(' 가 나올떄까지 pop
                    if(c == ')') {
                        char top = ' ';
                        do {
                            top = operStack.pop();
                            if(top != '(') {
                                output.add(top);
                            }
                        } while(top != '(');
                    } // 여는 괄호는 무조건 push 
                    else if(c == '(') {
                        operStack.push(c);
                    } // 그외 연산자인 경우 
                    else {
                        int tokenPriority = operPriorityMap.get(c);
                        
                        char top = operStack.peek();
                        int topPriority = operPriorityMap.get(top);
                        // 토큰의 우선순위가 더 높다면 스택에 추가
                        if(tokenPriority > topPriority) {
                            operStack.push(c);
                        } // 토큰의 우선순위가 더 높을때까지 pop 한 후 push 
                        else {
                            top = operStack.pop();
                            output.add(top);
                            
                            do {
                                if(operStack.isEmpty()) {
                                    operStack.push(c);
                                } else {
                                    top = operStack.peek();
                                    topPriority = operPriorityMap.get(top);
                                    if(tokenPriority > topPriority) {
                                        operStack.push(c);
                                    } else {
                                        top = operStack.pop();
                                        output.add(top);    
                                    }
                                }
                            } while(tokenPriority <= topPriority);
                        }
                    }
                }
            } // 피연산자
            else {
                output.add(c);
            }
        }
        
        // 6528-*2/+
        for(int i=0; i<output.size(); i++) {
            System.out.printf("%c", output.get(i));
        }
    }
    
    /**
     * 연산자 여부 확인
     * @param c
     * @return
     */
    public static boolean isOperation(char c) {
        if(')' == c) {
            return true;
        }
        
        return operPriorityMap.containsKey(c);
    }
}
 
cs


2. 후위표기법의 수식을 Stack을 이용하여 계산하기

위에서 구한 후의표기법을 이용하여 계산을 수행해보자. 알고리즘은 아래와 같다.

  1. 피연산자를 만나면 Stack에 push
  2. 연산자를 만나면 필요한 만큼의 피연자를 Stack에서 pop하여 계산하고 연산 결과를 다시 Stack에 push함
    피연산자의 숫자는 pop한 순서와 반대임
  3. 수식이 끝나면 마지막으로 Stack을 pop하여 출력


2-1. 후위표기법으로 계산 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
 
public class Stack_후위표기법계산 {
    private static Stack<Integer> numberStack = new Stack<>();
 
    public static void main(String[] args) {
        String input = "6528-*2/+";
        char[] inputChars = input.toCharArray();
        
        for(int i=0; i<inputChars.length; i++) {
            char c = inputChars[i];
            
            // 피연산자이면 스택에 추가
            if(!isOperation(c)) {
                int num = Integer.parseInt(new Character(c).toString());
                numberStack.push(num);
            } 
            else {
                int num1 = numberStack.pop();
                int num2 = numberStack.pop();
                
                int result = 0 ;
                switch(c) {
                case '+' :
                    result = num2 + num1;
                    break;
                case '-' :
                    result = num2 - num1;
                    break;
                case '*' :
                    result = num2 * num1;
                    break;
                case '/' :
                    result = num2 / num1;
                    break;
                }
                numberStack.push(result);
            }
            
        }
 
        int result = numberStack.pop();
        System.out.println(result); // -9
    }
    
    /**
     * 연산자 여부 확인
     * @param c
     * @return
     */
    public static boolean isOperation(char c) {
        char[] operations = {'(', ')', '*', '+', '-', '/'};
        for(int i=0; i<operations.length; i++) {
            if(c == operations[i]) {
                return true;
            }
        }
        return false;
    }
}
 
cs



백트래킹(Backtracking)

해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법이다. 이를 이용하여 최적화(Optimization) 문제와 결정(Desision)문제[각주:3]를 해결할 수 있다.

미로찾기 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Stack;
 
public class Stack백트래킹_미로찾기 {
    private static Stack<Pos> posStack = new Stack<>();
    private static Map<Pos, Boolean> visitHistory = new HashMap<>();
    
    // 0은 벽, 1은 통로, 2는 출구
    private static int[][] mazeArr = {
            {1, 0, 0, 0},
            {1, 1, 1, 0},
            {0, 1, 0, 0},
            {0, 1, 1, 1},
            {0, 2, 0, 0}
    };
    
    
    // 시계방향으로 이동가능한지 확인을 위함
    private static int[][] directionArr = {
            {1, 0}, // 우 
            {0, 1}, // 하
            {-1, 0}, // 좌
            {0, -1} // 상
    };
    
    public static void main(String[] args) {
        Pos now = new Pos(0, 0);
        posStack.push(now);
        
        do {
            System.out.println(now);
            visitHistory.put(now, true);
            
             Pos movablePos = move(now);
             if(movablePos != null) {
                  posStack.push(movablePos);    
             } else {
                movablePos = posStack.pop();
             }
            now = movablePos;
        } while(mazeArr[now.getY()][now.getX()] != 2);
    }
    
    /**
     * 이동할 수 있는 위치 반환. 이동할 수 없다면 null 반환
     * @param pos
     * @return
     */
    private static Pos move(Pos pos) {
        int x = pos.getX();
        int y = pos.getY();
        
        // 현재위치에서 시계방향으로 이동할 수 있는 곳을 체크함
        for(int i=0; i<4; i++) {
            int[] direction = directionArr[i];
            int moveX = direction[0];
            int moveY = direction[1];
            
            // 미로 범위안에서 이동가능 체크
            if((x + moveX) >= 0 && (x + moveX) <= 3
                    && (y + moveY) >= 0 && (y + moveY) <= 4) {
                if(mazeArr[y+moveY][x+moveX] == 0) {
                    continue;
                } 
                // 1(통로) 아니면 2(도착지)
                Pos movePos = new Pos(x+moveX, y+moveY);
                
                boolean isVisit = posStack.contains(movePos);
                if(!isVisit) {
                    Boolean hasVisitHisotry = visitHistory.get(movePos);
                    if(hasVisitHisotry == null) {
                        return movePos;
                    }
                }
            }
        }
        return null;
    }
}
 
 
class Pos {
    private int x;
    private int y;
    
    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return x;
    }
    
    public int getY() {
        return y;
    }
    
    @Override
    public boolean equals(Object obj) {
        if(obj == null || !(obj instanceof Pos)) {
            return false;
        }
        Pos pos = (Pos)obj;
        if(pos.getX() == x && pos.getY() == y) {
            return true;
        }
        return false;
    }
    
    public int hashCode() {
        return Objects.hash(x,y);
    }
    
    public String toString() {
        StringBuffer bf = new StringBuffer();
        bf.append("x: "+x+",");
        bf.append("y: "+y);
        return bf.toString();
    }
}
 
cs


  1. 연사자를 피연산자의 가운데 표기하는 방법 ex) A+B [본문으로]
  2. 연산자를 피연산자 뒤에 표기하는 방법. 컴퓨터로 연산할 때 자주쓰임 ex) AB+ [본문으로]
  3. 문제의 조건을 만족하는 해가 존재하는지의 여부를 'YES' OR 'NO'가 답하는 문제 ex) 미로 찾기, n-Queen, Map Coloring, 부분 집합의 해 [본문으로]
저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

백트래킹 - PowerSet  (0) 2019.05.15
백트래킹 - NQueen  (0) 2019.05.15
Stack(2) - DP(동적 계획법), DFS(깊이우선탐색)  (0) 2019.03.23
Stack(1) - 스택과 memorization  (0) 2019.03.19
문자열 (String)  (0) 2019.02.16

DP (동적 계획법)

DP란 Dynamic Programming의 약자이며 최적화 문제를 해결하는 알고리즘 설계기법 중 하나이다. 
  • 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제를 해결한다
  • 최종적으로 원래 주어진 입력의 문제를 해결한다
즉 점층적으로 문제를 해결해나가는 방식이다. 

앞선 예제인 피보나치 수열을 DP 방식으로 해결해보자. 
  • 문제를 부분 문제로 분할한다
    • F(N) = F(N-2) + F(N-1)
    • F(N-1) = F(N-3) + F(N-2)
    • ...
    • F(3) = F(2) + F(1)
  • 부분 문제로 나누는 일이 끝났으면 작은 부분부터 해를 구한다.
    • F(2) = 1, F(1) = 1 이다
  • 부분 문제의 해를 이용하여 전체의 해를 구한다.
    • F(2)와 F(1)을 이용하여 전체의 해를 구한다.

보통 Memorization는 재귀적 구조에 사용하는 것보다 반복문에서 사용하는 것이 효율적이다. 재귀 함수에서는 스택 오버플로우가 발생할 수 있다.

DP구현 - 피보나치 수열 ( 재귀함수 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class FibonacciNumberDP {
    private static Integer[] fArr; 
    public static void main(String[] args) {
        fArr = new Integer[46];
        fArr[0] = 0;
        fArr[1] = 1;
        fArr[2] = 1;
        
        int number = getFibonacciNumber(45);
        System.out.println(number);
    }
    
    public static int getFibonacciNumber(int index) {
        if(fArr[index] != null) {
            return fArr[index];
        }
        
        fArr[index] = getFibonacciNumber(index-2) + getFibonacciNumber(index-1);
        return fArr[index];
    }
}
 
cs



DP구현 - 피보나치 수열 (반복문)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class FibonacciNumberDP2 {
    private static Integer[] fArr; 
    public static void main(String[] args) {
        fArr = new Integer[46];
        fArr[0] = 0;
        fArr[1] = 1;
        fArr[2] = 1;
        
        for(int i=3; i<46; i++) {
            fArr[i] = fArr[i-2] + fArr[i-1];
        }
        int result = fArr[45];
        System.out.println(result);
    }
}
 
cs



DFS(깊이우선탐색)

비선형구조인 그래프 구조를 검색하는 두 가지 방법 중 하나이다. 

  • 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색한다
  • 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아온다
  • 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 방문, 순회한다
가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선탐색을 반복해야 하므로 후입선출 구조의 Stack을 사용하는게 적절하다.

DFS를 구현해보자

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.util.EmptyStackException;
import java.util.Stack;
 
public class DFS_깊이우선탐색 {
    public static boolean[] visitedArr = new boolean[7];
    
    public static void main(String[] args) {
        // 탐색 정점 표시 a,b,c,d,e,f 방문표시
        for(int i=0; i<visitedArr.length; i++) {
            visitedArr[i] = false;
        }
        // 그래프 연결
        
        Data g = new Data("g", 6, null);
        Data f = new Data("f", 5, g);
        Data e = new Data("e", 4, f);
        Data d = new Data("d", 3, f);
        Data c = new Data("c", 2, e);
        Data b = new Data("b", 1, d, e);
        Data a = new Data("a", 0, b, c);
        
        // 정점 스택
        Stack<Data> dataStack = new Stack<>();
 
        try {
            // 순회 시작점 a
            Data start = a;
            do {
                start.visit();
                
                // 방문하지않은 정점 찾기
                Data unvisit = start.getNotVisit();
                if(unvisit != null) {
                    dataStack.push(start);
                } 
                System.out.println("[정점]:"+start.getName()+"->");
                
                while(unvisit != null) {
                    System.out.println("\t[방문 정점]:"+unvisit.getName());
                    unvisit.visit();
                    // 방문하지 않은 정점찾기
                    if(unvisit.getNotVisit() != null) {
                        dataStack.push(unvisit);
                        unvisit = unvisit.getNotVisit();
                    } else {
                        unvisit = null;
                    }
                }
                start = dataStack.pop();
            } while(start != null);
        } catch(EmptyStackException e1) {
            // 방문결과확인
            for(int i=0; i<visitedArr.length; i++) {
                System.out.println(visitedArr[i]);
            }
        }
        
    }
}
 
class Data {
    private String name;
    private int index;
    private Data[] links;
    
    public Data(String name, int index, Data... data) {
        this.name = name;
        this.index = index;
        this.links = data;
    }
    
    public String getName() {
        return this.name;
    }
    
    public void visit() {
        DFS_깊이우선탐색.visitedArr[index] = true;
    }
    
    public boolean isVisit() {
        return DFS_깊이우선탐색.visitedArr[index];
    }
    
    public Data getNotVisit() {
        Data unvisit = null;
        
        if(links == null) {
            return null;
        }
        
        for(int i=0; i<links.length; i++) {
            Data link = links[i];
            if(!link.isVisit()) {
                unvisit = link;
                break;
            }
        }
        return unvisit;
    }
}
 
cs


저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

백트래킹 - NQueen  (0) 2019.05.15
Stack(3) - 계산기(문자열 수식), 백트래킹 기법  (0) 2019.04.04
Stack(1) - 스택과 memorization  (0) 2019.03.19
문자열 (String)  (0) 2019.02.16
Sort(정렬)에 대해서 - Selection Sort  (0) 2019.02.09

Stack

물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조를 말하며 선형구조[각주:1]를 가진다 마지막에 삽입한 자료가 가장 먼저 꺼내지는 후입선출(LIFO, Last-In-First-Out) 형태이다. 스택은 삽입(push), 삭제(pop), 공백확인(isEmpty), 반환(peek) 연산을 수행한다


스택의 연산



먼저 push 연산을 알아보자. 빈 스택에서는 top의 인덱스가 -1을 가리킨다. 이때 A를 push하면 스택의 맨 위에 A가 저장되고 top인덱스가 0이 된다. 이후 B를 push 하면 맨 위에 B가 저장되고 top 인덱스가 1이 증가된다. 스택의 크기를 넘어가면 overflow 가 발생한다.


pop 연산은 push의 반대이다. 스택에 A -> B -> C 순서대로 저장했을 때 pop 연산을 수행하면 C -> B -> A 순으로 반환하며 스택에서 삭제된다. 스택이 삭제될 때 top 인덱스는 1씩 감소한다. 


스택의 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
/**
 * push, pop 구현
 * @author troh
 *
 */
public class Stack구현1 {
    public static void main(String[] args) {
        Stack stack = new Stack(3);
        stack.push('A');
        stack.push('B');
        stack.push('C');
        
        System.out.println(stack.pop()); // C
        System.out.println(stack.pop()); // B
        System.out.println(stack.pop()); // A
    }
}
 
class Stack {
    private int top = -1;
    
    private char[] stack;
    
    public Stack(int size) {
        this.stack = new char[size];
    }
    
    public void push(char c) {
        if(top == stack.length) {
            throw new RuntimeException("Stack Overflow");
        }
        stack[++top] = c;
    }
    
    public char pop() {
        if(top == -1) {
            throw new RuntimeException("Stack Underflow");
        }
        return stack[top--];
    }
}
cs



스택의 활용 - 괄호 유효성

스택을 활용하여 괄호의 쌍이 올바르게 사용되었는지 판단하는 프로그램을 작성해보자. 괄호의 올바른 사용조건은 아래와 같다.
  • 여는 괄호와 닫는 괄호의 개수는 같아야한다
  • 여는 괄호가 닫는 괄호보다 먼저 나와야한다
  • 괄호사이에는 포함 관계만 존재해야한다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.EmptyStackException;
import java.util.Stack;
 
public class Stack활용_괄호 {
    public static void main(String[] args) {
        String str = "for(int i=0; i++; i<10)";
        boolean result = bracketCheck(str);
        System.out.println(result);
    }
    
    public static boolean bracketCheck(String str) {
        Stack<Character> bracketStack = new Stack<>();
        try {
            for(int i=0; i<str.length(); i++) {
                char c = str.charAt(i);
                if(isOpenBracket(c)) {
                    bracketStack.push(c);
                } else if(isCloseBracket(c)) {
                    bracketStack.pop();
                }
            }
            
            // 괄호의 쌍이 맞는지 확인
            if(!bracketStack.isEmpty()) {
                return false;
            }
            return true;
        } catch (EmptyStackException e) {
            // 여는 괄호보다 닫는 괄호가 먼저 나왔을 때는 유효하지 않는 경우임
            return false;
        }
    }
    
    /**
     * 여는 괄호인지 판단
     * @param c
     * @return
     */
    public static boolean isOpenBracket(char c) {
        return c == '(' ;
    }
    
    /**
     * 닫는 괄호인지 판단
     * @param c
     * @return
     */
    public static boolean isCloseBracket(char c) {
        return c == ')' ;
    }
}
 
cs



Memorization 

컴퓨터 프로그램을 실행하 ㄹ때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 피보나치 수열의 재귀함수[각주:2]를 Memorization을 사용하여 효율적으로 처리할 수 있다. 피보나치 수열을 재귀함수로 구현하면 중복 함수 호출이 많기 때문이다. 

다음은 피보나치 수열의 n번째 수를 구하는 일반적인 방법이다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
public class FibonacciNumbers {
    public static void main(String[] args) {
        int num = fibonacciNumber(21);
        System.out.println(num);
    }
    
    public static int fibonacciNumber(int index) {
        if(index <= 2) {
            return 1;
        }
        
        return fibonacciNumber(index-1) + fibonacciNumber(index-2);  
    }
}
 
cs


위의 알고리즘의 동작을 그림으로 살펴보면 많은 중복 호출이 있는것을 알 수 있다. fibonacciNumber 함수를 F로 표현하겠다.



위의 그림을 보면 함수가 중복적으로 많이 호출되는 것을 알 수 있다. 피보나치의 n이 커질수록 중복은 많아질 것이다. 이러한 중복을 해결하는 방법이 Memorization이다. 이를 이용하여 구현한 코드를 살펴보자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
public class FibonacciNumbers_Memorization {
    private static Integer[] memories ;
    
    public static void main(String[] args) {
        memories = new Integer[46];
        
        long start = System.currentTimeMillis();
        
        int num = fibonacciNumber(45);
        
        long end = System.currentTimeMillis();
        System.out.println(num);
        System.out.println("실행시간: "+ (end-start));
    }
    
    public static int fibonacciNumber(int index) {
        if(index <= 2) {
            return 1;
        }
        if(memories[index] != null) {
            return memories[index];
        } else {
            memories[index] = fibonacciNumber(index-1) + fibonacciNumber(index-2);
            return memories[index];
        }
    }
}
 
cs


Memorization을 이용하여 45번째 피보나치 숫자를 구한 실행시간은 0 밀리세컨으로 결과값이 나온다. 반면 Memorization을 사용하지 않았을 경우에는 약 3초(2919 밀리세컨)의 실행시간이 소요된다. 이러한 성능 차이는 숫자가 커짐에 따라 더욱 커질 것이다. 

  1. 선형구조: 자료 간의 관계가 1대 1의 관계를 가짐. 비선형구조: 자료 간의 관계가 1대 N의 관계를 가짐( 트리 자료구조 ) [본문으로]
  2. 자기 자신을 재호출하는 함수 [본문으로]
저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

Stack(3) - 계산기(문자열 수식), 백트래킹 기법  (0) 2019.04.04
Stack(2) - DP(동적 계획법), DFS(깊이우선탐색)  (0) 2019.03.23
문자열 (String)  (0) 2019.02.16
Sort(정렬)에 대해서 - Selection Sort  (0) 2019.02.09
검색  (0) 2019.02.09

String

문자열이란 말 그대로 문자를 나열한 것을 말합니다.  


패턴 매칭 알고리즘

- 본문이 되는 String에서 특정한 String을 패턴이라하며 이러한 패턴을 찾는 방법을 패턴 매칭이라고 합니다.

고지식한 패턴 검색(Brute Force)

- 본문 String을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식입니다.

특정 문자열에서 찾고자하는 패턴이 존재하는지 확인하려면 다음과 같은 알고리즘을 생각해볼 수 있습니다.

원본[0]과 패턴[0] 비교하여 다르면 원본의 인덱스를 증가시키고 패턴의 인덱스는 다시 0으로 이동시킵니다, 같으면 원본과 패턴의 인덱스를 서로 증가시키며 비교합니다.


고지식한 패턴 검색 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class BruteForce {
    public static void main(String[] args) {
        String origin = "abc 1, 2 ABC";
        char[] originArr = origin.toCharArray();
        
        String search = "1, 2";
        char[] searchArr = search.toCharArray();
        
        System.out.println(bruteForce(originArr, searchArr));
    }
    
    private static boolean bruteForce(char[] origin, char[] search) {
        int index = 0;
        while(index + search.length <= origin.length) {
            boolean match = true;
            for(int j=0; j<search.length; j++) {
                if(origin[index+j] != search[j]) {
                    index++;
                    match = false;
                    break;
                }
            }
            
            if(match) {
                return true;
            }
        }
        
        return false;
    }
}
 
cs




KMP 알고리즘

불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행한다. 


그림에서 보는것처럼 패턴(빨간색) 매칭 도중 E에서 매칭실패가 일어났을 때 비교 인덱스를 1만 이동하는 것이 아니라 4만큼 이동한다. 이 이동거리는 전처리 과정에서 미리 구할 수 있다. 



위의 배열은 전처리 과정으로 구한 배열이고 패턴 매칭이 실패할 경우 패턴의 인덱스를 저장하고 있다. B(1번째) 패턴 매칭이 실패했을 경우 패턴의 비교덱스를 A(0)번째로 이동한 후 다시 비교하라는 것이다. 

( 사실 인덱스0의 값이 왜 -1인지 모르겠음..)



KMP 알고리즘 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
public class KMP {
    public static void main(String[] args) {
        char[] data = "zzzzabcdzzabcdabcefz".toCharArray();
        char[] pattern = "abcdabcef".toCharArray();
        int[] failIndex = {0, 0, 0, 0, 0, 1, 2, 3, 0};
        
        System.out.println(solution(data, pattern, failIndex));
    }
    
    public static int solution(char[] data, char[] pattern, int[] failIndex) {
        int patternIndex = 0 ;
        int resultIndex = -1;
        for(int i=0; i<data.length-pattern.length+1; i++) {
            boolean isMatch = true;
            for(int j=patternIndex; j<pattern.length; j++) {
                
                if(data[i+j] != pattern[j]) {
                    patternIndex = failIndex[j];
                    isMatch = false;
                    break;
                }
            }
            
            if(isMatch) {
                resultIndex = i;
                break;
            }
        }
        
        return resultIndex;
    }
}
 
cs


보이어-무어 알고리즘

패턴을 오른쪽에서 왼쪽으로 비교하고 패턴에 오른쪽 끝에 있는 문자가 불일치하고, 이 문자가 패턴 내에 존재하지 않는 경우 이동거리는 패턴의 길이 만큼이 된다.




위의 예시는 문자열의 B와 패턴의 끝인R은 불일치하고 B는 WATER에 존재하지 않으므로 WATER의 길이인 5만큼 이동한 예시이다.  불일치하는 문자가 패턴에 존재하는 경우는 어떻게 될까?


문자열의 A와 패턴의 끝인 R은 불일치하지만 A는 WATER에 존재하므로 3칸을 이동하여 A의 위치를 일치시킨다. 



보이어-무어 알고리즘에서도 KMP 알고리즘처럼 패턴의 문자가 불일치할 경우 이동해야 할 위치를 데이터 전처리하여 저장한다.

패턴과 불일치하는 문자가 W일 경우는 패턴을 4칸 이동, A일 경우 3칸이동 W, A, T, E, R 외의 모든 문자는 5칸을 이동하면 된다. 

보이어-무어 알고리즘 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.HashMap;
import java.util.Map;
 
public class 보이어_무어 {
    public static void main(String[] args) {
        char[] data = "a pattern matching algorithm".toCharArray();
        char[] pattern = "rithm".toCharArray();
        Map<Character, Integer> failIndex = new HashMap<>();
        failIndex.put('r', 4);
        failIndex.put('i', 3);
        failIndex.put('t', 2);
        failIndex.put('h', 1);
        failIndex.put('m', 0);
        System.out.println(solution(data, pattern, failIndex));
    }
    
    public static int solution(char[] data, char[] pattern, Map<Character, Integer> failIndex) {
        
        int patternIndex = pattern.length-1;
        
        for(int i=0; i<data.length-pattern.length+1; i=i+patternIndex) {
            boolean match = true;
            for(int j=pattern.length-1; j>=0; j--) {
                if(data[i+j] != pattern[j] ) {
                    char failChar = data[i+j];
                    Integer index = failIndex.get(failChar);
                    if(index == null) {
                        patternIndex = pattern.length;
                    } else {
                        patternIndex  = index;
                    }
                    match = false;
                    break;
                }
            }
            
            if(match) {
                return i;
            }
        }
        return -1;
    }
}
 
cs


저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

Stack(2) - DP(동적 계획법), DFS(깊이우선탐색)  (0) 2019.03.23
Stack(1) - 스택과 memorization  (0) 2019.03.19
Sort(정렬)에 대해서 - Selection Sort  (0) 2019.02.09
검색  (0) 2019.02.09
부분 집합 문제  (0) 2019.02.09

선택 정렬 

주어진 자료중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식입니다. 저장되어 있는 자료를 전체 정렬한 뒤에 k 번째의 원소를 가져오는 것과는 차이가 있는 것 같습니다.

  1. 주어진 리스트 중에서 최소값을 찾습니다.
  2. 그 값을 리스트의 맨 앞에 위치한 값과 교환합니다.
  3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 작업을 반복합니다.


{64, 25, 10, 22, 11}을 선택 정렬하는 과정

1. 리스트에서 최소값을 찾습니다. 현재 시작위치는 64이고 최소값은 10입니다.

64 

25 

10 

22 

11 


2. 리스트의 맨 앞에 위치한 값과 교환합니다. 10은 정렬이 완료되었습니다.

10 

25 

64 

22 

11 


3. 아직 정렬되지 않은 리스트에서 최소값을 찾습니다. 현재 위치는 25이고 10을 제외한 최소값은 11입니다. 

10 

25 

64 

22 

11 


4. 아직 정렬되지 않은 리스트의 맨 앞에 위치한 값과 교환합니다. 10과 11은 정렬이 완료되었습니다.

10 

11 

64 

22 

25 


5. 위의 작업을 반복합니다..



Selection Sort 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
public class 선택정렬 {
    public static void main(String[] args) {
        int[] arr = {64, 25, 10, 22, 11};
        int[] sortedArr = selectionSort(arr);
        
        for(int i=0; i<sortedArr.length; i++) {
            System.out.printf(sortedArr[i]+" ");
        }
    }
    
    private static int[] 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 = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        return arr;
    }
}
 
cs


저작자표시

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

Stack(1) - 스택과 memorization  (0) 2019.03.19
문자열 (String)  (0) 2019.02.16
검색  (0) 2019.02.09
부분 집합 문제  (0) 2019.02.09
2차원 배열  (0) 2019.02.03

+ Recent posts

티스토리툴바