알고리즘2 알고리즘 | Java 백준[Silver II] 참외밭 - 2477 [Silver II] 참외밭 - 2477문제 링크성능 요약메모리: 11568 KB, 시간: 64 ms분류기하학, 구현, 수학제출 일자2024년 8월 24일 18:30:20문제 설명시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다.. 2024. 8. 24. 알고리즘 | 점화식과 알고리즘 복잡도 분석 점화식 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것 자기호출을 사용하는 함수의 복잡도를 구하는데 유용하게 쓰인다. 병합 정렬의 수행 시간 수행시간의점화식 T(n) = 2T(n/2) + 오버헤드 크기가 n인 병합 정렬 시간은 크기가 n/2인 병합 정렬을 두 번하는 시간과 나머지 오버헤드(두 개 정렬 결과를 병합하는 시간)를 더한 시간이다. 점화식의 점근적 분석 방법 1. 반복 대치 더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법 2. 추정후 증명 결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법 3. 마스터 정리 형식에 맞는 점화식의 복잡도를 바로 알 수 있다. 반복 대치 예시 1: 팩토리얼 C부분이 오버헤드라고 할 수 있다. 예시 2 해당 크기 만큼(n) 오버헤드.. 2023. 9. 12. 이전 1 다음
