https://www.acmicpc.net/problem/14714 14714번: 홍삼 게임 (Easy) 첫 번째 줄에 “질서 있는 홍삼 게임”의 참가자의 수 N(2 ≤ N ≤ 500), 은하가 먼저 지목한 사람의 번호 A와 두 번째로 지목한 사람의 번호 B(1 ≤ A, B ≤ N, A ≠ B), 각 지목권의 지목 간격을 나타내 www.acmicpc.net BFS를 사용한 문제다. 일단 방문 체크를 할 수 있는 배열을 만들었다. 이름은 쉽게 map으로. 초기에 map은 (지목권 A, 지목권 B)를 체크했다. 예를 들어 3번째 지목에 2번 사람이 지목권 A를 가지고, 4번 사람이 지목권 B를 가진다면, map의 (2, 4)는 3이다. 이렇게 만든 이유는 어떠한 (A, B)의 경우가 나왔을 때, 그 이후에 ..
알고리즘
안녕하세요! SSAFYcial 고주희입니다. 다른 사람들은 알고리즘 공부를 어떻게 하고 있을까? 궁금해서 저희 실습코치 님 두 분, 그리고 컨설턴트 님께 여쭈어보았습니다!
유클리드 호제법 a, b의 최대공약수와 b, a%b의 최대공약수가 같다는 것을 사용하여 최대 공약수를 찾는다. public static int gcd(int a, int b){ if(a%b==0) return b; return gcd(b, a%b); } a%b가 0이 되는 경우, a가 b로 나누어떨어지는 것이므로, b가 최대공약수가 된다. 관련 문제로 백준의 가 있다. 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 증명 유클리드 호제법은 귀류법으로 증명할 수 있다. f(a, b)는 최대공약수를 찾는 함수이다. 1. a>=b일 때, a = bx + r 가 성립한다. 2. f(..
SWEA의 7965_ 퀴즈 문제 (number)%p 연산을 위해 power에 아규먼트 p를 주도록 하는 경우와 함수 안에서 p를 따로 정의한 후 사용하는 경우 연산 시간에 상당한 차이가 보인다. DP를 사용하지 않는 경우 이 경우에는 파라미터 p가 있고 없음의 차이가 비교적 작지만, 파라미터가 있는 쪽이 연산시간이 더 큰 걸 확인할 수 있다. 파라미터가 있는 경우 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Solution { public static void main(String[] args) throws Numbe..
