반응형 [개발] 알고리즘11 Runner 기법 Runner 기법은 일반적으로 링크드 리스트(linked list)와 같은 자료구조에서 사용되는 두 포인터(tortoise and hare) 기법입니다. 이 기법은 다양한 문제를 효율적으로 해결하는 데 유용합니다. 대표적인 예로는 사이클 검출, 중간 지점 찾기, 두 리스트의 교차점 찾기 등이 있습니다. 가장 널리 알려진 것은 Floyd의 사이클 탐지 알고리즘입니다.1. Floyd's Cycle Detection AlgorithmFloyd의 알고리즘은 주로 링크드 리스트에서 사이클이 존재하는지 확인하는 데 사용됩니다. 이 알고리즘은 다음과 같이 작동합니다:두 포인터 설정: 두 개의 포인터를 설정합니다. 하나는 'slow' 포인터, 다른 하나는 'fast' 포인터입니다.포인터 이동:slow 포인터는 한 번에.. 2024. 7. 24. 하노이탑 하노이 탑(Tower of Hanoi)은 수학적 퍼즐 게임으로, 세 개의 기둥과 여러 개의 서로 다른 크기의 원반으로 구성되어 있습니다. 이 게임의 목적은 한 기둥에 순서대로 쌓여 있는 원반들을 다른 기둥으로 옮기는 것인데, 이때 다음과 같은 규칙을 따라야 합니다: 한 번에 하나의 원반만 이동 한 번에 한 개의 원반만 다른 기둥으로 옮길 수 있습니다. 큰 원반 위에 작은 원반을 놓을 수 없음 원반이 다른 원반 위에 놓일 때, 그 아래에 있는 원반은 무조건 더 커야 합니다. 하노이 탑 알고리즘은 재귀적인 접근 방식을 사용하여 이 문제를 해결합니다. 가장 간단한 형태에서는, n개의 원반을 가지고 있을 때, 다음과 같은 단계를 거칩니다: 상위 n-1개의 원반을 '보조 기둥'으로 이동합니다. 가장 큰 원반을 '.. 2023. 12. 19. 공간복잡도 프로그래밍에서 공간 복잡도(Space Complexity)는 알고리즘이 실행될 때 필요한 메모리 공간의 양을 나타내는 척도입니다. 이는 프로그램이 실행되면서 필요한 총 저장 공간을 의미하며, 일반적으로 입력 크기에 대한 함수로 표현됩니다. 공간 복잡도를 이해하기 위해 몇 가지 주요 개념을 살펴보겠습니다: 고정 공간(Fixed Space) 이는 알고리즘의 입력 크기나 문제의 크기와 무관하게 고정된 양의 공간을 차지합니다. 예를 들어, 데이터 타입, 변수, 상수 등이 여기에 해당합니다. 가변 공간(Variable Space) 이는 문제의 크기나 입력의 크기에 따라 변하는 메모리 공간입니다. 예를 들어, 동적 할당, 재귀 스택 공간, 배열의 크기 등이 여기에 포함됩니다. 공간 복잡도는 다음과 같이 계산됩니다:.. 2023. 12. 13. 시간복잡도 시간 복잡도(Time Complexity)는 프로그래밍에서 알고리즘의 효율성을 측정하는 방법 중 하나입니다. 구체적으로, 시간 복잡도는 어떤 알고리즘이 문제를 해결하는 데 얼마나 많은 시간이 소요되는지를 나타내는 지표입니다. 이는 일반적으로 알고리즘에 입력되는 데이터의 크기에 따라 어떻게 변화하는지를 나타냅니다. 시간 복잡도를 이해하기 위해서는 다음의 개념들을 알아야 합니다: 빅 오 표기법 (Big O Notation) 가장 널리 사용되는 시간 복잡도 표현 방법으로, 최악의 경우를 나타냅니다. 예를 들어, O(n)은 알고리즘이 입력 데이터의 크기(n)에 비례하여 실행 시간이 증가한다는 것을 의미합니다. 상수 시간 (Constant Time) - O(1) 입력 데이터의 크기와 상관없이 알고리즘의 실행 시간.. 2023. 12. 13. 이전 1 2 3 다음 반응형
