알고리즘/Math5 징검다리 건너기 징검다리 건너기 2019 카카오 개발자 겨울 인턴쉽 https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 2. 풀이 2.1 풀이 방법 캐릭터들이 징검다리를 건널 때마다 징검다리의 숫자가 1씩 깎이고 징검다리의 숫자가 0이 되면 캐릭터는 그 징검다리를 뛰어넘을 수 있으며, 캐릭터는 k만큼 건너뛸 수 있다. 만약 숫자가 0인 징검다리가 연속해서 k만큼 이어져있으면 캐릭터는 징검다리를 뛰어 넘을 수 없으므로 징검다리를 건너갈 수 없다. 따라서 .. 2023. 3. 10. 골-드바흐의 추측 골드바흐의 추측 백준 6588번 문제 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 에라토스테네스의 체를 사용해서 테스트 케이스의 최대 값(= 100,000)까지 각 숫자가 소수인지 아닌지를 판별한다. 소수로 나누려는 숫자의 절반까지 탐색하면서 해당 숫자를 소수로 뺀 나머지가 소수인지 판별한다. 2.2 코드 2.2.1 makePrimeSet 주어진 size까지의 숫자들이 소수인지 .. 2022. 8. 11. 최대공약수 최대공약수 특정한 두 수가 주어졌을 때 두 수 의 최대공약수(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. 이전 1 2 다음
