본문 바로가기

Algorithm/Math

 (100)
(C++) - 백준(BOJ) 13458번 : 시험감독 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 단순 수학 문제였습니다. 📕 풀이방법 1. 총 감독관은 1명만 있어야하므로 무조건 추가되어야 합니다. 2. 부 감독관은 몇 명이 있는지 상관없으므로 (a[i] - b) / c만큼 있으면 됩니다. * (a[i] - b) % c가 나머지가 있으면(양수면) 부 감독관을 한 명 더 배치해야합니다. * 총, 부 감독관이 감시가능한 학생 수 가 각각 ..
(C++) - 백준(BOJ) 17827번 : 달팽이 리스트 https://www.acmicpc.net/problem/17827 17827번: 달팽이 리스트 첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 C1, C2, …, CN이 공백 www.acmicpc.net 순회하는 공식을 찾는 수학문제였습니다. 풀이방법 1. 1번노드를 제외한 2번부터 사이클의 첫 번째이므로 v의 값을 입력받은뒤 1을 빼줘야 합니다. 그 외 적절히 입력받습니다. 2. k < n인 경우에는 사이클을 순회하지 않으므로 그대로 k번째 값을 출력합니다. 이외의 경우에는 사이클을 적절히 돌게 됩니다. 사이클에 해당하지 않는 노드의..
(C++) - 백준(BOJ) 21739번 : 펭귄 네비게이터 https://www.acmicpc.net/problem/21739 21739번: 펭귄 네비게이터 펭귄은 현재 ($1$, $1$)에 있다. 펭귄은 집까지 가고 싶다. 펭귄의 집은 ($2$, $N$)이다. 하지만 누군가에 의해 얼음길이 다 깨져 집에 갈 수 없게 되었다. 현진이는 펭귄들을 위해 얼음길을 만들어줄 www.acmicpc.net 카탈란 수열의 값을 구하는 문제였습니다. 접근법이 너무 어려워 아래 해설을 참조하게 되었습니다. 응용하기 너무 어렵네요 ㅠㅠ https://www.acmicpc.net/board/view/68251 글 읽기 - 제1회 숙명여자대학교 교내 알고리즘 경진대회 (SMUPC) 종료 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net Code #include usi..
(C++) - 백준(BOJ) 1837번 : 암호제작 https://www.acmicpc.net/problem/1837 1837번: 암호제작 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 www.acmicpc.net 큰 수와 소수를 다루는 문제였습니다. 풀이방법 1. 2 ~ 100만까지의 소수를 prime배열 변수에 저장합니다. 2. 2 ~ k까지의 소수들 중 하나를 골라 p의 약수인지를 확인합니다. 입력받은 p의 경우에는 수의 범위를 초과하므로 string으로 입력받습니다. p의 첫번째 자리부터 하나씩 자리수를 붙여가며 확인합니다. 해당 수가 i에 나누어 떨어지는지 확인합니다. 3. 모든 자리수에 대해 자리..
(C++) - 백준(BOJ) 2981번 : 검문 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net gcd구한 후 약수를 구하는 문제였습니다. 풀이방법 1. gcd 구하기 : 나누어 나머지가 같은 m의 의미는 각 수의 차이들에 대해 최대공약수를 찾는 다면 이들의 약수가 모두 m이 된다는 뜻입니다. 2. 약수 구하기 : i * i > n; for(int i = 0; i > num[i]; for(int i = 1; i < n; i++) m = gcd(abs(num[i] - num[i-1]..
(C++) - 백준(BOJ) 14476번 : 최대공약수 하나 빼기 https://www.acmicpc.net/problem/14476 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 누적 GCD를 구하는 문제였습니다. 풀이방법 a는 n개의 수를 입력받고 저장하는 배열, lgcd를 왼쪽에서 시작해 오른쪽으로 가며 누적 gcd를 구한 값을 저장하는 배열, rgcd는 오른쪽에서 시작하는 배열이라고 정의합니다. a 8 12 24 36 48 lgcd 8 4 4 4 4 rgcd 4 12 12 12 48 다음 예제에서 i번째 값을 지울 때 이렇게 생각할 수 있습니다. lgcd[i-1] -> 삭제할 ..
(C++) - 백준(BOJ) 13251번 : 조약돌 꺼내기 https://www.acmicpc.net/problem/13251 13251번: 조약돌 꺼내기 첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다. www.acmicpc.net 확률 문제였습니다. 풀이방법 m개의 색으로 이뤄진 조약돌들 중 k만큼 랜덤으로 골랐을 때 모두 같은 색일 확률을 구해야합니다. 3개의 색으로 이워진 조약돌들이 각 색마다 3, 5, 7개 있다면 n은 3 + 5 + 7인 15입니다. k가 지금 뽑아야하는 색의 조약돌의 개수이하라면 뽑을 수 있습니다. k를 3이라고 가정해보면 확률을 구하는 공식은 다음과 같습니다. 정답 : 3/15 * 2/14 * 1/14 + 5/15 * 4/14 *...* 1/11 + 7/15 * ... * ..
(C++) - 백준(BOJ) 11444번 : 피보나치 수 6 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 행렬 곱셈을 이용해 log n만에 피보나치를 구하는 문제였습니다. 풀이방법 ​F(n) = F(n-1) + F(n-2) (n > 2) 를 행렬로 나타내면 다음과 같습니다. {\begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix}} = {\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}} X {\begin{pmatrix} F(n-1) \\ F(n-2) \end{pmatrix}} 1. 행렬로 피보나치 수열을 연산하게 되면 l..

티스토리툴바