Project31 [백준 알고리즘] 2749번(피보나치 수3) [백준 알고리즘] 피보나치 수열을 오늘 모두 풀어보기 위해 다음 문제를 보겠습니다.이 문제는 피보나치 수열에 N번째 피보나치 수를 1,000,000으로 나눈 값을 구하는 문제입니다.그냥 단순하게 생각하고 N번째 피보나치 수에 1,000,000으로 나누니 출력이 안나오더라구요역시나 이렇게 쉬운 문제가 아니였습니다. 그래서 이리저리 해봤지만 안되서 구글링해봤습니다.구글링해보니 한 가지 더 알아야 할 것이 있더라구요그래서 거기에 대해 먼저 설명을 좀 하겠습니다. 일단, 피사노 주기(Pisano Period)를 기억하셔야 합니다.피사노 주기는 피보나치 수를 K로 나눴을 때 그 나머지가 항상 주기를 가진다는 말입니다.예를 보시겠습니다. 이렇게 일정한 주기를 가지게 됩니다.이 주기는 규칙을 가집니다 주기 길이를 P.. 2017. 8. 22. [백준 알고리즘] 2748번(피보나치 수2) [백준 알고리즘] 저번에 포스팅한 피보나치 수는 재귀함수를 이용하여 문제를 해결했다면이번에 알고리즘은 다 똑같은데 범위가 45 -> 90으로 변경되었습니다.그래서 그냥 똑같이 제출을 하니 시간초과가 떴습니다.범위 주의하시고 푸시면 되겠습니다. 그리고 재귀함수로 해도 범위가 커짐으로 호출해야하는 자기자신의 숫자도 늘어납니다.그렇기 때문에 시간이 너무 오래 걸릴 것이므로 재귀함수를 사용하지 않고 그냥 for문으로 알고리즘을 짰습니다. 간단하게 작성이 가능합니다. 1234567891011121314151617181920import java.util.Scanner; public class Beak2748 { public static void main(String[] args) { Scanner sc = new .. 2017. 8. 22. [백준 알고리즘] 2747번 (피보나치 수) [백준 알고리즘] 오늘 풀어본 문제는 피보나치 수열입니다. 피보나치 수열은 간단하게 0 / 1 / 1 / 2 / 3 / 5 / 8 / 13 .... 이렇게 진행이됩니다. 식으로 나타내면 F(n) = F(n-1) + F(n-2) // (n >=2) 이렇게 됩니다. 간단한 알고리즘입니다. 하지만 백준 알고리즘에서는 원하는게 재귀함수를 원하고 있습니다. 재귀 함수는 자기 자신을 재참조 하는 것입니다. 이 피보나치 수열이 재귀함수에서 가장 기본이 된다고 할 수 있습니다. 다음 문제를 보겠습니다. 간단한 문제입니다. 바로 코딩을 보겠습니다. 12345678910111213141516171819202122import java.util.Scanner; public class Beak2747 { public stati.. 2017. 8. 18. [기초 알고리즘] 넓이 우선 탐색(BFS)Ⅱ 넓이 우선 탐색(BFS) 이제 기본적인 내용은 다 배웠으니 그림으로 어떤 식으로 탐색이 진행 되는지 알아보도록 하겠습니다. 최대한 이해하기 쉽게 일단 그래프를 보시면 세 가지 색으로 나타나 있을 것이 보이실 겁니다.검정 / 회색 / 흰색 이렇게요검정은 탐색 완료 / 회색은 탐색 중 / 흰색은 아직 미 탐색 위에 보이는 그래프처럼 시작점을 A라고 한다면 A에서 같은 거리에 있는 B / D 를 탐색하기 시작합니다. 그리고 난 뒤, A는 탐색이 끝났으므로 검정으로 변환시켜 주고 B / D를 탐색하고 난 뒤 B는 더 이상 탐색할 수 있는 정점이 없으므로 검정으로 변환시켜 주고 D는 다시 탐색을 시작합니다.계속 이러한 과정을 거치면서 마지막 연결된 정점까지 탐색을 하는 것입니다. 이런 설명으로는 많이 부족할 것 .. 2017. 8. 16. [기초 알고리즘] 넓이 우선 탐색(BFS)Ⅰ 넓이 우선 탐색(BFS) 그래프의 탐색에는 넓이 우선 탐색과 깊이 우선 탐색 두 가지로 나뉩니다. 오늘은 넓이 우선 탐색을 먼저 공부를 해봤습니다. 넓이 우선 탐색은 Breadth First Search의 약자입니다. 시작점을 기준으로 동일한 거리에 있는 노드들을 먼저 탐색하는 탐색 기법입니다. 그렇다면 왜? 넓이 우선 탐색이라고 부를까요? 탐색이 시작되면 깊이 우선 탐색과 다르게 동일 선상에 있는 노드들을 탐색하게되고 또 그 노드들을 기준으로 동일한 거리에 있는 노드들을 탐색하게 됩니다. 그렇게 되면 탐색 범위가 점점 넓어 지는 듯한 모양을 띄게 됩니다. 그래서 넓이 우선 탐색이라고 부르게 되었다고 합니다. 그렇다면 이제 기본적인 것들을 알아보겠습니다. 거리(Distance)거리는 간단하게 말해서 정점.. 2017. 8. 16. 이전 1 2 3 4 5 6 7 다음
