버블정렬

버블정렬이란 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식입니다.

알고리즘 이해하기

두 인접한 원소를 검사하여 정렬하는 방법입니다. 시간 복잡도가 O(n^2)로 느린편입니다. 


{ 3, 2, 1, 5, 4 }을 원소로 가지는 배열 arr을 오름차순으로 정렬해보도록 하겠습니다.


위의 과정을 반복합니다. 우연히도 이미 정렬이 완료되어있네요 ㅎㅎ..


알고리즘 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = { 3, 2, 1, 5, 4 };
 
        arr = bubbleSort(arr);
        for (int i = 0; i < 5; i++) {
            System.out.println(arr[i]);
        }
    }
 
    private static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}
 
cs


저작자표시

'알고리즘 > 정렬' 카테고리의 다른 글

삽입정렬(Insert Sort)  (0) 2019.09.08

수 정렬하기

이번 포스팅 문제는 2750 문제입니다. 시간복잡도 O(n^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
package BackJoon.수정렬;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/2750
 * 시간복잡도 O(n^2)
 * @author troh
 *
 */
public class _2750_수정렬하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int[] arr = new int[count];
        
        for(int i=0; i<count; i++) {
            arr[i] = sc.nextInt();
        }
        
        arr = sort(arr);
        for(int i=0; i<count; i++) {
            System.out.println(arr[i]);
        }
    }
    
    private static int[] sort(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr.length-i-1; j++) {
                if(arr[j] > arr[j+1]) {
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
}
 
cs

배운점

버블 정렬은 시간복잡도 O(n^2) 란걸 다시한번 새겼으며 다시한번 정리해보았습니다. 같은 시간복잡도를 가지는 삽입 정렬에 대해서도 정리해보았습니다.

저작자표시

'알고리즘 > BackJoon' 카테고리의 다른 글

[백준 온라인저지]괄호 - 스택  (0) 2019.09.12
[백준 온라인저지]단어 뒤집기 - 스택  (0) 2019.09.12
[백준 온라인저지]영화감독숌 - 브루트포스(5)  (0) 2019.09.06
[백준 온라인저지]체스판 다시 칠하기 - 브루트포스(4)  (0) 2019.09.04
[백준 온라인저지]덩치 - 브루트포스(3)  (0) 2019.09.03

영화감독 숌

이번 포스팅 문제는 1436번 문제입니다. 이 문제는 정답률이 50%가 안되네요.. 이문제 역시 브루트포스 알고리즘을 사용하여 풀이했습니다.

문제요약

666을 포함하는 숫자중에 작은수부터 n번째 숫자를 찾는 문제입니다. 예를 들어 1번째 666을 포함하는 숫자는 666이고 2번째 666을 포함하는 숫자는 1666 입니다. 

풀이전략

1. 1부터 무한대까지 숫자를 검사
2. 각 숫자가 666을 포함하는지 검사
3. 666을 포함하면 count를 1씩 증가시키고 입력받은 n과 같으면 출력

구현하기

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
package BackJoon.브루트포스;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/1436
 * @author troh
 *
 */
public class _1436_영화감독숌 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int count = 0;
        int num = 0;
        while(n != count) {
            num++;
            if(isEndNumber(num)) {
                count ++;
            }
        }
        System.out.println(num);
    }
    
    private static boolean isEndNumber(int num) {
        int temp = num;
        while(temp > 100) {
            if(temp%10 == 6 && temp/10 % 10  == 6 && temp/10/10 % 10 == 6) {
                return true;    
            }
            temp = temp/10;
        }
        return false;
    }
}
 
cs

배운점

처음에는 n번째 숫자를 만드려고 했는데 패턴이 너무 어려운 것 같아 1부터 숫자를 증가시키며 666을 포함하는지 체크하는 식으로 관점을 바꿨습니다. 666을 체크하는 알고리즘은 처음에는 String을 이용하여 "666"을 포함하는지 검사하였는데 메모리와 수행속도가 너무 높아서 알고리즘을 변경하였습니다. 

저작자표시

'알고리즘 > BackJoon' 카테고리의 다른 글

