'Algo Rhythm🕺💃/BOJ' 카테고리의 글 목록 (2 Page)

Algo Rhythm🕺💃/BOJ

[Algo Rhythm🕺💃] BOJ 17425 - 약수의 합
Algo Rhythm🕺💃/BOJ 2021. 6. 24. 21:43

문제 분석 약수의 성질 중 하나는 두 자연수 $a, b$ 에 대하여 $a$ 가 $b$ 의 배수이면 $b$ 는 $a$ 의 약수(들) 중 하나라는 것이다. 그리고 이 문제는 자연수 $n(1 \le n \le 10^6)$ 을 입력할 때 $g(n)$ 을 출력할 것을 요구한다. 이때 $g(n)$ 은 아래와 같은 수식으로 정의할 수 있다. $g(n)= \begin{cases} g(n - 1) + f(n) & n \gt 1\\ 1 & n = 1 \end{cases}$ 앞서 말한 두 가지를 종합할 때 이 문제는 약수의 성질을 이용하여 모든 $n$ 에 대하여 $g(n)$ 을 구하여 저장한 다음 테스트케이스로 $n$ 에 속하는 자연수 $a$ 가 들어올 때마다 $g(a)$ 를 출력하는 문제로 이해할 수 있다. 문제 풀이 1. $g(n)$ 을 저장하..

[Algo Rhythm🕺💃] BOJ 17427 - 약수의 합 2
Algo Rhythm🕺💃/BOJ 2021. 6. 24. 01:42

문제 분석 입력으로 주어지는 자연수를 $n (1 \le n \le 10^6)$ 그리고 $n$ 보다 작거나 같은 자연수를 $i$ 라고 하자. 자연수 $a$ 가 자연수 $b$ 로 나누어 떨어진다면 즉, $a$ 가 $b$ 의 배수라면 $b$ 는 $a$ 의 약수이다. 따라서, 이 문제는 $i$ 에 속하는 한 자연수의 배수의 개수와 그 자연수를 곱한 값들을 더하여 $g(n) = \sum_{i=1}^n f(i)$ 을 구하는 문제로 이해할 수 있다. 문제 풀이 $i$ 를 1부터 $n$ 까지 반복하여 $i$ 의 배수의 개수와 $i$ 를 곱한 값들을 더한다. 이때 $i$ 의 배수는 $n/i$ 개이다. 그리고 $i > n/2$ 일 때 $n$ 보다 작은 자연수들 중 $i$ 의 배수는 $i$ 자기 자신뿐이다. 따라서 그 경우에는 $i$ 만 더한다. 복잡도 분석..

[Algo Rhythm🕺💃] BOJ 4375 - 1
Algo Rhythm🕺💃/BOJ 2021. 6. 23. 21:55

문제 분석 1로만 이루어진 한 정수를 $x$ , 2와 5로 나누어 떨어지지 않는 정수를 $n (1 \le n \le 10^5)$ 이라고 하자. 이 정수의 오른쪽 끝에 1을 붙이기 위해서는 정수의 자릿수를 한 자리 올린 후 1을 더하면 된다. 즉, $10 \times x + 1$ 을 하면 된다. 하지만 overflow가 발생할 수 있기 때문에 계속해서 오른쪽 끝에 1을 붙일 수 없다. 다행히도 문제에서 요구하는 것은 $x$ 자체가 아니라 $x \mod n == 0$ 을 만족할 때의 자릿수이다. 따라서, 중요한 것은 $x$ 가 아니라 $x \mod n$ 이라는 것을 알 수 있다. 그래서 정수의 오른쪽 끝에 1을 붙일 때 $x = 10 \times x + 1$ 이 아닌 $x = (10 \times x + 1) \mod n..

[Algo Rhythm🕺💃]BOJ 6588 - 골드바흐의 추측
Algo Rhythm🕺💃/BOJ 2021. 6. 23. 17:45

문제 분석 이 문제는 4보다 큰 어떤 짝수 $x (6 \le x \le 10^6)$ 가 두 홀수인 소수 $a, b (a \le b)$ 의 합으로 나타낼 수 있는지 판별하는 문제이다. 이때 주의할 점은 골드바흐의 추측은 $10^{18}$ 이하에서 참임이 확인되었기 때문에 두 홀수 소수의 합으로 나타내지 못 하는 경우는 생각하지 않아도 된다는 것이다. 문제 풀이 1. '소수 판별 알고리즘' 응용 주어진 $x$ 에 대하여 $a$ 의 가능한 최소값인 3부터 $x - a$ 인 $b$ 가 2보다 크지 않을 때까지 $a, b$ 모두 소수인지 판별한다. 만약 모두 소수라면 $x = a + b$ 를 출력한 뒤 반복문을 탈출하고 그렇지 않다면 $a$ 를 2씩 증가하고 위 과정을 반복한다. 이때 2씩 증가하는 이유는 짝수는 절대 소수가 ..

