소수하기

이번 포스팅 문제는 1929번 문제입니다.


문제요약

에라토스테네스의 체 알고리즘을 이용하여 자연수 M이상 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
package BackJoon.수학;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/1929
 * 에라토스테네스의 체
 * @author troh
 */
public class _1929_소수구하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        
        boolean[] check = new boolean[num2+1];
        for(int i=2; i<=num2; i++) {
            if(!check[i]) {
                for(int j=i+i; j<=num2; j=j+i) {
                    check[j] = true;
                }
            }
        }
        
        int count = 0;
        for(int i=num1; i<=num2; i++) {
            if(i == 1) continue;
            
            if(!check[i]) {
                System.out.println(i);
            }
        }
    }
}
 
cs

배운점

에라토스테네스의 체

저작자표시

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

[백준 온라인저지]GCD합 - 수학  (0) 2019.10.23
[백준 온라인저지]스택 수열 - 스택  (0) 2019.09.12
[백준 온라인저지]괄호 - 스택  (0) 2019.09.12
[백준 온라인저지]단어 뒤집기 - 스택  (0) 2019.09.12
[백준 온라인저지]수 정렬하기 - 정렬  (0) 2019.09.07

이번 포스팅 문제는 9613번 문제입니다


문제요약

양의 정수 n개가 주어졌을 때 가능한 모든 쌍의 GCD의 합을 구하는 문제


풀이전략

양의 정수n개가 다음과 같이 {10, 20, 30, 40} 이렇게 주어졌다면 
  1. 10과 {20, 30, 40} 의 GCD를 각각 구해서 결과값에 더함
  2. 20과 {30, 40} 의 GCD를 각각 구해서 결과값에 더함
  3. 30과 {40}의 GCD를 구해서 결과값에 더함

구현하기

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
package BackJoon.수학;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/9613
 * @author troh
 */
public class _9613_GCD합 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 테스트 횟수
        int c = sc.nextInt();
        
        for(int i=0; i<c; i++) {
            // 입력받을 정수 개수
            int s = sc.nextInt();
            
            // 정수 입력
            int[] arr = new int[s];
            for(int j=0; j<s; j++) {
                arr[j] = sc.nextInt();
            }
            
            // gcd 합 출력
            System.out.println(sumGcd(arr));
        }
    }
    
    private static long sumGcd(int[] arr) {
        long sum = 0;
        for(int i=0; i<arr.length-1; i++) {
            for(int j=i+1; j<arr.length; j++) {
                sum += gcd(arr[i], arr[j]);
            }
        }
        return sum;
    }
    
    private static int gcd(int a, int b) {
        if(b == 0) 
            return a;
        else
            return gcd(b, a%b);
    }
}
 
cs

배운점

자연수 A, B 최소공배수(GCD)를 구하는 알고리즘을 알게되었다. 

저작자표시

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

[백준 온라인저지]소수구하기 - 수학  (0) 2019.10.23
[백준 온라인저지]스택 수열 - 스택  (0) 2019.09.12
[백준 온라인저지]괄호 - 스택  (0) 2019.09.12
[백준 온라인저지]단어 뒤집기 - 스택  (0) 2019.09.12
[백준 온라인저지]수 정렬하기 - 정렬  (0) 2019.09.07

스택 수열

이번 포스팅 문제는 1874번 문제입니다.


문제요약

문제에서는 수열이 주어지는데 이 수열을 스택으로 만들 수 있는지 없는지를 판단하는 문제입니다. 
예를 들어 {4, 3, 6, 8, 7, 5, 2, 1} 수열이 주어지고 스택에 삽입하는 수는 1부터 순차적으로 증가될 때 이 수열이 스택을 이용해서 어떻게 만들어지는지 알아보도록 하겠습니다.


풀이전략

  1. 수열원소 > 자연수라면 "자연수 == 원소"일 때 까지  스택에 push() 합니다
  2. 수열원소 < 자연수라면 이미 스택에 수열원소가 들어가 있다는 뜻입니다. 그럼 스택에서 pop()을 수행하여 수열원소를 찾습니다.
    하지만 이 때 "pop()에서 얻은 값이 != 수열원소"라면 해당 수열은 스택으로 만들 수 없는 수열을 뜻합니다. 왜냐하면 스택은 LIFO 구조이기 때문에 최상단 아래 원소를 구할 수 없기 때문입니다.

