알고리즘39 최대공약수 최대공약수 특정한 두 수가 주어졌을 때 두 수 의 최대공약수(GCD)를 구하는 코드를 작성한다. 1. 풀이 1.1 풀이 방법 두 수 M과 N의 최대 공약수를 gcd(M, N)이라고 할 때, 다음과 같은 식이 성립한다. (M > N) gcd(M, N) = gcd(N, M % N) (증명은.. 위키에 있다..!) 따라서 위의 식을 M % N = 0이 될 때까지 반복해서 적용한다. M % N = 0이 성립한다는 것은 M이 N의 배수가 된다는 뜻이니까 gcd(M, N) = N이 된다. 1.2 코드 1.2.1 gcd [gcd] private int gcd(int M, int N) { //최대공약수를 구하는 메서드 if (M < N) { int temp = M; M = N; N = temp; } while (M %.. 2022. 8. 9. 조합 구현 조합 구현 특정 자료의 집합이 주어질 때, 해당 집합에서 N개를 뽑는 경우를 모두 구하는 코드를 구현한다. 순서는 고려하지 않는다(조합) 예를 들어 {1, 2, 3}과 {1, 3, 2}는 같은 경우로 판단한다. 1. 풀이 1.1 풀이 방법 초기에 주어진 집합을 initArray라고 했을 때, initArray의 원소들을 재귀적으로 탐색하면 N개를 선택한다. 다만 순서를 고려하지 않기 때문에 이전에 탐색한 원소는 탐색하지 않는다. [순열의 탐색] 위 그림에서 initArray = {1, 2, 3, 4} 라고 하자. 위 그림은 initArray에서 3개를 선택하는 경우를 찾을 때 탐색되는 방법을 나타낸 것이다. 1을 선택했을 때 순서대로 각 원소를 재귀적으로 탐색하면 위 그림과 같이 1 -> 2 -> 3 순.. 2022. 8. 8. 순열 구현 순열 구현 특정 자료의 집합이 주어질 때, 해당 집합의 자료를 순서를 고려해서 N개 선택하는 경우의 수를 구한다. 예를들어 {1, 2, 3}과 {1, 3, 2}는 다른 경우이다. 1. 풀이 1.1 풀이 방법 초기에 주어진 자료집합을 initArray라고 하자. initArray의 각 원소를 하나의 노드로 볼 때, 노드들을 처음부터 끝까지 재귀적으로 N번 탐색하면서 선택하면 모든 경우의 수를 구할 수 있다. 단, 각 노드는 해당 노드까지 선택된 자료의 정보를 갖고 있어야한다. [중복 선택 불가 예시] 예를 들어 1, 2, 3중 3개를 고르는 경우를 찾을 때 1과 2를 선택한 상황이라고 하자. 그러면 중복이 허용되지 않기 때문에 그다음에 선택될 숫자는 1과 2가 될 수 없다. 따라서 각 노드는 다음 노드로 .. 2022. 8. 5. 이-모티콘 이-모티콘 백준 14226번 문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 주어진 조건에서 1초간 할 수 있는 일은 다음과 같이 3가지가 있다. ● 화면의 이모티콘을 복사해서 클립보드에 붙여 넣기 ● 클립보드에 있는 이모티콘 화면에 붙이기 ● 화면에 있는 이모티콘 1개 삭제하기 [노드와 분기] screen은 화면에 나타나는 이모티콘의 개수, clip은 클립보드에 저장된 이모티콘의 개수, time은 해.. 2022. 8. 5. 이전 1 ··· 3 4 5 6 7 8 9 10 다음
