Page 14 -

현 재 스 팬 의 길 이 는 변 수 (v ari a bl e ) k 로 나 타 낸 다( 변 수 는 의 사 코 드 에 서 일 부 데 이 터 를 참 조 하 는 이
름 이 다). 이 러 한 데 이 터 의 내 용, 정 확 히 말 해 변 수 의 값 (v al u e )이 알 고 리 즘 실 행 중 에 변 경 될 수 있

어 서 변 수 라 한 다. k 의 값 은 스 팬 을 계 산 하 기 시 작 할 때 3 행 처 럼 항 상 1 로 설 정 한 다. 또 한, 알 고 리 1
즘 에 서 는 지 시 자 변 수 (i n di c at or v ari a bl e )인 s p a n _ e n d 를 사 용 한 다. 이 변 수 는 T R U E 또 는 F A L S E 를 값 주
가
으 로 갖 는 데, 이 는 특 정 상 태 나 위 치 에 있 음( T R U E ) 또 는 특 정 상 태 에 있 지 않 음(F A L S E ) 을 나 타 낸 스
팬
다. 스 팬 의 끝 에 도 달 하 면 s p a n _ e n d 의 값 은 T R U E 가 된 다.
각 스 팬 계 산 을 시 작 할 때 s p a n _ e n d 는 4 행 처 럼 F A L S E 가 된 다. 스 팬 의 길 이 는 5 ~ 9 행 사 이 내 부 루

프 에 서 계 산 된 다. 5 행 은 스 팬 이 끝 나 지 않 는 한 시 간 을 거 슬 러 갈 것 을 지 시 한 다. 반 복 은 ‘ i - k
≥ 0 ’ 는 조 건 에 따 라 결 정 된 다. 이 때 i - k 는 스 팬 이 끝 났 는 지 확 인 하 고 자 거 슬 러 가 는 날 짜 의 인
덱 스 로, 0 은 첫 째 날 에 해 당 하 므 로 인 덱 스 는 0 이 될 수 없 다. 스 팬 의 끝 에 대 한 확 인 은 6 행 에 서 한
다. 스 팬 이 끝 나 지 않 았 으 면 7 행 에 서 k 를 증 가 시 키 고, 그 렇 지 않 으 면 9 행 에 서 스 팬 이 끝 나 고 5 행
으 로 다 시 돌 아 가 루 프 가 끝 난 다. 외 부 루 프 의 마 지 막 인 1 0 행 에 서 는 배 열 s p a n s 의 적 절 한 위 치 에

k 의 값 을 저 장 한 다. 루 프 를 빠 져 나 온 뒤 1 1 행 에 서 알 고 리 즘 의 결 과 인 배 열 s p a n s 를 반 환 한 다.

알 고 리 즘 을 시 작 할 때 i = 0 , k = 1 이 므 로 최 초 5 행 이 실 행 되 면 조 건 을 만 족 하 지 않 아 루 프 를 실
행 하 지 못 한 다. 이 것 은 스 팬 이 1 인 경 우 에 해 당 한 다.
앞 에 서 펜 과 종 이 를 언 급 했 듯 이, 알 고 리 즘 을 이 해 하 는 올 바 른 방 법 은 수 작 업 으 로 실 행 해 보 는 것

이 다. 언 제 든 지 알 고 리 즘 이 복 잡 해 보 이 거 나 완 전 히 이 해 했 는 지 확 신 할 수 없 으 면 몇 가 지 예 로
알 고 리 즘 이 수 행 하 는 작 업 을 적 어 본 다. 구 식 으 로 보 일 지 모 르 지 만, 시 간 이 많 이 절 약 될 것 이 다.
알 고 리 즘 1 -1 에 대 해 확 신 이 서 지 않 는 다 면 지 금 직 접 실 행 해 보 고 알 고 리 즘 이 명 확 해 지 면 이 지

점 으 로 다 시 돌 아 오 자.

1 . 2 실 행 시 간 과 복 잡 도 R E A L - W O R L D A L G O R I T H M S

알 고 리 즘 1 -1 은 주 가 스 팬 문 제 에 대 한 해 법 인 데, 이 보 다 더 빨 리 실 행 될 수 있 는 더 나 은 알 고 리

즘 이 있 을 수 도 있 다. 알 고 리 즘 에 서 속 도 는 알 고 리 즘 이 실 행 할 연 산 수 를 말 한 다. 컴 퓨 터 가 아 무
리 빨 라 지 고 연 산 을 더 빨 리 실 행 할 수 있 을 지 라 도 연 산 수 는 동 일 하 므 로 연 산 수 의 관 점 에 서 알
고 리 즘 성 능 을 평 가 하 는 것 이 합 리 적 이 다. 그 래 서 시 간 단 위 로 측 정 되 지 않 는 순 수 한 숫 자 이 긴 하

0 2 5

리 얼 월 드 알 고 리 즘( 본 문) 최 종.i n d d 2 5 2 0 1 9 - 0 8 - 1 2 오 후 4: 2 7: 0 2