[Algo Rhythm🕺💃]BOJ 2309 - 일곱 난쟁이
Algo Rhythm🕺💃/BOJ 2021. 6. 22. 20:02

문제 분석 문제에서 주어지는 아홉 난쟁이들의 키의 합은 일곱 난쟁이들의 키의 합인 100보다 크다. 따라서 이 문제는 $i$ 번째 난쟁이와 $j$ 번째 난쟁이 $(1 \le i, j \le n)$ 의 합이 초과값과 일치하는 $(i, j)$ 쌍을 찾는 문제로 이해할 수 있다. 문제 풀이 아홉 난쟁이의 키를 배열에 저장한 뒤, 이를 오름차순으로 정렬한다. 왜냐하면 일곱 난쟁이의 키를 출력할 때 오름차순으로 출력해야 하기 때문이다. 다음으로 이중 반복문을 통해 $(i, j)$ 쌍을 찾는다. 만약 찾았다면 $i$ 번째 난쟁이와 $j$ 번째 난쟁이를 제외한 모든 난쟁이들의 키를 차례대로 출력한 뒤 프로그램을 종료한다. 복잡도 분석 난쟁이 $n$ 명의 키가 입력으로 주어질 때, 시간 복잡도와 공간 복잡도는 다음과 같다. 시간 복..

[Algo Rhythm🕺💃]BOJ 14888 - 연산자 끼워넣기
Algo Rhythm🕺💃/BOJ 2021. 6. 22. 16:24

문제 분석 $N (2 \le N \le 11)$ 개의 수로 이루어진 수열 $A_1, A_2, A_3, ..., A_n$ 의 순서는 바꿀 수 없지만 숫자 사이 들어가는 연산자들의 순서는 바꿀 수 있다. 따라서 이 문제는 연산자들의 순서에 대한 '모든 조합을 구한 뒤' 계산한 결과들 중 최대값과 최소값을 구하는 문제로 이해할 수 있다. 문제 풀이 1. 최적화 🙅‍♂️ 연산자들의 순서에 대한 모든 조합을 구하기 위해 backtracking을 사용했다. 이때 방문해야 하는 vertex들은 연산자들인데 연산자들의 종류를 구분하기 위해 enum을 정의했다. 또한 연산자들의 개수는 입력에 따라 가변적이기 때문에 정의한 enum을 저장하는 vector를 정의했다. backtracking에 사용한 점화식은 아래와 같다. 이..

[Algo Rhythm🕺💃]BOJ 20170 - Commemorative Dice
Algo Rhythm🕺💃/BOJ 2021. 6. 21. 03:26

문제 분석 주사위 게임을 하는 첫번째, 두번째 플레이어를 각각 A, B라고 하고 A와 B의 주사위 중 임의의 한 면에 적힌 숫자를 각각 $\alpha, \beta$ 라고 하자. 이때 주사위는 6면이기 때문에 A와 B가 주사위를 던져서 나올 수 있는 경우의 수는 $6 \times 6 = 36$ 이다. 그리고 A가 B를 이기는 경우의 수인 $N_{win}$ 은 $\alpha \gt \beta$ 를 만족하는 모든 $\alpha$ 의 수와 같다. 따라서, A가 B를 이길 확률은 $N_{win} \over 36$ 이다. 이때, 문제에서 요구하는 것은 '더이상 나눌 수 없는' 분수 형태로 출력하는 것이기 때문에 분자와 분모를 최대 공약수로 나눠서 출력해야 한다. 문제 풀이 A와 B의 주사위 정보를 각각 배열에 저장한 뒤, $..

[Algo Rhythm🕺💃]BOJ 14889 - 스타트와 링크
Algo Rhythm🕺💃/BOJ 2021. 6. 18. 23:44

문제 분석 스타트팀을 $T_{start}$ , 링크팀을 $T_{link}$ 그리고 두 팀의 능력치를 각각 $S_{start}, S_{link}$ 라고 하자. 이때 각 팀에 속하는 사람들의 수는 두 팀 모두 축구를 하는 $N\ (4 \le N \le 20)$ 명의 절반인 $N / 2$ 명이다. 문제에서 요구하는 $min(|S_{start} - S_{link}|)$ 를 구하기 위한 가장 직관적인 방법은 $(T_{start}, T_{link})$ 의 모든 조합을 구한 뒤 각 조합의 $|S_{start} - S_{link}|$ 을 구하고 그 중 최소값을 찾는 것이다. 모든 조합을 구해야 하는 문제들은 주로 'backtracking'을 사용한다. 이 문제도 마찬가지로 backtracking을 사용하여 해결했다. 문제 풀이 ..

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`