알고리즘3 알고리즘 | DFS | Java 백준[Silver II] 유기농 배추 - 1012 [Silver II] 유기농 배추 - 1012문제 링크성능 요약메모리: 13552 KB, 시간: 96 ms분류그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색제출 일자2024년 9월 28일 00:27:07문제 설명차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 .. 2024. 9. 28. 알고리즘 | 기하학 | 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 다음