구현하기

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
package BackJoon.스택;
 
import java.util.Scanner;
import java.util.Stack;
 
public class _1874_스택수열 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        int[] arr = new int[T];
        for(int i=0; i<T; i++) {
            arr[i] = sc.nextInt();
        }
        
        String s = getSolution(arr);
        System.out.println(s);
    }
    
    private static String getSolution(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        StringBuffer bf = new StringBuffer();
        int num = 1; // 자연수
        for(int i=0; i<arr.length; i++) {
            int e = arr[i]; // 만들어야 하는 수열요소
            
            // 자연수가 만들어야하는 요소보다 작을 때
            if(num <= e) {
                while(num <= e) {
                    // 자연수를 증가시키며 스택에 추가
                    stack.push(num++);
                    bf.append("+\n");
                    
                    // 만들어야하는 요소까지 스택에 담았다면 꺼냄
                    if(num > e) {
                        stack.pop();
                        bf.append("-\n");
                    }
                }
            } 
            // 자연수가 만들어야하는 요소보다 클 때 -> 만들어야하는 요소는 이미 스택에 들어있다는 의미
            else {
                int n = stack.pop();
                // 스택의 가장 위의 수(n)가 만들어야하는 요소(e)보다 크다면 pop() 을 했을 때 n이 출력되므로 요소를 출력할 수 없음
                if(n > e) {
                    return "NO";
                } //  
                else {
                    bf.append("-\n");
                }
            }
        }
        return bf.toString();
    }
}
 
cs

배운점

알고리즘을 생각하는 것보다 알고리즘을 코드로 옮기는게 역시나 훨씬 어려웠습니다. 전반적인 알고리즘을 구현해놓고 제약사항(인덱스의 마지막 등)을 상세하게 구현해주는게 문제 푸는게 좀 더 수월한 것 같습니다 

저작자표시

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

[백준 온라인저지]소수구하기 - 수학  (0) 2019.10.23
[백준 온라인저지]GCD합 - 수학  (0) 2019.10.23
[백준 온라인저지]괄호 - 스택  (0) 2019.09.12
[백준 온라인저지]단어 뒤집기 - 스택  (0) 2019.09.12
[백준 온라인저지]수 정렬하기 - 정렬  (0) 2019.09.07

괄호

이번 포스팅 문제는 9012번 입니다. 이번 문제 역시 스택을 이용하여 풀이하였습니다.

문제요약

주어진 문자열이 올바른 괄호인지 판단하는 문제입니다. 올바른 괄호란 여는 괄호, 닫는 괄호의 순서와 수량이 같은 괄호를 말합니다.

풀이전략

그럼 올바른 괄호를 판단하는 기준을 생각해보겠습니다. 
  1. 여는 괄호와 닫는 괄호의 개수가 같아야 합니다.
  2. 여는 괄호와 닫는 괄호의 순서가 올바라야 합니다
    1. 닫는 괄호가 나왔을 때 이전 여는 괄호 중에서 가장 가까운 괄호와 매핑된다.
    2. 닫는 괄호가 나왔을 때 이전 여는 괄호 중에서 매핑되지 않은 여는 괄호가 하나이상 존재해야 한다.
그럼 스택을 이용한 풀이 전략을 짜보도록 하겠습니다.
  1. 주어진 문자열을 문자 배열로 변환합니다
  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
package BackJoon.스택;
 
import java.util.Scanner;
import java.util.Stack;
 
public class _9012_괄호 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        sc.nextLine();
        
        for(int i=0; i<T; i++) {
            String s = sc.nextLine();
            String solution = getSolution(s);
            System.out.println(solution);
        }
    }
    
    private static String getSolution(String s) {
        char[] charArr = s.toCharArray();
        
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<charArr.length; i++) {
            char c = charArr[i];
            // 여는 괄호라면 스택에 추가
            if(c == '(') {
                stack.push(c);
            } // 닫는 괄호라면 스택에서 꺼냄 
            else if(c == ')') {
                // 꺼낼 여는 괄호가 없다면 여는 괄호와 닫는 괄호 순서가 맞지않음
                if(stack.isEmpty()) {
                    return "NO";
                }
                stack.pop();
            }
        }
        // 스택이 비어있지않다면 여는 괄호와 닫는괄호 갯수가 맞지않음
        return stack.isEmpty() ? "YES" : "NO";
    }
}
 
