목록분류 전체보기 (38)

devmoon

[C++] 백준 8111 : 0과 1

1. 문제 출처 https://www.acmicpc.net/problem/8111 8111번: 0과 1 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 2. 문제 접근 $N$이 주어졌을 때, 100 자릿수 이하인 $N$의 배수를 구하는 데에는 시간도 매우 많이 걸리고, 해당 수를 담을 자료형도 long long으로 부족하기 때문에 string연산으로 해결을 해줘야 한다. 따라서 반대로, 1과 0으로 이루어진 수들을 작은 자리 수부터 생성을 하고, 그 수가 $N$의 배수인지 ($N$)으로 나눈 나머지가 0인지) 확인만 해주면 되었다. 1과 0으로 이루어진 100자리의 수 역시 매우 큰 수 이므..
알고리즘/Baekjoon Online Judge 2021. 10. 14. 10:54
[C++] 백준 11402 : 이항 계수 4 / 뤼카의 정리

1. 문제 출처 https://www.acmicpc.net/problem/11402 11402번: 이항 계수 4 첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수) www.acmicpc.net 2. 문제 접근 $10^{18}$ 이하의 자연수 $n$과 $n$ 이하의 음이 아닌 정수 $k$가 주어졌을 때, $_nC_k$의 값을 구하는 문제이다. $_nC_k$ 의 값이 매우 커질 수 있으므로, 2000 이하의 임의의 소수 $m$이 주어지고 $_nC_k$의 값을 $m$으로 나눈 나머지를 출력하면 된다. 이 문제를 해결하기 위해서는 뤼카의 정리에 대해서 알아야 한다. 뤼카의 정리는 $_nC_k..
알고리즘/Baekjoon Online Judge 2021. 10. 12. 16:12
[C++] CCW / 두 선분의 교차 판단

선분 교차 판단 알고리즘은 2차원 평면 위에서 두 선분이 주어졌을 때, 두 선분이 서로 교차하는지 교차하지 않는지 판단하는 알고리즘이다. 이 알고리즘을 학습하기 위해서 선행되어야 하는 기하 알고리즘이 있는데, 그 개념은 CCW이다. CCW (Counter Clock Wise)는 2차원 평면 위에 놓인 3개의 점에 대해서 어떤 방향성이 있는지 알려주며 이 방향성 정보를 사용해 선분이 서로 교차하는지 판단하게 된다. CCW 먼저 3개의 점으로 나타낼 수 있는 방향성의 종류에는 무엇이 있는지 알아봐야 한다. 3개의 점을 임의의 순서대로 이어서 나온 방향성은 아래와 같이 1) 시계 방향 2) 반시계 방향 3) 일직선 3종류가 있을 수 있다. 그러면 이제 3개의 각 점에 대한 좌표정보가 주어지면 그 방향성을 어떻..
알고리즘/Concept 2021. 10. 11. 22:49
Meet in the middle / 중간에서 만나기

1. 관련 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 2. Meet in the middle 최대 길이 40의 수열이 주어졌을 때, 이 수열의 원소들 중 몇 개를 중복되지 않게 선택하여 모두 더한 값이 S가 되도록 하는 경우의 수가 몇 개나 있는지 찾는 문제이다. 시간, 공간 복잡도를 생각하지 않고 간단하게 접근했을 때, 모든 원소들을 순회하면서 [포함 / 미포함]으로 둘 수 있기 때문에 최대 ..
알고리즘/Concept 2021. 10. 11. 14:58
[C++] Codeforces Round #747 (Div. 2)

1. 문제 출처 https://codeforces.com/contest/1594 Dashboard - Codeforces Round #747 (Div. 2) - Codeforces codeforces.com 2. 문제 A. Consecutive Sum Riddle / solved 정수 $n \; (1 \leq n \leq 10^{18})$이 주어졌을 때, $l$부터 $r$까지의 합이 $n$이 되는 $l$과 $r$을 출력하는 문제. $-k + k + (k + 1) = k + 1$ 인 점을 이용해서 문제를 해결할 수 있다. #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(..
알고리즘/CodeForces 2021. 10. 9. 12:27
[C++] 백준 17071 : 숨바꼭질 5

1. 문제 출처 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 2. 문제 접근 도착점이 고정되어 있는 일반적인 BFS문제와는 달리, 도착점도 동시에 이동하는 BFS문제 수빈이가 이동할 수 있는 경우는 다음 3가지밖에 없다. 현재 위치 x에서 1칸 좌측(x - 1)으로 이동 현재 위치 x에서 1칸 우측(x + 1)으로 이동 현재 위치 x에서 순간이동하여 2배 떨어진 위치(x * 2)로 이동 특정 위치 x에 ..
알고리즘/Baekjoon Online Judge 2021. 10. 8. 22:33
이전 Prev 1 2 3 4 5 Next 다음