[백준 온라인저지]단어 뒤집기 - 스택  (0) 2019.09.12
[백준 온라인저지]수 정렬하기 - 정렬  (0) 2019.09.07
[백준 온라인저지]체스판 다시 칠하기 - 브루트포스(4)  (0) 2019.09.04
[백준 온라인저지]덩치 - 브루트포스(3)  (0) 2019.09.03
[백준 온라인저지]분해합 - 브루트포스(2)  (0) 2019.09.01

체스판 다시 칠하기

이번 포스팅 문제는 1018번 문제입니다. 이 문제 역시 브루트포스 알고리즘으로 풀이했습니다.

문제요약

M*N 단위 정사각형으로 이루어진 보드가 있을 때 8X8 체스판 모양으로 잘라서 다시 색칠하려고 합니다.  이때 체스판 모양을 만들기위해 다시 색칠해야 하는 정사각형의 최소 개수를 구하는 문제입니다.


풀이전략

1. 좌상단을 기준으로 체스판 크기만큼 잘라낸다. 
2. 잘라낸 체스판의 좌상단이 흰색일 때 다시 칠해야하는 개수를 구한다
3. 잘라낸 체스판의 좌상단이 검은색일 때 다시 칠해야하는 개수를 구한다
4. (2), (3)번의 값을 최소값으로 저장한다.
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package BackJoon.브루트포스;
 
import java.util.Scanner;
 
public class _1018_체스판다시칠하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int height = sc.nextInt();
        int width = sc.nextInt();
        
        char[][] board = new char[height][width];
        for(int h=0; h<height; h++) {
            String row = sc.next();
            board[h] = row.toCharArray();
        }
        
        int min = 64;
        for(int h=0; h<height-7; h++) {
            for(int w=0; w<width-7; w++) {
                int changeCount = getChangeCount(board, h, w, h+7, w+7);
                if(changeCount < min) {
                    min = changeCount;
                }
            }
        }
        System.out.println(min);
    }
    
    private static int getChangeCount(char[][] board, int h1, int w1, int h2, int w2) {
        int count = 0;
        // 8X8 모양으로 체스판 생성
        char[][] chessBoard = new char[8][8];
        for(int h=0; h<8; h++) {
            for(int w=0; w<8; w++) {
                chessBoard[h][w] = board[h1+h][w1+w];
            }
        }
        // 새로만든 체스판을 순회하면서 바뀌어야하는 곳을 체크후 변경
        for(int h=0; h<8; h++) {
            // 세로줄이 같을 경우 변환이 필요
            if(h != 7 && (chessBoard[h][0] == chessBoard[h+1][0])) {
                chessBoard[h+1][0] = chessBoard[h][0] =='B'? 'W':'B';
                count ++;
            }
            // 가로줄이 같을 경우 변환이 필요
            for(int w=0; w<8-1; w++) {
                char c1 = chessBoard[h][w];
                char c2 = chessBoard[h][w+1];
                if(c1 == c2) {
                    count ++;
                    chessBoard[h][w+1] = c1=='B'? 'W':'B';
                }
            }
        }
        // 체스판의 좌상단이 흰색의 경우 n개 바꿔야한다면 검은색의 경우는 64-n개를 바꿔야 정상적인 체스판이 완성됨
        if(count <= 32) {
            return count;
        } else {
            return 64-count;
        }
    }
}
 
cs


배운점

제가 생각하는 위 문제의 핵심은 아래와 같습니다. 

  • 모든 경우의 수 구하기(board 에서 만들수있는 8x8 체스판)
  • 각 체스판에서 색을 변화해야 하는 횟수 구하기
두 번째 핵심 로직을 개선하면 속도도 좀 더 나올 것 같네요.. 
1차원 배열로 풀어보려다가 더 복잡해질 것 같아서 그냥 2차원 배열로 풀이했습니다.


저작자표시

'알고리즘 > BackJoon' 카테고리의 다른 글

[백준 온라인저지]수 정렬하기 - 정렬  (0) 2019.09.07
[백준 온라인저지]영화감독숌 - 브루트포스(5)  (0) 2019.09.06
[백준 온라인저지]덩치 - 브루트포스(3)  (0) 2019.09.03
[백준 온라인저지]분해합 - 브루트포스(2)  (0) 2019.09.01
[백준 온라인저지]블랙잭 - 브루트포스(1)  (0) 2019.09.01

