Algorithm
2013.04.23 17:51
러시아 페인트공 알고리즘에 대해..
조회 수 22895 댓글 0
도로 차선 페인트 작업을 하는 러시아 페인트공이 있었습니다.
작업 첫날 페인트 공은 페인트 통을 들고 나가서 300야드를 칠했습니다.
깜짝 놀란 책임자는 "정말 놀라운데! 정말 손놀림이 좋군." 이라며, 페인트공에게 1코펙을 주었습니다.
다음날 페인트공은 겨우 150야드만 칠했습니다.
그래도 책임자는 "음, 어제 만큼은 못하지만, 여전히 손놀림이 좋군." 이라며, 페인트공에게 1코펙을 주었습니다.
그 다음날 페인트공은 30야드를 칠했습니다.
책임자는 "고작 30야드라니! 용납할 수 없네! 첫날에는 어떻게 오늘보다 10배를 넘게 칠한건가?
도대체 뭐가 문제야?" 라고 윽박질렀습니다.
풀이 죽은 페인트공은 이렇게 말했습니다.
"저도 어쩔 수 없었습니다. 매일 페인트 통에서 점점 멀어지니까요."
아래 코드는 러시아 페인트공 알고리즘이 무엇인지 그리고 얼마나 멍청한 형태인지 알수 있다.
수 만개에 해당하는 문자열을 위의 함수를 사용하여 덧 붙일 경우 처음 부터 계속 NULL 값을 찾아야 하므로 성능이 무척 떨어 지게 될 것이다. 따라서 위와 같은 알고리즘을 러시아 페인트 공 알고리즘 이라고 할수 있다.
위의 코드는 아래와 같이 수정가능 하다. 즉, NULL 포인터의 위치를 리턴해 주는 것이다.
간단한 변경만으로도 좋은 성능을 개선 할 수 있다.
- 조엘 온 소프트웨어(Spolsky, Joel) 발췌
작업 첫날 페인트 공은 페인트 통을 들고 나가서 300야드를 칠했습니다.
깜짝 놀란 책임자는 "정말 놀라운데! 정말 손놀림이 좋군." 이라며, 페인트공에게 1코펙을 주었습니다.
다음날 페인트공은 겨우 150야드만 칠했습니다.
그래도 책임자는 "음, 어제 만큼은 못하지만, 여전히 손놀림이 좋군." 이라며, 페인트공에게 1코펙을 주었습니다.
그 다음날 페인트공은 30야드를 칠했습니다.
책임자는 "고작 30야드라니! 용납할 수 없네! 첫날에는 어떻게 오늘보다 10배를 넘게 칠한건가?
도대체 뭐가 문제야?" 라고 윽박질렀습니다.
풀이 죽은 페인트공은 이렇게 말했습니다.
"저도 어쩔 수 없었습니다. 매일 페인트 통에서 점점 멀어지니까요."
아래 코드는 러시아 페인트공 알고리즘이 무엇인지 그리고 얼마나 멍청한 형태인지 알수 있다.
void strcat(char *dest, char *src) { while(*dest) dest++; while(*dest++ = *src++); }
수 만개에 해당하는 문자열을 위의 함수를 사용하여 덧 붙일 경우 처음 부터 계속 NULL 값을 찾아야 하므로 성능이 무척 떨어 지게 될 것이다. 따라서 위와 같은 알고리즘을 러시아 페인트 공 알고리즘 이라고 할수 있다.
위의 코드는 아래와 같이 수정가능 하다. 즉, NULL 포인터의 위치를 리턴해 주는 것이다.
char *strcat(char *dest, char *src) { while(*dest) dest++; while(*dest++ = *src++); return --dest; }
간단한 변경만으로도 좋은 성능을 개선 할 수 있다.
- 조엘 온 소프트웨어(Spolsky, Joel) 발췌
번호 | 분류 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|---|
729 | PPT | [doc] 정보보호이론 강의자료 (중앙대꺼..) 2 | hooni | 2013.04.23 | 22811 |
728 | PPT | [doc] 정보보호학술대회 논문지 ㅋㅋ | hooni | 2013.04.23 | 12178 |
727 | System/OS | [doc] 코코아 프로그래밍 for MACOS 관련 내 분량.. | hooni | 2013.04.23 | 20839 |
726 | Develop | [doc] 테크니컬 레포트 (BHO 취약점을 이용한 공격) 2 | hooni | 2013.04.23 | 27077 |
725 | System/OS | [doc] 피쳐셀렉션(feature selection using..) 발표 자료 | hooni | 2013.04.23 | 12546 |
724 | System/OS | [dos] 노트북 백업 스크립트 xcopy 명령 예제 | hooni | 2003.04.23 | 40805 |
723 | Etc | [english] 영어공부 혼자 하기, 인터넷으로 영어공부하기 추천사이트 20선 | hooni | 2013.11.25 | 9408 |
722 | Etc | [eng] 숙제 ㅋㅋㅋ | hooni | 2015.10.14 | 1 |
721 | Develop | [erp] SAP 모듈 요약 | hooni | 2013.04.23 | 15284 |
720 | Etc | [flash] 맘에 드는 파이차트 | hooni | 2013.04.23 | 12590 |
719 | Etc | [flash] 자동차 엔진의 원리 (4행정 사이클 그림) | hooni | 2013.04.23 | 21224 |
718 | Etc | [flash] 페이지 이동 (액션스크립트) | hooni | 2013.04.23 | 16263 |