덩치

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

티스토리툴바