덩치

이번 포스팅 문제는 7568번 문제입니다. 이 문제 역시 브루트포스를 이용하여 풀이하였습니다.

문제요약

사람의 덩치를 비교할 때 키와 몸무게를 이용합니다. 사람1의 키와 몸무게가 사람2의 키와 몸무게보다 모두 더 클 때 사람1의 덩치가 사람2보다 크다고 말합니다. 덩치 순위는 자신보다 덩치가 큰 사람의 수+1 이며 키와 몸무게가 같더라도 같은 덩치순위를 가질 수 있을 때 주어진 사람들의 덩치 순위를 출력하는 문제입니다. 

풀이전략

1. 키와 몸무게를 데이터로 표현(저는 Person 클래스를 작성하여 이용)
2. 키와 몸무게를 비교하는 알고리즘 구현
3. 이중 반복문을 이용하여 자신보다 덩치가 큰 사람이 있을 때 덩치순위를 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
package BackJoon.브루트포스;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/7568
 * @author troh
 *
 */
public class _7568_덩치 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int personNumber = sc.nextInt();
        Person[] persons = new Person[personNumber];
        for(int i=0; i<personNumber; i++) {
            int weight = sc.nextInt();
            int height = sc.nextInt();
            
            Person p = new Person(weight, height);
            persons[i] = p;
        }
        
        int[] ranks = getRanks(persons);
        for(int i=0; i<ranks.length; i++) {
            System.out.printf("%d ", ranks[i]);
        }
    }
    
    private static int[] getRanks(Person[] persons) {
        int[] ranks = new int[persons.length];
        
        // 모든 사람들을 순회하며 자신보다 덩치가 크면 rank를 증가시켜서 저장시킴
        for(int i=0; i<persons.length; i++) {
            int p1Rank = 1;
            Person p1 = persons[i];
            
            for(int j=0; j<persons.length; j++) {
                if(i==j) continue;
                
                Person p2 = persons[j];
                if(p2.compareTo(p1) == 1) {
                    p1Rank ++;
                }
            }
            ranks[i] = p1Rank;
        }
        return ranks;
    }
}
 
class Person implements Comparable<Person>{
    private int weight;
    private int height;
    
    public Person(int weight, int height) {
        this.weight = weight;
        this.height = height;
    }
 
    // Comparable 인터페이스를 구현하여 덩치비교
    @Override
    public int compareTo(Person o) {
        if(this.weight > o.weight && this.height > o.height ) {
            return 1; 
        } else if((this.weight == o.weight || this.weight > o.weight) && (this.height == o.height || this.height < o.height)) {
            return 0;
        } else if((this.weight == o.weight || this.weight < o.weight) && (this.height == o.height || this.height > o.height)) {
            return 0;
        } else {
            return -1;
        }
    }
}
 
cs

배운점

다차원 배열을 이용했어도 문제를 해결했을 수 있을 것 같습니다. 그랬으면 메모리 사용량이 줄지 않을까 생각됩니다..

저작자표시

'알고리즘 > BackJoon' 카테고리의 다른 글

[백준 온라인저지]영화감독숌 - 브루트포스(5)  (0) 2019.09.06
[백준 온라인저지]체스판 다시 칠하기 - 브루트포스(4)  (0) 2019.09.04
[백준 온라인저지]분해합 - 브루트포스(2)  (0) 2019.09.01
[백준 온라인저지]블랙잭 - 브루트포스(1)  (0) 2019.09.01
[백준 온라인저지]Adding Reversed Numbers - 그리디알고리즘(1)  (0) 2019.08.31

분해합

이번 포스팅 문제는 2231번 문제입니다. 이 문제 역시 브루트포스 알고리즘을 통해 해결하였습니다.
그럼 문제를 풀어보도록 하겠습니다

문제요약

자연수 n이 주어졌을 때 자연수n의 생성자 중 최소값을 구하는 문제입니다.