cs

배운점

스택을 사용한 가장 큰 이유는 "닫는 괄호가 나왔을 때 가장 가까운 여는 괄호와의 매핑" 이였습니다. 스택의 성질중 가장 마지막에 삽입한 원소가

가장 먼저 추출된다는 성질이 있기때문에 적합하다고 판단하였습니다. 

저작자표시

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

[백준 온라인저지]GCD합 - 수학  (0) 2019.10.23
[백준 온라인저지]스택 수열 - 스택  (0) 2019.09.12
[백준 온라인저지]단어 뒤집기 - 스택  (0) 2019.09.12
[백준 온라인저지]수 정렬하기 - 정렬  (0) 2019.09.07
[백준 온라인저지]영화감독숌 - 브루트포스(5)  (0) 2019.09.06

단어 뒤집기

이번 포스팅 문제는 9093번 문제입니다. 이 문제는 스택의 성질을 이용하여 풀이하였습니다.

스택은 LIFO(Last In First Out) 성질 즉, 마지막 넣은 요소를 처음으로 얻을 수 있다는 것입니다. 자 이 성질을 염두에 두고 문제를 풀어보도록 하겠습니다.


문제요약

주어진 문장에서 단어(띄어쓰기로 구분)단위로 단어를 뒤집으면서 출력하는 문제입니다. 예를 들어
"I am happy today" 는 4개의 단어 I, am, happy, today로 나누어지고 이 4단어를 각각 역순으로 출력하면 "I ma yppah yadot" 이 출력됩니다.

풀이전략

  1. 주어진 문장을 Charactor형 공백을 포함한 배열로 변환합니다.
  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
41
42
43
44
45
46
47
48
49
package BackJoon;
 
import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;
 
/**
 * https://www.acmicpc.net/problem/9093
 * @author troh
 *
 */
public class _9093_단어뒤집기 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        sc.nextLine();
        
        String[] inputs = new String[t];
        for(int i=0; i<t; i++) {
            inputs[i] = sc.nextLine();
        }
        
        for(int i=0; i<inputs.length; i++) {
            String s = getSolution(inputs[i]);
            System.out.println(s);
        }
    }
    
    private static String getSolution(String s) {
        s += '\n';
        Stack<Character> stack = new Stack<>(); 
        StringBuffer bf = new StringBuffer();
        for(int i=0; i<s.length(); i++) {
            if(s.charAt(i) == ' ' || s.charAt(i) == '\n') {
                while(!stack.isEmpty()) {
                    bf.append(stack.pop());
                }
                if(i != s.length()-1) {
                    bf.append(s.charAt(i));
                }
            } else {
                stack.push(s.charAt(i));
            }
        }
        return bf.toString();
    }
}
 
cs

배운점

문제에서 공백 또한 포함한 출력결과를 만들어야하기 때문에 입력받은 문자열에 '\n'을 임의로 추가해주고 문자열의 끝을 체크했습니다. 하지만 '\n'은 개행문자 이기때문에 출력결과에는 포함되지 않도록 만들었습니다.  씨언어에서는 문자열의 끝에 널문자가 포함되는 것으로 기억하는데 씨언어로 구현할 수 있다면 좀 더 편할 것 같네요..ㅎㅎ 


아무튼 스택의 성질은 무언가를 뒤집을 때 사용하면 좋을 것 같습니다. 






저작자표시

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

[백준 온라인저지]스택 수열 - 스택  (0) 2019.09.12
[백준 온라인저지]괄호 - 스택  (0) 2019.09.12
[백준 온라인저지]수 정렬하기 - 정렬  (0) 2019.09.07
[백준 온라인저지]영화감독숌 - 브루트포스(5)  (0) 2019.09.06
[백준 온라인저지]체스판 다시 칠하기 - 브루트포스(4)  (0) 2019.09.04

수 정렬하기

이번 포스팅 문제는 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

+ Recent posts

티스토리툴바