본문 바로가기

알고리즘

(8)
[수학] 유클리드 호제법이란?(gcd, lcm) 유클리드 호제법 알고리즘 문제에서 두 수의 최대 공약수(gcd)를 찾는데 활용되는 알고리즘 이론이다. 어려운 내용도 아니고 구현도 간단하지만, 그만큼 최대공약수 문제의 기본이 되는 이론이니 익혀두는 것을 추천한다! 원리 두 수 a,b가 있을 때, a를 b로 나눈 나머지를 r이라고 할 때(a%b = r (a>b) ), a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 따라서, 이 성질에 따라 a를 b로 나눈 나머지 r을 구한 뒤, b를 r로 나눈 r'를 구하고 r%r' == 0 이 된다면 r'이 a와 b의 최대 공약수가 된다. (위 같은 식이 성립하는 이유는 나머지 연산(%)이 분배법칙이 성립하기 때문인데, 나머지 연산의 분배법칙 또한 수학 카테고리의 문제의 기본이 되는 경우가 많으니 찾아보길 권장..
[JAVA] SWEA D4 1868번: 파핑파핑 지뢰찾기(BFS) ※문제 출처 https://swexpertacademy.com/main/talk/solvingClub/problemView.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ※BFS 넓이 우선 탐색(Breadth First Search) . 특정 노드(칸)를 기준으로 같은 깊이의 노드(칸)으로 탐색 범위를 넓혀가는 방법. Queue 자료형을 활용해서 구현하며 주로 경로 탐색 등에서 사용된다. [문제] ‘파핑 파핑 지뢰 찾기’라는 유명한 게임이 있다. 이 게임은 RXC 크기의 표를 이용하는 게임인데, 표의 각 칸에는 지뢰가 있을 수도 있고 없을 수도 있다. 표의 각 칸을 클릭했을 때, 그 칸이 지뢰가 있는 칸..
[Python] 백준 1978번: 소수 찾기(파이썬,수학,정수론) 문제 출처: https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 풀이 방법 백준 17425 약수의 합(https://yoon-e.tistory.com/7) 문제와 매우 유사하다. 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 1 2 2 2 2 2 ..
[Python] 백준 17425번: 약수의 합 (파이썬,수학,정수론) 문제 출처: https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값..
[Python] 백준 17425번: 약수의 합 (파이썬,수학,정수론) 문제 출처: https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값..
[Python] 백준 17427번: 약수의 합2 (파이썬) 문제 출처: https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y..
[Python] 백준 4375번: 1 (나머지, 부르트포스, 파이썬) 문제 출처: https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net ※ BruteForce Algorithm(부르트포스) 문자 그대로 Brute Force(야성적인 힘), 완전탐색 알고리즘이라고 불린다. 발생할수 있는 모든 케이스들을 무식하게 대입해가며 답을 찾는 방식 이다. 단순하고 설계가 쉽다는 장점이 있지만, 그만큼 속도와 메모리 측면에서 비효율적이라는 단점을 가지고 있다. 문제 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을..
[Python] 백준 10430번: 나머지 (파이썬) 문제 출처: https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 문제 (A+B)%C는 ((A%C) + (B%C))%C 와 같을까? (A×B)%C는 ((A%C) × (B%C))%C 와 같을까? 세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) 출력 첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다. 풀이 방법 사실 풀이 방법이라 ..