어떤 자연수 n의 분해합이 m일 경우 m을 n의 생성자라 합니다. 분해합은 자신과 각 자리수의 합을 말합니다. 
예를 들어 자연수 256은 분해합 245를 가지는데 그 이유는 256 = 245 + 2 + 4 + 5 이기 때문입니다. 

풀이전략

1. 생성자의 최소값을 구하는 문제이고 생성자는 n보다 클수가 없기때문에 1부터 n까지 반복문을 실행합니다.
2. 해당 자연수가 생성자라고 판별되면 그 값이 생성자의 최소값입니다.

구현하기

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
package BackJoon.브루트포스;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/2231
 * @author troh
 *
 */
public class _2231_분해합 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(getMinConstructor(n));
    }
    
    private static int getMinConstructor(int n) {
        int min = 0;
        for(int i=1; i<n; i++) {
            boolean isConstructor = isConstructor(n, i);
            if(isConstructor) {
                min = i;
                break;
            }
        }
        return min;
    }
    
    private static boolean isConstructor(int n, int m) {
        // sum을 m으로 초기화한 후 1의자리수부터 sum에 더한 다음 최종적으로 n과 같은지 확인함
        int sum = m;
        while(m/10 != 0) {
            sum = sum + (m % 10);
            m = m / 10;
        }
        sum = sum + (m % 10);
        return sum == n ; 
    }
}
 
cs

배운점

제가 생각하는 문제의 핵심은 

  • 생성자는 n보다 클 수 없고 최소값을 찾는 문제이기 때문에 1 -> n까지 반복문을 실행하고 처음 찾는 생성자가 최소값이라는 점
  • 각 자리수를 더하는 알고리즘
이정도 인 것 같습니다. 가장 큰 자리수부터 더하려고 했는데 자리수를 구해야하고 알고리즘이 복잡해지는 것 같아 관점을 바꿔서
1의 자리수부터 더하도록 수정했습니다. 


저작자표시

'알고리즘 > BackJoon' 카테고리의 다른 글

[백준 온라인저지]영화감독숌 - 브루트포스(5)  (0) 2019.09.06
[백준 온라인저지]체스판 다시 칠하기 - 브루트포스(4)  (0) 2019.09.04
[백준 온라인저지]덩치 - 브루트포스(3)  (0) 2019.09.03
[백준 온라인저지]블랙잭 - 브루트포스(1)  (0) 2019.09.01
[백준 온라인저지]Adding Reversed Numbers - 그리디알고리즘(1)  (0) 2019.08.31

블랙잭

이번 포스팅 문제는 2798번 문제입니다. 이 문제는 브루트포스 알고리즘을 이용하여 풀어냈습니다. 
브루트포스 알고리즘이란 모든 경우의 수를 구한 다음 그 중 최적의 해를 찾아내는 접근 방법입니다. 
그럼 문제를 풀어보도록 하겠습니다.

문제요약

n개의 카드 중 3개의 합을 구하는데 정수 m을 넘지않는 최대값을 구하는 문제입니다.

풀이전략

01. n개의 카드중 3개를 추출하는 모든 경우의 수를 구한뒤 합을 구함
02. 합이 m을 넘지 않는지 확인하고 이전 최대값과 비교하여 최대값 갱신

구현하기

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
package BackJoon.브루트포스;
import java.util.Scanner;
/**
 * https://www.acmicpc.net/problem/2798
 * @author troh
 *
 */
public class _2798_블랙잭 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m  = sc.nextInt();
        int[] cards = new int[n];
        for(int i=0; i<cards.length; i++) {
            cards[i] = sc.nextInt();
        }
        int result = getMaxCardsSum(cards, n, m);
        System.out.println(result);
    }
    
    private static int getMaxCardsSum(int[] cards, int n, int m) {
        int max = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(i == j) continue;
                for(int k=0; k<n; k++) {
                    if(k == i || k == j) continue;
                    // n개의 원소중 3개를 취합
                    int cardsSum = cards[i] + cards[j] + cards[k];
                    // 원소의 합이 m을 넘으면 무시하고
                    if(cardsSum > m) {
                        continue;
                    }
                    // 현재 최대값과 비교하여 갱신
                    max = max < cardsSum ? cardsSum : max;
                }
            }
        }
        return max;
    }
}
 
cs

배운점

문제의 핵심은 n개의 원소중 3개를 선택할 수 있는 경우의 수를 구하는 부분이였던 것 같습니다. 


저작자표시

'알고리즘 > BackJoon' 카테고리의 다른 글

[백준 온라인저지]영화감독숌 - 브루트포스(5)  (0) 2019.09.06
[백준 온라인저지]체스판 다시 칠하기 - 브루트포스(4)  (0) 2019.09.04
[백준 온라인저지]덩치 - 브루트포스(3)  (0) 2019.09.03
[백준 온라인저지]분해합 - 브루트포스(2)  (0) 2019.09.01
[백준 온라인저지]Adding Reversed Numbers - 그리디알고리즘(1)  (0) 2019.08.31

Adding Reversed Numbers 

이번 포스팅 문제는 3486번 문제입니다. 이 문제는 탐욕 알고리즘(Greedy Algorithm) 문제인데 이 알고리즘 관점에서 문제를 풀어보기 위해

신경을 많이 썼습니다. 


그리디 알고리즘이란 각 부분적인 상황에서 최적의 해를 선택해나가면서 최종적인 해를 구하는 방법인데 이 결과가 항상 전체 상황의 최적의 해는 

아닐 수 있다는 점을 주의해야 합니다. 


그럼 문제를 풀어보도록 하겠습니다 .


조건

2개의 정수가 주어지고 각 정수를 역순으로 나열(123일 경우 -> 321)한 후 덧셈을 하고 그 덧셈 결과를 다시 역순으로 나열하여 출력하는 문제입니다.

풀이전략

01. 각 정수를 역순으로 변환
02. 변환된 정수를 덧셈
03. 덧셈 결과를 역순으로 변환

구현하기

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
package BackJoon.그리디;
import java.util.Scanner;
/**
 * https://www.acmicpc.net/problem/3486
 * @author troh
 * 
 * INPUT: N case, 2개의 정수
 * OUTPUT: 입력된 각 정수의 역순의 합을 역순 
 */
public class _01_AddingReversedNumbers {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int testCase = sc.nextInt();
        for(int i=0; i<testCase; i++) {
            int num1 = sc.nextInt();
            int num2 = sc.nextInt();
            int result = getSolution(num1, num2);
            System.out.println(result);
        }
    }
    
    private static int getSolution(int num1, int num2) {
        num1 = reverse(num1);
        num2 = reverse(num2);
        return reverse(num1+ num2);
    } 
    
    private static int reverse(int num) {
        int reverseNum = 0;
        while(num/10 != 0) {
            reverseNum = reverseNum*10 + num % 10;
            num /= 10;
        }
        reverseNum = reverseNum*10 + num % 10;
        return reverseNum;
    }
}
 
cs

배운점..

그리디 알고리즘으로 문제에 접근한다에 대해 고민을 많이 할 수 있었고 사전적 정의를 실제 문제에 적용하는게 쉽지 않았습니다. 
개인적인 생각의 그리디 알고리즘 접근 방법은 "각 단계" 와 "최적의 해"를 정의할 수 있어야 한다고 생각합니다. 제가 구현한 코드에서는
"각 단계" 란 "정수 역변환, 덧셈, 결과 역변환"이고 "최적의 해"란 변환하는 알고리즘 이였던 것 같습니다.

문제가 어려웠던건 아니지만 그리디알고리즘 개념이 잘 잡히지 않네요.. 이상입니다



저작자표시

'알고리즘 > BackJoon' 카테고리의 다른 글

[백준 온라인저지]영화감독숌 - 브루트포스(5)  (0) 2019.09.06
[백준 온라인저지]체스판 다시 칠하기 - 브루트포스(4)  (0) 2019.09.04
[백준 온라인저지]덩치 - 브루트포스(3)  (0) 2019.09.03
[백준 온라인저지]분해합 - 브루트포스(2)  (0) 2019.09.01
[백준 온라인저지]블랙잭 - 브루트포스(1)  (0) 2019.09.01

+ Recent posts

티스토리툴바