Tip:
Highlight text to annotate it
X
이 강의의 한국어자막은 www.snow.or.kr 자원활동가들에 의해 작성되었습니다. 이제 수업 시작하겠습니다. 핸드아웃 가져가지 않은 학생은 문 옆에 있으니 가져가세요.
제 이름은 찰스 라이저슨입니다.
이번 학기에 에릭 데메인과 함께
알고리즘 입문 과목을 강의할 겁니다.
덧붙여 이건 데이비드 수에 의해
싱가포르에서 진행되고 있는 싱가포르 MIT 과정, SMA입니다.
그리고 모든 수업은 비디오 테이프로 녹화되고
웹을 통해 강의 보기를 선택한 MIT 학생들뿐만 아니라
웹을 통해 싱가폴 학생들이 볼 수 있도록 만들어 질 것입니다.
만약에 비디오에 녹화되지 않길 원하는 학생은
뒷줄에 앉아주시길 바랍니다. 아셨나요?
그렇지 않으면 비디오 테잎에 녹화 될 것입니다.
비디오 녹화 정책이 있는데 만기된 것 같군요.
만약 보고 싶으면 돌려가며 봐도 되고,
아니면 저한테 와도 됩니다.
제게 복사본이 하나 있습니다.
본격적으로 수업으로 들어가기 전에
간단하게 수업에 대한
정보를 살펴보도록 하겠습니다.
여러분이 보다시피 이번 학기에는 조교들이 아주 많습니다.
여기 핸드아웃을 보세요.
6명의 조교들을 포함해서 다른 학기 때보다 2명 더 많은 조교들이 있습니다.
그것은 특히 설명은 많지 않을 것이라는 것을 뜻하죠.
여기 웹 페이지가 있습니다.
모든 공지들이 이곳으로 올라오니 즐겨찾기 해두고
정기적으로 확인하기 바랍니다.
이메일은, 여러분께 우리 이메일 주소를 알려 드려도
조교나 교수에게 직접
이메일을 보내지는 마시기 바랍니다.
이것은 여러분이
좀 더 빠른 답변을 받기 위한 것입니다.
제가 이미 언급 했듯이,
이번 학기에 우리는 원격 교육을 하게 될 것이고,
그래서 인터넷으로 강의를 듣고 싶다면
여러분은 온라인으로 강의를 들을 수 있습니다.
볼 수 있는 기회를 가진 분들은 보는 것을
추천합니다. 그렇지만,
강의에 올 수 있는 분들은 아무래도 현장에 와서 강의를 듣는 것이 좋겠지요.
소통할 수 있고, 뭐라고 꼭 집어서 말할 수 없는 무언가가 있습니다.
사실 비디오 외에도 저는 싱가폴 학생들 또한 직접 들을 수 있도록 매주 모임을 가지고 있습니다.
필수요건으로는
이번 강의를 듣기 위해서 미리 알고 있어야 할 것은 컴퓨터 과학을 위한 수학,
6.042와 6.001입니다.
여러분이 이 과목을 잘 따라가기 위해서는 프로그래밍 경험뿐만 아니라
기본적으로 이산수학과 확률에 대한 지식이 필요합니다.
이 선수 과목들을 수강하지 않은 분들은
이 수업을 들어서는 안 됩니다.
선수과목을 한번 체크해보도록 하지요.
질문이 있다면 수업이 끝난 후에 이야기
하도록 합시다.
강의는 여기서 이루어지고, SMA 학생들은
비디오 테잎을 보고 매주 모임을 가질 것입니다.
학생들은 반드시 매주 있는 한 시간짜리 설명 시간에 출석 해야 합니다.
설명시간에 새로운 자료가 주어질 것이고,
이 수업과는 다르게 온라인으로는 제공되지 않을 것입니다.
또한 이 수업과 다르게
일반적으로 설명에 대해 주는 강의노트도 없을 것입니다.
그러나 그 시간에
직접적으로 시험에 관련된 자료가 나갈 것입니다. 그리고
매 학기 그랬던 것처럼 여러분이 배우고서 금세 까먹는 것을 잘 알기 때문에 여러분께 설명시간에 이 부분을 언제 다뤘었지? 라고 물어서
중요한 부분을 상기시켜 줄 것입니다.
그래서 설명시간은 의무적으로 반드시 출석해야 합니다.
그리고 특히 설명시간 강사님도 여러분에게 성적을 주는 사람들 중 하나라고 말씀 드리고 싶습니다.
우리는 성적 미팅을 가질 것이고,
설명시간은 여러분의 성적에 아주 큰 영향을 미칠 것입니다.
핸드아웃들.
핸드아웃은 강좌 웹 페이지에서 볼 수 있고,
이번에 첫 번째 핸드아웃만 나눠드리고,
일반적으로 앞으로 나눠드릴 핸드아웃은 수업에 들고 들어오지는 않을 것입니다.
교재는 이 책입니다. Introduction to Algorithms.
MIT 학생들은 MIT Coop을 포함해서 지역의 어느 서점에서도 이 책을 살 수 있습니다.
또한 교재를 파는 새로운 온라인 서비스가 있고,
MIT Press 서점에서 사면
할인도 받을 수 있습니다.
MIT Press 서점에서 할인 받을 수 있는 쿠폰이 MIT 전화번호부에
한 개 있습니다. 이 책을 구입하는데
할인을 사용할 수 있죠.
강의 웹사이트. 이것이 강의 웹사이트입니다.
이것은 Stellar 사이트와 연결되는데, Stellar 사이트에
모든 것이 보관될 것입니다.
그리고 SMA 학생들은 자신의 웹 사이트를 가지고 있지요.
몇몇 학생들은 이 강의가 매우 어려울 것이라는 것을 알고 있습니다.
그래서 추가적인 도움이 필요할 것이고
매주 오피스 시간을 강의 웹사이트에 게재할 것입니다.
그리고 이번 학기에 실습으로 과제를 제공할 것입니다.
실습과제를 하기 위해 가는 장소와 시간이 있고,
일반적으로 2명의 조교가 있을 것입니다.
그리고 과제를 하면서
필요하면 조교들로부터
도움을 얻을 수 있을 것입니다.
스케줄을 정해서
강좌 일정에 써놓을 것입니다.
보통은 일요일 오후 2시부터 4시까지거나
아니면 저녁이 될 것입니다.
제 생각에는 첫 번째 실습은 저녁인 것 같습니다.
그렇죠? 실습이 가까이 왔습니다.
가장 좋은 방법은 실습과제를
미리 하려고 노력하는 것입니다.
그러나 또, 도움이 필요하거나 사람들과 여러분의 솔루션에 대해 이야기 하고 싶다면
왜냐하면, 문제를 함께 의논할수록
여러분은 공동 작업 속에서 문제를 풀어낼 수 있기 때문입니다.
게다가 몇 개의
peer assistance 프로그램들도 있습니다.
또한 소수 교육 오피스도 지원프로그램을 가지고 있습니다.
그리고 보통은 매우 빨리 예약이 마감됩니다.
만약 여기에 흥미가 있으면, .
그곳에 가서 약속을 잡는 것이 좋을 것입니다
실습과제, 저는 많은 사람들이 시도하고 시험해봤으면 좋겠네요.
우리는 이런 것을 해본 적이 없습니다.
다른 강의들은 잘 모르겠는데,
MIT에서 이것을 했었던 강의가 있나요?
6.011이 했군요. 좋습니다.
좋아요. 그 수업에서 성공적이었나요?
안 갔다고요.
좋습니다.
자 봅시다. 이것이 안 되면,
일반적인 오피스 아워를 이용하게 될 테지만,
몇몇 학생들에게 이것은 매우 좋은 기회일 것입니다.
만약 이 강의에 등록하고 싶다면 여러분은 반드시 웹 페이지에 등록해야 합니다.
이것은 요구조건이고 오늘 반드시 하셔야 합니다.
수업에 없으면 이 과목을 패스하기
어렵다는 것을 알게 될 것입니다.
드롭을 결정했다면 메일을 더 이상 보내지 않도록
여러분의 조교에게 알리고, 수업을 듣는 분들은
오늘 저녁 7시 전에 등록을 해야 합니다.
그러면 내일 정오가 되기 전에 여러분에게 설명시간 과제를 이메일로 보내게 될 것입니다.
그리고 만약 여러분이 목요일 정오까지도
이 이메일을 받지 못했다면 일반적으로는 그 강좌의
스태프에게 이메일을 보내주시기 바랍니다.
저에게 개인적으로 보내지는 마시고, 스태프에게 여러분이 설명시간 과제를 받지 못했다고 말씀해주시기 바랍니다.
목요일 정오까지도 받지 못하면
아마 밤이나 적어도 다음날 오전까지는
보내게 될 것입니다.
좋습니다. SMA 학생들은 이것에 대해 걱정할 필요가 없습니다.
문제 세트들.
이번 학기에 할당된 과제는 9개가 있습니다.
문제 세트들에 대해 몇 가지 것들이 있습니다.
일반적으로 집에서 하는 과제는 받아주지 않을 것입니다.
만약 사정이 있다면 설명시간
강사님과 사전에 협의를 해야 할 것입니다.
사실 거의 모든 행정적인 일에 대해서는,
저한테 와서 늦게 내도 되냐고 묻지 마시고,
여러분의 설명시간 강사님과 상의하도록 하세요.
다른 것들도 읽어보시고,
그렇지만, 연습문제에 대해서는 언급해야겠군요.
연습문제를 풀기는 해야 하지만,
제출할 필요는 없습니다.
저는 연습문제를 푸는 것을 매우 추천합니다.
이런 것들은 모두 자료에 대한 이해를 테스트 하게 될 것입니다.
그리고 퀴즈를 푸는데 도움이 될 것입니다.
종종 알고리즘을 설명해 보라는 질문을 받습니다.
그리고 여기 여러분이 알고리즘을 설명하기 위해서 사용할 것들의 작은 아웃라인이 있습니다.
성적은
어쨌든 제가 주게 되고
만약 과제를 빠뜨리게 되면 성적에 안 좋은 영향이 갈 것입니다.
성적은 알 수 없는 것이에요.
알았죠?
그렇지만 어떤 문제도 빠뜨리지 않게 되면 성적에 영향은 없을 것입니다.
만약 한 문제를 빠뜨렸다면,
성적에 대해 조정할 수 도 있습니다.
그렇지만, 이것들이 문제 세트는 아닙니다.
이것이 문제들인거죠. 그렇죠?
성적은 내려가게 될 것이고,
9이상을 하지 않으면, 일반적으로 3,4 문제세트들을 하지 않으면,
이 강의를 패스할 수 없습니다.
매년 해가 끝날 때 찾아와서
저는 어떤 문제도 없었고, 시험도 잘 봤는데,
패스 시켜주시면 안되나요? 라고 묻는 학생들이 있습니다.
저는 안 됩니다. 라고 말합니다. 매우 간단한 대답이지요. 왜냐하면 제가 계속 말해왔기 때문입니다.
문제 세트들은 이 강의에 필수 요소입니다.
공동연구 방침에 대해 보도록 하지요. 이것은 매우 중요합니다.
모두 집중하도록 하세요. 만약 자고 있으면 일어나세요.
이게 누군가 깨울 것 같죠?
과제의 목적에 대해서 말해보죠.
Demaine 교수와 저의 철학은 집에서 하는 과제의 목적은
여러분의 이해를 돕기 위한 것이라고 생각합니다.
그리고 배우는 것을 돕는 한 가지 방법은
여러분이 막히지 않도록 하는 것이지요. 그리고 문제를 풀지
못하는 것이 없도록 하는 것입니다.
여러분은 함께 연구하게 되는 것이 좋습니다.
그러나 여기에는 공동연구에 대한 상식이 있는데,
만약 여러분이 가서 그저
다른 사람으로부터 정보를 얻는 정도까지만 하게 된다면
여러분은 잘 배울 수 없고,
시험을 잘 볼 수도 없을 것입니다.
제 경험에 비추어 보면, 일반적으로 공동연구를 해서
공부한 학생들이 혼자 공부한 학생들보다 잘했습니다.
이것을 하는 것이 의무이고, 만약 여러분이 스터디 그룹에서 공부를 하러 간다면,
여러분의 스터디 그룹 모임을 잘 준비하도록 하세요.
구체적으로 스터디 그룹에 가기 전에 각각의 문제에 대해서 여러분은
1시간 반이나 45분 정도 걸릴 것입니다.
그러면 기대한 정도의 속도에 도달하고, 여러분의 아이디어를 시험해 볼 수 있을 것입니다.
그러면 해결책을 얻을 수도 있고, 어떤 문제는 잘 풀리지 않았을 수도 있습니다.
그러나 적어도 그것에 전념하도록 하세요.
30분이나 45분 후에, 문제가 해결되지 않아서
그저 앉아서 머리를 치고 있지 마세요.
이것은 여러분의 시간을 생산적으로 사용하는 것이 아니죠.
그리고 저는 여러분이 시간이 있는데도
그러고 있다는 것을 알고 있습니다. 그렇죠?
그렇게 보이지는 않을지 모르지만요.
그래서 문제가 안 풀린다고
머리를 때리고 있지 말고, 그럴 때 스터디 그룹을 이용하도록 하세요.
스터디 그룹이 도와줄 것입니다.
제가 언급한 것처럼, 실습과제가 있을 것이고,
어쩔 수 없이 그룹을 만들기 보다는
다른 학생들과 같이 연구하면서 공부할 기회가 있을 것입니다.
물론, 조교들도 그곳에 있을 것입니다.
만약 여러분 그룹이 문제를 풀지 못하면,
옆의 그룹에 가거나 강사님께 여쭤보면 됩니다.
이렇게 문제를 풀어 가면 됩니다.
이미 해놓은 메모들을 바탕으로 문제 세트들을 기록하고,
그러나 이것은 여러분이 혼자 하도록 해야 합니다.
문제 솔루션은 다른 학생들과 함께 작성하지 마세요. 스스로 정리하도록 합니다. 알겠죠?
그리고 여러분 문제 세트에 대해서
이것은 아카데믹한 부분이기 때문에
우리는 아카데믹한 정보에 대한 출처가 매우 중요합니다.
만약 여러분이 문제에 대해서 협동했다면,
협동한 사람들의 리스트를 작성해주십시오.
여러분의 성적에는 영향을 미치지 않습니다.
단지 알고자 하는 것입니다.
여러분이 교수님이나 조교에게 입으로
설명 못하는 문제 해결책을 제출하는 것은 방침의 위반입니다.
여러분이
제 레포트가 다른 사람의 것과 비슷합니다.
저는 베끼지 않았어요. 그러면 우리는
여러분에게 그 해결책에 대해 설명해 보라고 물을 겁니다. 만약 여러분이 못하면
이 방침에 따라서, 우리는 커닝이라고 간주할 것입니다.
이해 못한 것은 쓰지 못합니다.
여러분은 그것을 이해하고 쓸 수 있어야 합니다.
여러분이 작성한 것에 대해서 왜 그런지 이해하도록 하세요.
물론,
어떠한 협동도 시험에서는 허용되지 않습니다.
시험은 우리가 여러분을 평가하기 위함입니다.
그리고 저희는 다른 사람들을 평가하는 데에는 관심이 없지요. 우리는 여러분을 평가합니다.
그래서 시험에서는 어떠한 협동도 안 됩니다.
우리는 집에서 풀어서 제출하는 두 번째 퀴즈가 있을 겁니다.
스케줄을 확인하고 만약 문제가 있으면 미리 알려주시기 바랍니다.
공동연구에 대해서는
월요일, 11월 28일 강의시간에
더 자세하게 이야기하도록 하겠습니다.
일반적으로
여기서 강의가 의무적이지만, 9:30분이
조금 이른 것 같기는 합니다.
특히 월요일 또는 다른 요일에도요.
약간 일찍 일어 나야 하죠.
그렇지만
11월 28일 월요일에는 정각에 오지 않으면 시험을 잘 보지 못할 것입니다.
꼭 와야 하는 날이지요.
질문 있으신가요? 알겠죠? 정각에 꼭 와야 합니다.
인터넷 강의를 들어왔어도 말이죠.
만약 정 안 되겠다면,
가장 좋은 방법은 저희한테 오셔서 그것에 대해 이야기 하는 것입니다.
보통은 해결해드릴 수 있을 것입니다.
이것은 우리가 제 3자나
분명한 분석들에 의해서 누군가가 위반을 했다는 것을 알 때이고,
복잡해지겠죠.
그래서 여러분이 생각하기에 어떤 이유에 대해서
뭔가 잘못 한 것 같다 라고 생각하시면 저희한테 와서 이야기 하시면 됩니다.
사실 저희도 한때는 학생이었으니까요.
매우 오래되었지만요. 좋습니다. 질문 있습니까?
자, 이 수업에는 정말 좋은 자료가 있습니다.
정말 멋진 자료죠. 정말 재미있습니다.
그렇지만, 여러분은 공부를 매우 열심히 해야 할 거에요. 자, 내용에 대해서 한번 이야기 해보죠.
이것은 첫 번째 파트의 주제입니다.
이 강의의 첫 번째 파트는 분석에 초점을 맞추고 있지요.
두 번째 파트는 디자인에 초점을 맞추고 있습니다.
여러분이 디자인을 하기 전에 알고리즘을 분석하는
많은 기술들을 마스터 해야만 합니다.
그러면 여러분이 분석한 알고리즘을
효율적으로 디자인하는 위치에 도달하게 되는 거죠.
알고리즘 분석은
컴퓨터 프로그램 성능과
리소스 사용에 대한 이론적인 학문입니다. 그리고 특히 성능에 초점을 맞추죠.
우리는 컴퓨터를 어떻게 빠르게 만들지에 대해 공부합니다.
특히
컴퓨터 프로그램들이요. 우리는 또한 커뮤니케이션 같은
다른 리소스들에 대해서도 개발하고 이야기합니다.
예를 들면 메모리에 대해서 말입니다. 램 메모리일수도 있고 디스크 메모리일수도 있지요.
여기에는 우리가 관심을 기울여야 할 다른 리소스들이 있습니다.
그렇지만 우리는 주로 성능에 집중할 겁니다.
왜냐하면 이 강의가 성능에 관한 것이고,
저는 프로그래밍에서
성능보다 더 중요한 것이 뭐냐고 물으면서
시작하고 싶기 때문입니다.
만약 여러분이 엔지니어링 상황에서 코드를 쓰고,
소프트웨어를 작성하고 있다면 성능보다 더 중요한 것은 무엇일까요?
정확성.
좋습니다. 좋아요.
또 뭐가 있을까요? 간단함도 될 수 있겠고요.
좋습니다.
유지도 때론 성능보다 더 중요할 수 있지요.
비용. 어떤 유형의 비용이라고 생각하시나요?
아니, 제 말은 어떤 종류의 비용이 될 수 있을지에 대해 여쭤보는 것입니다.
우리는 소프트웨어에 대해 이야기하고 있지요. 그렇죠?
그래서 어떤 유형의 비용이 될 수 있을까요?
프로그래밍을 할 때 프로그래머 시간과 같은 몇몇 비용들이 있지요.
그래서 프로그래머의 시간이 또 다른 중요한 것이 될 수 있을 것입니다.
안정성.
소프트웨어의 단단함.
또 뭐가 있을까요?
생각해 보세요. 여기 많은 엔지니어분들이 있는데
엄청 많습니다.
HoFeatures 는 어떤가요?
이것도 더 중요할 수 있죠.
기능성(Funtionality), 모듈방식(Modularity).
이것은 여러분이 코드에 부분적으로 변화를 준 방식대로 디자인되어지죠.
그리고 기능성에 단순한 변화를 주기 위해서
다른 코드로 변화를 줄 필요가 없습니다.
엄청 중요한 것이 하나 있습니다. 90년대에 컴퓨터에
아주 큰 부분이었는데.
아주 큰 것입니다. 음. 보안.
좋습니다. 그건 쓰지도 않았네요.
보안 좋습니다.
그것은 사실 2000년대에 더 중요해지고 있죠.
보안은 종종 성능보다 더 중요합니다.
확장성. 중요하죠.
확장성이 어느 부분에서는 성능과 관계 있지만,
확장성은 중요하죠.
큰 돌파구는 무엇이었을까요?
왜 사람들이 윈도우보다 매킨토시를 사용했을까요?
사용하기 쉬움(User-friendliness). 와우.
만약 여러분이 90년대에 사용자 친화(user-friendliness)로 된
컴퓨터 원들의 숫자를 세어보면,
이것이 전혀 없다가 현대에 컴퓨터가 사용자 친화적으로 되면서
현대 컴퓨터의 아주 중요한 부분으로 자리 잡게 되었다는 것을 알 수 있을 겁니다.
그래서 모든 이러한 것들이 성능보다 더 중요한 것들이지요.
이런 것들이 성능에 대해 이 강의에서 배우게 될 것들입니다.
그러면 여러분은 왜 우리가 귀찮게 이런 많은 것들의
바닥에 자리 잡고 있는 알고리즘과 성능을 배워야 하죠? 라고 물을 것입니다.
항상 대부분 사람들은 차라리
성능보다 이런 것들을 배우고 싶다고 합니다.
나가서 사람들한테 물어보세요. 성능을 배우는 것이 나을까 아니면
사용자 친화(user-friendliness)를 배우는 것이 나을까?
항상 사람들은 성능보다 사용자 친화(user-friendliness)가 중요하다고 할 것입니다.
그러면 왜 우리는 이것을 공부 해야 하는가? 네 학생?
그것은 사용자 친화적이지 않습니다. 때때로 성능은
사용자 친화(user-friendliness)와 밀접한 연관이 있습니다.
매우 많이요. 어떠한 것도 앉아서 기다리는 것보다 더 좌절감을 느끼게 하는 것은 없을 것입니다.
그렇죠?
네. 좋은 이유입니다. 다른 이유도 있나요?
때때로 실시간 통제를 가지죠.
그래서 그것들이 적절하게 작동하지 않으면 사실 효과가 없습니다.
그렇죠?
이해하기 어려운데 음. 우리는 보통 사용자 친화(user-friendliness)를 수량화 하지 않습니다.
그래서 잘 모르겠네요. 그렇지만 무슨 말을 하는지는 이해합니다.
저 학생은 사용자 친화(user-friendliness)에서
기하급수적인 성능개선은 얻을 수 없음을 이야기 했습니다.
우리는 종종 성능에서 그 부분을
잘 이해 못하죠.
그런데 때때로 우리는 이해를 잘 못해요. 그렇지만, 좋습니다.
제가 중요하다고 생각하는 몇 가지 이유들이 있습니다.
우선 첫 번째는 성능은 종종 실현가능한지 실현 가능하지 않은지를 구분해줍니다.
우리는 이런 것들에 대해 들어왔지요.
예를 들어보면,
여기 실시간 요구가 있을 때,
그것이 충분히 빠르지 않다면 단순하게 정상적으로 동작하지 않을 것입니다.
또는 만약 너무나 많은 메모리를 사용하면, 또한 작동하지 않을 것입니다.
결과적으로
여러분이 발견한 것은 기업가 활동의 최첨단에 있는 알고리즘들입니다.
만약 여러분이 사람들이 10년 전에 하던
재실행 일에 대해 이야기하는 것이라면,
성능은 그 수준에서 그리 중요하지 않습니다.
그러나 만약 여러분이 어떠한 사람도 전에 해본 적이 없는 일에 대해 이야기 하는 것이라면,
그 이유들 중에 하나는 시간이 너무 많이 걸려서 일 것입니다.
크기를 조정할 수 없고 기타 등등이 될 수 있죠
그래서 성능이 실현가능한지 아닌지를
나누는 하나의 이유입니다.
또 다른 이유는 알고리즘이 여러분에게 프로그램의 움직임에 대해
이야기해주는 언어를 제공해주기 때문입니다.
그리고 결국 그것은 컴퓨터 과학 전반에 사용되는 언어가 됩니다.
이론적인 언어이고, 전문가들에 의해 쓰여 집니다.
왜냐하면 이것이 프로그램의 움직임을 깔끔하게 이해하는 방법이기 때문입니다.
그리고 성능에 대해 이해하는 좋은 방법이기 때문이죠.
그리고 이것이 이런 많은 것들의 가장 근본적인 부분에 있는 이유는
약간 성능이 돈과 같기 때문입니다. 통화 같아요.
여러분이 엄청 많은 돈이 있다면 무엇을 하는 것이 좋을까요?
음식을 가지는 것이 좋을까요? 물을 가지는 것이 좋을까요?
집을 가지는 것이 좋을까요? 어떤 것이든지요. 그리고 여러분은 기꺼이 백 달러짜리 계산서를 지불할 것입니다.
만약 여러분이 그러한 물품들에 대해 백 달러가 쓰여 있는 청구서를 받는다면 말이죠.
비록 물이 여러분이 살아가는데 훨씬 더 중요하다고 하더라도 말이죠.
음 비슷하게,
성능은 사용자 친화(user-friendliness)에 대해 지불하기 위해 사용되는 것입니다.
보안에 대해 지불하는 것이에요. 그리고 사람들이 이렇게 말하는 것을 들을 것입니다.
예를 들면, 제가 훨씬 더 기능이 뛰어난 컴퓨터를 원한다고 하죠.
그러면 사람들은 자바로 프로그램을 만들 것입니다.
C언어보다 훨씬 느린데 말이죠. 그리고 자바에서 프로그램 짜는데
성능 면에서 아마도 세 개정도의 요소를 가지기 때문이라고 말하죠.
그러나 자바는 그럴만한 가치가 있다는 것입니다.
왜냐하면 자바는 객체 지향적이라든지 많은 장점을 지녔기 때문입니다.
메커니즘이나 기타 등등을 제외하면 말이죠.
그래서 사람들은 성능 면에서 기꺼이 세 개중의 하나의 요소에 대해서도 지불을 하는 것입니다.
이것이 바로 여러분이
성능을 원하는 이유입니다.
알겠죠? 여러분이 원하는 다른 것들을 지불하기 위해 사용할 수 있기 때문입니다.
이것이 어떤 면에서, 많은 요소들의 가장 아랫부분에 위치하는 이유이기도 하지요.
왜냐하면 여러분이 수량화 할 수 있는 가장 보편적인 것이기 때문입니다.
여러분은 두 개 중에 하나의 요소에 돈을 지불하고 싶으신가요?
아니면 보안 같은 것들에 대해 세 개 중에 하나에 돈을 지불하고 싶으신가요?
그리고 게다가 이러한 교훈들은
커뮤니케이션, 메모리 같은 리소스 측정에 대해서도 일반화 됩니다.
그리고 우리가 알고리즘 성능을 공부하는 마지막 이유는
정말 재미있기 때문입니다.
스피드는 항상 즐겁죠. 그렇죠?
왜 여러분은 차, 경주마 같은 것들을 빠르게 타나요?
로켓 같은 것들
우리는 왜 그렇게 하죠? 스피드는 즐겁기 때문입니다.
스키. 스키 좋아하나요?
저는 스키를 좋아합니다. 스키 타고 빨리 내려가는 것을 좋아하죠.
정말 재미있습니다.
하키. 빠른 스포츠죠. 그렇죠?
우리는 모두 빠른 스포츠를 좋아하죠.
모두 다는 아니겠지만,
좋아요. 넘어갑시다.
우리가 알고리즘을 왜 공부하는지에 대한
약간의 개념에 대한 것이었습니다.
우리가 생각할 것들에 대한 기본을 쌓는 것입니다.
그래서 우리는 컴퓨터 계산에서
스스로가 어떻게 돈을 만들어 내는 지를 이해하고 싶습니다.
매우 간단한 문제로 시작하도록 하죠.
알고리즘에서 매우 오랫동안 연구되어온 것들 중에 하나입니다.
정렬의 문제이죠.
앞으로 몇 개의 강의 동안 이것에 대해 공부할 것입니다.
왜냐하면 정렬이 매우 많은 알고리즘적인 기술을 포함하기 때문입니다.
정렬문제는 다음과 같습니다.
입력으로는 a1, a2에서 an까지 숫자 시퀀스가 있습니다.
그리고 출력은 이런 수들의 순열입니다.
수열은 숫자들의 재배열입니다.
모든 숫자들은 숫자가 커지는 것을 만족하면서 딱 한 번씩만 나오게 됩니다.
저는 ‘such that’ 의 의미로 종종 달러 표시를 씁니다.
많은 숫자를 가지고, 적절하게 넣습니다.
여기 그것을 해줄 알고리즘이 있습니다. 삽입정렬이라고 부릅니다.
우리가 의사코드라고 부르는 것으로 이 알고리즘을 써보도록 하겠습니다.
의사코드는 약간 프로그래밍 언어
같은 것입니다.
이것은 간단하게 쓴 것입니다.
이것은 A를 1부터 n까지 정렬합니다. 그리고 여기 삽입정렬에 대한 코드가 있습니다.
이것이 의사코드라 부르는 것입니다.
그리고 만약 의사코드를 이해하지 못하면 여러분은 어떠한 표기법에
대해서도 질문하셔도 됩니다.
시간이 갈수록 익숙해지실 겁니다.
의사코드에서 우리는 들여쓰기를 사용합니다.
모든 언어는 처음과 끝을 표시하는
구분문자를 가지고 있습니다. 예를 들면 자바나 C언어에서 '{}'같은 것처럼 말이죠.
우리는 단지 들여쓰기만 사용합니다.
의사코드의 아이디어는 각각의 단계를 이해하는 동안은
가능한한 짧게 해서 알고리즘을 이해하도록 하는데 있습니다.
실제로
이런 것들의 묶음을 보여주는 의도로
들여쓰기를 사용하는 언어도 있었습니다.
일반적으로는 안 좋은 생각이죠. 왜냐하면 한 페이지 넘어가면,
예를 들면
이 묶음의 단계가 어디까지인지 알 수가 없으니까요
반면에, 딱 구분되는 중괄호는 말하기가 훨씬 쉽지요.
이것이 여러분이 소프트웨어 엔지니어링에서 들여쓰기 사용법이 안 좋은 이유입니다.
그러나 짧게 할 수 있고, 조금만 써도 되니까,
우리한테는 매우 좋죠.
이것이 삽입 정렬입니다.
이것이 어떻게 작동하는지 좀 알아보도록 하죠.
기본적으로 배열A를 가지고,
어느 한 지점에서,
바깥 루프는 j에서, 2에서 n으로 움직이고,
안의 루프는 j-1에서 시작해서 0이 될 때까지 실행합니다.
기본적으로 만약 우리가 알고리즘에서 어떤 지점을 보면
우리는 j가 있는 것을 보게 됩니다.
배열A의 j. j번째 원소.
우리가 가장 기본적으로 해야 할 것은 우리가 키(key)라고 부르는 여기서 값을 빼내는 것입니다.
그리고 이 부분이 가장 중요한 부분입니다.
금요일 설명시간에 이것에 대해 더 이야기 나눠보도록 하죠.
매 시간에 이 루프에 의해서 그대로 유지되는
불변성이 있습니다.
그 불변은 이 배열의 이 부분이 정렬되는 것입니다.
그리고 매 시간 루프를 통과하면서 목표는 증가하는 것,
정렬 되어진 이 부분에 하나 더해지는 것입니다.
그리고 우리가 key를 빼냈던 그 방식대로 해서 값을 복사해서
이렇게 올려주는 것입니다. 그리고 키가 가려고 했던 곳에 도달 할 때까지
계속 복사를 하다가 그 자리에 키를 삽입하는 것입니다.
이것이 우리가 삽입 정렬이라고 부르는 이유입니다.
키가 들어갈 곳을 찾을 때까지 이것들을 옮기고,
복사해서 한 칸씩 옮기고
이곳에 키를 넣으면 되는 것입니다.
그러면 A에서 1부터 j까지 정렬 되어 지고, j+1에서 작동합니다.
예를 하나 보겠습니다.
8,2,4,9,3,6 이 있다고 합니다.
2에서 시작합니다. J는 2와 같습니다. 2가 여기에 삽입되어야 되니까,
2,8,4,9,3,6이 됩니다.
그리고 4를 봅니다.
4는 여기 앞으로 가야 되니까,
바깥 루프가 2번 반복된 후에 2,4,8,9,3,6이 됩니다.
그 다음 9를 봅니다.
우리는 9가 바로 그 자리라는 것을 알 수 있습니다.
이 단계에서는 별로 할 일이 없죠.
그러면 반복 후에 우리는 정확하게 똑같은 출력결과를 갖게 됩니다.
그 다음 3을 봅니다. 3은 이곳에 삽입되어야 합니다.
2,3,4,8,9,6입니다.
그리고 마지막으로 6을 보고
6은 이곳으로 삽입되어야 하니까, 2,3,4,6,8,9가 됩니다.
이제 다 됐습니다.
질문 있습니까?
배열은 처음에 1에서 시작하는 것이 맞습니다.
네. A[1...n]. 그렇죠?
이것이 삽입 정렬알고리즘입니다.
그리고 이것이 우리가 분석한 첫 번째 알고리즘이군요.
알고리즘 분석을 돕기 위해 수학 지식을 이용하게 될 것입니다.
무엇보다도,
러닝 타임에 대해서 보도록 하죠.
러닝 타임은 많은 요소에 의해 결정됩니다.
한 가지는 입력입니다.
예를 들면
입력 값들이 이미 정렬이 되어 있으면
삽입 정렬은 할 일이 거의 없습니다.
매 시간 이런 경우와 같을 것이기 때문입니다.
이미 정렬이 돼서 제 자리에 있기 때문에 앞으로 하나씩 이동할 필요가 없는 것이죠.
반면에
삽입정렬의 최악의 경우는 어떻게 될까요?
만약 이것이 반대면, 할 일이 정말 많아지는 거죠.
바깥 루프의 매 단계에서 계속해서 앞으로 이동하는 과정이 필요하게 됩니다.
실제 입력 값 외에도
러닝타임은 물론 입력의 사이즈에도 영향을 받습니다.
여기 예가 있습니다. 우리가 6개의 입력이 있는 경우를 다루었지요.
예로 만약 6*10^9의 입력 값을 다루게 된다면
시간이 더 오래 걸릴 것입니다.
만약 더 많은 입력 값들을 정렬하게 된다면, 시간은 점점 더 많이 걸리겠지요.
전형적으로, 우리가 그것들을 다루는 방식은
입력 사이즈에서 그것들을 파라미터로 나타내는 것입니다.
우리는 우리가 정렬하는 것들의
사이즈에 대해 함수를 이용해
시간에 대해 이야기 나누게 될 것입니다. 그래서 그것의 움직임에 대해 볼 수 있게 될 것입니다.
그리고 마지막으로 러닝 타임에 대해서 말하고 싶은 것은
우리가 러닝 타임에서 상한(upper bound)을 알고자 한다는 것입니다.
우리는 그 시간이 어느 정도 이상은 아니라는 것을 알고자 합니다.
그리고 그 이유는 사용자에게
품질 보장을 하는 것이기 때문입니다.
만약 제가 이것은 작동하지 않을 것입니다 라고 말한다면, 예를 들면,
제가 여러분에게 여기 프로그램이 하나 있고, 이것이 작동하는데 3초 보다 더 걸리지는 않을 것이라고 말한다고 하면
그것은 여러분에게 그것을 어떻게 사용해야 하는지에 대한 진짜 정보를 주는 것이지요.
예를 들면 실시간 세팅에서 말이죠.
반면에, 제가 여기 프로그램이 하나 있고,
이것이 적어도 3초 안에 작동하게 될 것이다라고 말한다면,
이 프로그램이 3년이 걸릴지는 모르는 것입니다.
여러분이 그 컴퓨터의 사용자라면 보장 받을 수 없다는 것입니다.
일반적으로 우리는 상한을 원합니다. 왜냐하면 이것이 사용자에게 보장한 것을
보여줄 수 있기 때문입니다.
다른 종류의 분석방법이 있습니다.
첫 번째로 우리가 집중 해야 할 것은 최악의 경우입니다.
그리고 보통은 어떠한 입력 사이즈에 대해서도
최대시간이 되는 것이라고 정의합니다.
(T(n)).
그것이 하는 일은 입력이 때때로 좋을 때도 있지만
때때로 입력이 나쁠 때에 우리는 최악의 경우를
생각해야 한다는 말입니다. 왜냐하면 그것이
우리가 보장할 수 있는 방법이기 때문입니다.
이것은 단지 때때로 하는 것이 아니라, 항상 하는 것입니다.
그래서 우리는 최대 시간을 보게 될 것입니다.
최대가 없다면, T(n)이 어떤 점에서 관계라는 것을 명심하세요.
함수가 아니라 관계를 나타내는 것입니다.
왜냐하면 시간이 입력 사이즈에
의존하기 때문입니다.
많은 다른 시간들을 얻을 수 있지요.
그러나 최대를 넣으면 관계는 하나의 함수로 변합니다.
왜냐하면 그것이 가질 수 있는 최대 시간은 단지 하나이기 때문입니다. 알겠죠?
때때로 우리는 평균 케이스에 대해서도 이야기 합니다.
때때로 이것을 사용하죠.
T(n)은 사이즈가 n인 입력에 전반적으로 기대되는 시간에 대한 것입니다.
이것은 기대되는 시간이지요.
그러면, 제가 기대되는 시간에 대해 이야기하면
또 다른 것은 무엇을 말해야 할까요?
기대되는 시간이 무슨 뜻일까요? 죄송한데
손들어 주시겠습니까? 기대 입력.
기대입력은 무슨 뜻일까요?
수학이 좀 더 필요하네요. 여기 기대 시간에 무엇이 필요 할까요?
모든 입력의 시간을 구해서 평균을 낸다.
좋습니다.
그것이 기대시간으로 우리가 의미했던 것과 가깝네요.
좋습니다. 딱 맞지는 않는데,
여러분이 말하는 것은 완벽하게 맞는 것이어야 합니다.
네, 학생?
모든 입력 값을 넣었을 때의 시간, 하나의 입력 값을 넣었을 때의 기대되는 확률.
평균에 가중치를 둔 생각이네요.
정확하게 맞습니다. 어떻게 모든 입력 값들의 확률이 무엇인지 알았을까요?
어떻게 이 주어진 상황에서
특정 입력 값의 확률을 알아냈을까요?
모릅니다. 추정해야만 합니다.
그런 추정을 뭐라고 부르죠? 이것을 충족시키기 위해서 어떤 추정방법을 사용해야 하죠?
통계적 분포의
추정이 필요합니다.
그렇지 않으면 기대 시간은 어떠한 의미도 뜻하지 않습니다.
왜냐하면 확률을 모르기 때문입니다.
확률을 하기 위해서 여러분은 추정이 필요하고
이러한 추정을 분명하게 말해야 합니다.
가장 보편적인 추정 중에 하나는 모든 입력이 동등하게 비슷한 것입니다.
이것을 균일 분포라고 부릅니다.
그러나 여러분이 추정할 수 있는 다른 방법들도 있습니다.
그리고 그것들은 모두 사실이 아닐 수도 있습니다. 이것은 좀 더 복잡한데,
여러분이 보다시피, 다행스럽게도,
여러분 모두가 좋은 확률 지식을 가지고 있기 때문에
우리는 평균 같은 것들을 다루는 주제를 말하는데,
어려움을 느끼지 않을 것입니다.
그렇지 않더라도, 시간이 흐르면 이해하게 될 겁니다.
이 수업 선수과목인 확률 수업을 듣는 게 좋을 거에요.
마지막으로 제가 언급할 것은 best-case 분석입니다.
이것을 가짜라고 주장하죠.
가짜에요. 좋지 않습니다.
왜 best-case 분석을 가짜라고 할까요?
best-case 는 아마도 발생하지 않았을 것입니다.
사실 흥미로운데,
정렬문제에 있어서 정렬 되어 진 가장 평범한 것들은 재미있게도
이미 정렬되어진 것들 이었습니다.
또는 적어도 거의 정렬 되어져 있었거나 말이죠. 예를 들면
정렬 되어진 가장 흔한 것들 중에 하나는 숫자를 검사하는 것입니다.
그것들은 들어와서
같은 순서로 쓰여 지는 경향이 있죠.
거의 정렬 되어진 것들을 정렬하죠.
제 말은, 좋습니다.
보장하고 싶죠.
왜 이것이 보장이죠?
뭔가 알아낼 듯 하네요.
그렇지만, 이 부분에서 좀 더 자세하게 봐줘야 합니다.
제가 어떻게 속였죠?
여러분도 속일 수 있죠. 645 00:46:07,643 --> 00:46:14,172 여러분이 원하는 어떤 느린 알고리즘을 가지고 특정 입력을 검사하죠.
그리고 그 입력이 딱 적당하면,
즉시 맞았다고 하면서 이게 답이라고 하겠죠.
하나의 좋은 best-case를 얻은 겁니다.
그러나 엄청나게 많은 수에 대해서는 어떻게 진행되는지 뭐라고 말해줄 수가 없습니다.
그래서 특정 입력에서만 빠르게
작동하는 느린 알고리즘으로 속일 수가 있는 것이죠.
여러분이 할 일은 많지 않으니 걱정하지 않아도 됩니다.
자.
삽입 정렬의 최악의 경우 시간은 무엇인지 한번 볼까요?
자, 약간 재미있는 주제로 들어가 보겠습니다.
첫 번째로, 삽입정렬의 최악의 경우 시간은
여러분이 돌리고 있는 컴퓨터에 따라 다릅니다.
누구의 컴퓨터 인가요? 큰 슈퍼 컴퓨터 인가요?
아니면 손목시계인가요? 그것들은 다른 계산 능력을 가집니다.
그리고 알고리즘을 비교할 때,
우리는 일반적으로 상대적 속도에 대해서 비교합니다.
같은 기계에서 2개의 알고리즘을 비교합니다.
여러분은 단지 알고리즘의 상대적인 속도만 비교하는데,
같은 기계에서 비교할 필요가 있냐고 물을 수도 있습니다.
물론,
절대적인 속도에도 관심이 있을지도 모릅니다.
사실 어떤 기계에서 돌리느냐에 상관없이 알고리즘이 좋을까요?
그리고 이것은 제가 하드웨어에 대해 말하지 않고,
소프트웨어 알고리즘의 최악의 경우 시간에 대해 이야기해서
약간의 혼란을 줄 수 있습니다. 왜냐하면
분명히, 제가 빠른 기계에서 알고리즘을 돌린다면,
빨리 돌아갈 것입니다.
그래서 이 부분이 여러분이 알고리즘에 대한 큰 생각을 얻는 부분이기도 합니다.
왜 알고리즘이 그러한 큰 분야가 되었을까요?
왜 알고리즘은 구글, 아카마이, 아마존 같은 큰 기업을 낳았을까요?
왜 알고리즘 분석은 컴퓨팅 역사 전반에 걸쳐 큰 성공을 이루었을까요?
그리고 완전히
통달하게 되는 능력이고,
정말 어지럽고, 복잡한 상황을 계산해 내서 수학을 쓸 수 있도록
줄이는 능력이 되는 걸까요?
그 아이디어를 우리는 점근적 분석이라고 부릅니다
점근적 분석의 가장 기본적인 생각은
기계 의존적인 상수들을 무시하는 것입니다.
그리고 진짜 러닝 타임 대신에,
러닝 타임의 증가를 보는 것입니다.
진짜 러닝 타임은 보지 않습니다.
러닝 타임의 증가를 봅니다. 그것이 의미하는 바를 알아봅시다.
정말 좋은 생각입니다. 어려운 게 아닙니다.
그렇지 않으면, 첫 번째 수업 시간에 가르치지는 않았을 것입니다.
그렇지만, 매우 중요한 개념이고,
앞으로 몇 번의 강의 시간에 그것이 의미하는 바에 대해
공부하게 될 것입니다.
그리고 여러분이 엔지니어로 일하게 되면,
매일 쓰게 될 것입니다.
그러기 위해서, 우리는 몇몇 표기법을 사용하게 될 것입니다.
특히
점근적 표기법을 사용할 것입니다.
이미 몇몇 분들은 표기법을 보았을 수도 있고,
아직 보지 못한 분들도 있을
것입니다. 그러나 조금은 봤어야 하죠.
우리가 수업에서 주로 사용하게 될 표기법은 세타 표기법입니다.
세타 표기법은 배우기가 매우 쉽습니다.
공식을 만들고,
낮은 차수의 항과 최고차 항을 이끄는 상수를 지워주면 됩니다.
예를 들면, 3n^3
= 90n^2 - 5n + 6046 공식이 있다고 하면,
우리가 지워줄 수 있는 항들은 무엇입니까? n^3이 n^2보다 크니까,
이 항들을 무시해주고,
그리고 θ(n^3)이라고 말할 수 있는 거죠.
매우 쉽습니다.
이것이 세타 표기법입니다. 자, 이것은 세타 표기법의 엔지니어링 조작방법이고,
여기에는 사실
수학적 정의가 있습니다. 그것은 다음 시간에 이야기 하도록 할 것입니다.
함수의 집합에 관한 정의에 관한 것입니다.
여러분은 수학과 컴퓨터 과학 수업 모두에
책임감을 느끼게 될 것입니다.
과정 전반에 걸쳐,
수학과 엔지니어링 상식에 어려움을 느낄 수 있습니다.
이것은 엔지니어링 과정이고,
우리는 모두 하게 될 것입니다.
이것이 여러분이 하는 것들을 이해하는 엔지니어링 방법이고,
그래서 이러한 조작을 할 수 있어야 합니다.
또한, 세타 개념의 수학적 정의를 이해해야 합니다.
그리고 그것과 관계된 빅오 표기법과 오메가 표기법에 대해서도 알아야 합니다.
n이 무한대로 간다고 할 때,
θ (n^2)알고리즘은 결과적으로
항상 θ (n^3)을 이기게 됩니다.
n이 점점 커질수록,
만약 제가 이 식의 완전히 정확한 행동을 계산해 내어도,
이 다른 항들이 어떤지는 그리 문제가 되지 않습니다. θ(n^2)알고리즘이 있다면
이것은 항상 θ(n^3)알고리즘보다 빠르게 돌아갈 것입니다.
이 아래 항들이 무엇이어도 상관이 없습니다.
n^3의 계수가 무엇이든 상관이 없습니다.
이것이(θ (n^2))이 항상 빠를 것입니다.
심지어 θ (n^2)알고리즘이 느린 컴퓨터에서 돌아가고,
θ (n^3)이 빠른 컴퓨터에서 돌아간다고 해도,
점근적 표기법이 좋은 것은 상대적이고,
절대적인 스피드를 비교하는 우리의 문제를 해결해 준다는 것이죠.
왜냐하면 우리는 컴퓨터가 어떻든지,
플랫폼이 어떻든지 간에 이것을 할 수 있기 때문입니다.
다른 플랫폼에서, 다른 상수들을 얻을지도 모릅니다.
진짜 러닝 타임의 기계 의존적인 상수들 말입니다.
그렇지만, 만약 입력의 크기가 커짐에 따라 커지는 정도를 보면,
점근적 분석이 일반적으로 변하지 않는 것을 볼 수 있을 것입니다.
예를 들면, 그림으로 설명 드리겠습니다.
x축은 n으로 놓고, y 축은 T(n)으로 놓겠습니다.
그러면,
이 곡선이 θ (n^3)알고리즘이 될 것이고,
이 곡선이 θ (n^2)알고리즘이 될 것입니다.
그리고 항상 두 알고리즘의 교차점이 n_o가 생기게 됩니다.
여러분이 가지고 있는 컴퓨터의 스피드에 대해 시작점에서
θ (n^2)가 θ (n^3)보다 유리했을지라도,
n_o보다 큰 지역에서 θ (n^2)알고리즘은 θ (n^3)알고리즘보다 작을 것입니다.
그러면 엔지니어링 관점에서 보도록 하죠.
우리가 다루어야 할 몇 가지 문제가 있습니다.
왜냐하면 때때로 n_o는 컴퓨터가 그 문제를 해결하지 못할 만큼
매우 클 수 있기 때문입니다.
그럼에도 불구하고, 우리가 느린 알고리즘에
관심을 가지는 이유는 느린 알고리즘들은
점근적으로는 느려지겠지만,
적당한 크기의 입력 크기가 들어온다면
더 빠를 것이기 때문입니다.
그래서 우리는 좋은 프로그래밍을 하기 위해서
수학적 이해와 엔지니어링 상식 사이의 균형을 맞춰 공부해야 합니다.
그래서 그냥 알고리즘 분석을 끝내서는
여러분은 좋은 프로그래머가 될 수 없을 것입니다.
프로그램을 어떻게 짜는지에 대해서 배워야 하고,
그것들이 관련이 있을 때와 없을 때를 이해하기 위해 실제로 이러한 도구들을 사용하여
연습해 보아야 합니다.
훌륭한 프로그래머가 되고 싶으면,
2년 동안 매일 프로그램을 만들면 됩니다.
그러면 훌륭한 프로그래머가 될 거에요. 만약 세계적인 프로그래머가 되고 싶으면,
10년 동안 매일 프로그램을 만들면 됩니다.
아니면 2년 동안 매일 프로그램을 찌면서 알고리즘 수업을 들으면 되죠.
우리가 했던 삽입 정렬 알고리즘으로 돌아가 봅시다.
삽입정렬 알고리즘 분석을 해볼 겁니다.
최악의 경우를 볼까요?
이것은 우리가 전에 언급했다시피, 입력이 반대로 정렬될 때를 말합니다.
가장 큰 원소가 첫 번째에 오고
가장 작은 것이 마지막에 위치하죠.
삽입될 때마다 모든 것들이 이동하게 됩니다.
중첩 루프를 보면, 러닝 타임을 적을 수 있습니다.
우리는 요약을 하면 됩니다.
우리는 모든 연산, 모든 기본적인 연산에
일정한 시간이 걸린다고 가정하면 됩니다.
그러나 그 일정한 시간에 대해서 걱정할 필요는 없습니다.
왜냐하면 우리는 점근적 분석법을 이용할 것이기 때문입니다.
제가 말했다시피, 이 방법의 좋은 점은 모든 이러한 것들을
약간 무시할 수 있게 해준다는 데에 있습니다.
3 밀리미터 같은 곳이 아니라, 30,000 피트에서 내려다 보는 것과 같은 거죠.
이 각각의 작동들은 가장
기본적인 연산이 될 것 입니다.
연산을 세는 것에 있어서 첫 번째로 고려해야 할은
참조 메모리를 세는 것입니다.
실제로 변수에 몇 번 접근하게 될까요?
이 모델에 대해서 생각하는 약간 다른 방법입니다.
우리가 그것을 하면, 이 루프를 통과하게 될 것입니다.
j는 2에서 n으로 가고 우리는 그 루프 내에서 한 일을
추가하게 될 것입니다.
수학적으로 j가 2에서부터 n까지 갈 때의 합을 구할 수 있습니다.
이 루프 안에서 진행해 가면서 무슨 일이 일어날까요?
음, 이 루프 안에서 일어나는 일은 다양할 겁니다.
그러나 최악이 경우에, 얼마나 많은 연산들이
각각의 j 값에 대해서 어떻게 진행해 나가게 될까요?
주어진 j값에 대해,
이 루프 안에서 얼마나 많은 동작이 일어나게 될까요? 누가 말해보겠습니까?
점근적으로, 그것이 세타 j 입니다.
이 루프가 1에서 j-1이 되므로,
여기서 세타 j가 일어나게 됩니다.
그리고 각각의 단계의 i값에 대해 일정한 양의 일을 하게 되고,
i는 j-1에서 0로 떨어지게 됩니다.
그래서 우리는 θ (j)라고 말하게 됩니다.
여러분 이해하겠어요?
좋습니다. 계산할 공식이 있습니다.
이 공식을 단순하게 하고 싶다면,
답은 무엇일까요?
미안합니다. 뒤쪽이요.
네, 좋습니다. θ (n^2),
좋습니다. 왜냐하면, 이것은 연속된 숫자의 합이기 때문입니다.
무슨 뜻인지 알겠습니까?
수학적 용어들에 대해 알아야 우리가 의사소통 할 수 있지 않겠어요?
이런 것들을 알아야 합니다.
그래야 이야기 할 수 있어요. 이것은 어떤 종류의 시퀀스로 불리나요?
이것은 사실 급수인데,
좋습니다. 어떤 종류의 급수 일까요?
등차 급수.
와, 좋습니다. 의사 소통할 수 있는 예리한 학생이 있네요.
이것은 등차 급수입니다.
기본적으로 1 + 2 + 3 + 4 로 더해지게 되고,
거기에는 몇몇 상수들도 있을 수 있지만, 기본적으로 n까지 1 + 2 + 3 + 4 + 5 + 6로 더해지게 될 것입니다.
그것이 θ (n^2)입니다. 만약 이 수학을 모르면,
책에 단원이 있고, 아니면, 선수과목을 들었어야 했죠.
등차수열
기억이 날 듯 말 듯 하죠?
네네, 좋습니다.
이 조작방법에 대해서 알아두어야 하고,
다음시간에도 좀 더 볼 것입니다. 그렇지만,
Theta 가 어떻게 작동하는지에 대한 Theta 조작법을 꼭 알아두도록 합니다.
Theta는 약한 표기법입니다.
미적분학에 나오는 라이프니츠 표기법과 같은 것이 강한 표기법이죠.
연쇄 법칙(chain rule)은 단지 2개를 지워주면 됩니다.
연쇄법칙에서 없어지는 것은 정말 멋집니다.
라이프니츠 표기법에서는 조작하는 방법이
너무나 직접적으로 보여 집니다.
세타 표기법은 그렇지 않습니다.
여러분이 어려움에 빠졌다고 생각이 든다면,
세타 표기법에서 어떻게 되어가고 있는 것인지 다시 한번 잘 생각해 보아야 합니다.
이것은 조작이 쉬운 표기법이기 보다는
설명적인 표기법이라고 하겠습니다.
이것을 가지고 할 수 있는 많은 조작법들이 있습니다.
그러나 세타 표기법이 어떻게 구해지는지 이해하지 못한다면 앞으로 하는 것을 이해하는데 어려움을 느낄 것입니다.
세타 표기법에 대해서는
다음 시간에 더 이야기 하도록 하죠.
삽입 정렬은 빠를까요?
음, 입력 n의 개수가 적을 때는 적당히 빠르지만,
입력 n의 개수가 많으면 전혀 그렇지 않습니다.
삽입 정렬보다 좀 더 빠른 알고리즘을 보여드리죠.
이것은 합병 정렬이라고 불립니다. 삽입 정렬을 남겨둬야 할지 고민이군요.
지우겠습니다.
이 부분은 나중에 쓰도록 하겠습니다. 공책에 적을 때
왼쪽에 공간을 좀 남겨두세요. 이것이 합병 정렬입니다.
배열 A에 1부터 n까지 있고요.
기본적으로 3단계가 있습니다. 만약 원소가 1개이면,
우리는 이미 정렬이 끝났습니다. 하나의 원소를 정렬한 것이죠.
이미 되었네요. 좋습니다.
재귀 알고리즘. 그렇지 않으면,
우리는 재귀적으로 A를
1부터 |n/2|까지 정렬하고, |n/2|+1부터 n까지를 정렬합니다.
그래서 입력 값들은 두 부분으로 나누어 집니다.
그리고 나서 세 번째로, 우리가 이미 정렬을 마친 두 부분을
합치도록(merge) 합니다.
그것을 하기 위해서, 우리는 서브 루틴을 사용합니다.
제가 보여드리죠.
여기 서브 루틴이 있습니다. 이렇게 작동합니다.
2개의 리스트가 있고, 그것들 중 하나를 20이라고 말하도록 하겠습니다.
반대 순서로 하고 있습니다.
이렇게 정렬했습니다. 그리고 나서 다른 한 개의 서브 루틴을 정렬합니다.
왜 이 순서로 하는지는 모르겠지만, 어쨌든 여기에 또 다른 리스트가 있습니다.
제가 정렬한 2개의 리스트들이 있습니다.
A[1]부터 A[|n/2|]까지,
A[|n/2|+1]부터 A[n]까지 입니다.
그리고 둘을 합병하기 위해,
저는 정렬 리스트를 만듭니다.
제가 처음으로 해야 할 일은 이미 정렬된 2개의 리스트 중
가장 작은 원소가 있는 곳을 찾는 것입니다.
첫 번째 리스트의 헤드에 있을까요? 아니면 두 번째 리스트의 헤드에 있을까요?
2개의 원소를 봅시다.
어떤 원소가 더 작나요? 이것이 더 작지요.
그러고 나면 해야 할 일은 더 작은 원소를 출력 배열에 넣어주는 것입니다.
그리고 지워줍니다.
그 다음에 작은 원소는 어디에 있을까요?
그 답은 2개의 리스트들 중 하나의 헤드에 있을 것입니다.
그러면 저는 이것을 지우고
출력 배열에 넣어주고, 다음 7을 동그라미 쳐줄 것입니다.
7과 9중 7이 더 작으니 7을 출력 배열에 넣어주고, 다음 원소를 동그라미 쳐 줍니다.
다음에는 9와 13을 보게 되고 그래서
각각의 단계에서 배열의 크기와는 상관없이 모든 단계는
몇몇의 고정된 동작 횟수를 가지게 됩니다.
각각의 단계에서 첫 번째로 2개의 원소를 보고,
작은 것을 고른 다음, 제가 현재 리스트의 헤드를 알 수 있도록
포인터를 배열로 옮기는 것입니다.
그러므로
그 시간은 전체 원소 개수
n에 'n'이 됩니다.
우리는 이것을 때때로 선형 시간이라고 부릅니다.
2차나 다른 것이 아니기 때문입니다.
이것은 n에 비례합니다. 입력 크기에 비례합니다.
그것이 선형 시간입니다. 쭉 살펴보면서,
이 간단한 연산을 해보면,
결국 n 연산이 되는 것입니다.
그것은 총 오더 n 시간입니다.
따라오고 있지요?
좋습니다. 그래서 이것이 재귀 프로그램인 것입니다.
이 프로그램에 대해서
반복을 써볼 수 있습니다.
n 원소를 정렬한 시간을 T(n)이라고 해 봅시다.
1개의 스텝을 실행하는데 얼마나 걸릴까요?
일정한 시간입니다. n이 1인지 한번 확인해 봅시다.
n의 사이즈는 독립적입니다.
기계가 무엇이든지 간에 일정한 양의 기계어 명령을 취할 것이고,
우리는 그것을 정수 시간이라고 부릅니다.
θ (1)이라고 부르죠.
이것은 사실 약간은 남용입니다.
그리고 일반적으로 그 이유를 말하기 위해서는,
무엇과 함께 커졌는지 말해야만 합니다.
그러나 우리는 그저 상수를 의미하는
표기법으로 사용하고 있지요.
그래서 남용이라고 볼 수 있습니다. 이러면 사람들이 알아보겠죠.
제가 θ (1)을 쓰면 이런 것들을 단순화 하는 것이고,
기본적으로 같은 것을 뜻을 나타냅니다.
자 그러면 이 두 가지를 정렬해 봅시다.
어떻게 설명할 수 있을까요? 이것을 하는 시간,
n/2의 T와 n-n/2의 T를 더해서 재귀적으로 설명할 수 있습니다.
사실 약간 복잡합니다.
그래서 우리는 정확하지는 않지만, 2T(n/2)라고 씁니다.
약간은 엉성한데,
금요일 설명시간에 이렇게 하는 것이 괜찮은지 알아보도록 하겠습니다.
이것이 알고리즘에 정말 유용한 점입니다.
여러분이 철저하고 정확하면,
원하는 만큼 간단하게 할 수 있습니다.
그렇지만, 이것이 어떻게 될지에 대해서는 걱정하지 않아도 됩니다.
큰 차이가 없기 때문입니다.
그 경우에 대해서는 앞으로 보게 될 것입니다.
그리고 마지막으로,
정렬된 두 리스트들을 합쳐야 합니다.
그리고 합병 서브 루틴을 이용한 것을
분석하면 θ (n)이 나오게 됩니다.
합병 정렬의 성능에 대해 회귀를 쓸 수
있습니다.
T(n)은 n이 1일 때, θ (1)이고, n이 1보다 클 때,
2T(n/2)+ θ (n)입니다.
스탭 1을 해도, 스탭 1,2,3을 해도 모두 그렇습니다.
스탭 1을 하면, 다시 돌아가서 끝나게 되고,
그렇지 않으면, 돌아가지 않고,
스탭 2,3을 하게 될 것입니다.
그래서 이렇게 식을 쓸 수 있습니다.
제가 θ (n)+ θ (1)이라고 말했지만,
θ (1)이 θ (n)보다는 작기 때문에 지워도 되고 그래서 결국 θ (n)이 됩니다.
θ (1)이거나, 2T(n/2)+ θ (n)입니다.
일반적으로 θ (1)은 쓰지 않습니다.
보통은 이것을 생략합니다.
회귀의 솔루션에 차이가 없다면,
보통은 생략합니다.
사실 수학적으로 사실은 아니지만,
알고리즘에서 일정한 크기의 입력(input)에서 어떤 프로그램을 실행시키면,
항상 일정한 시간을 얻게 됩니다.
그래서 이 값이 무엇인지는 신경 쓰지 않아도 됩니다.
반복의 점근적 솔루션에 어떠한 영향도 미치지 않습니다.
이러한 회귀를 어떻게 풀 수 있을까요?
T(n)을 T(n/2)의 관점에서 표현한 것이
책에 있고, 2번째 강의에서도 다루게 될 것입니다.
2번째 강의에서 해결해 보도록 하고요,
남은 시간 동안 할 것은 시각적으로
보여주는 것입니다.
다음시간에 어떤 것을 구체적으로 배우게 될지 말입니다.
이것은 재귀 트리라고 불립니다.
이것은 진짜 회귀에 쓰일 것인데,
거의 2T(n/2)와 같습니다.
이것이 발생하는 것을 사실적이고 명쾌하게 보여드리고 싶은데,
T(n) = 2T(n/2)+cn이고, 여기서 상수 c는 0보다 큽니다.
기본적인 경우를 들어 회귀를 한번
보도록 하겠습니다.
여기 있는 상수를 좀 더 분명하게
해보겠습니다.
재귀 트리에서 우리가 하는 방법은 다음과 같습니다.
우선 식의 왼쪽 부분을 먼저 적어줍니다.
그리고 나서 같다(‘=’) 표시를 써주고,
cn에 트리 처럼
두 개의 T(n/2) 자식을
추가해 줍니다.
T(n/2), T(n/2).
이것을 요약하면 T(n)을 얻게 됩니다.
그래서 T(n)=2T(n/2)+cn 식이 나오게 되는 것입니다.
여기 두 개의 T(n/2)과 cn이 있지요? 그리고 또 해보겠습니다.
여기 cn이 있고, 그 다음 2개의 cn/2가 있습니다.
그리고 각각의 cn/2에는 4개의 T(n/4)이 있습니다.
이것들은 각각 T(n/4)를 갖습니다. 그리고 이것은 T(n/4)를 갖습니다.
저는 계속합니다.
그리고 계속 해 나갑니다.
그러면 결국 이런 것이 나오게 되지요.
단말 노드에 도달 할 때까지 계속 해 나갑니다.
그리고 하나의 단말 노드는 기본적으로 T(1)입니다.
그리고 T(1)은 θ(1)이지요. 그러면 여기서 문제 드리겠습니다.
이 트리의 높이(height)는 무엇입니까?
네, log n. 사실 log n에
매우 가깝습니다.
n에서 시작해서 n/2, n/4 그리고 그런 식으로
쭉 1까지 갑니다.
1까지 도달하는데, n이 나누어진 것들의 수는 log n이지요.
그래서 여기서 높이는 log n입니다. 좋습니다.
앞에 상수 c가 있어도 c는 상관 없습니다.
그러면, 이 트리에는 얼마나 많은 단말 노드들이 있습니까?
이 트리에는 단말 노드가 몇 개 있을까요?
네, 단말 노드의 수는
n입니다.
간단한 가정을 통해서
생각해보면,
n은 2의 거듭제곱이고, 정수입니다.
그러면 T(1)에 도달할 때, 정확하게 log n이 되지요.
그러면 n개의 단말 노드가 생기고,
각 레벨에서 1,2,4,8의 노드들이
만들어 집니다.
우리가 수학을 했네요. 그렇죠?
자, 그러면 각 레벨에서 얼마나 많은 일을 하게 되는지 알아봅시다.
만약 이 트리의 모든 것을 합산하면 T(n)을 얻게 될 것입니다.
한번 계산해 보도록 하죠. 레벨 한 개씩 계산해 보겠습니다.
첫 번째 레벨에는 얼마가 될까요?
cn입니다.
두 번째 레벨은 어떨까요?
역시 cn입니다. 세 번째도
cn입니다.
그러면 모두 합산하면 얼마가 될까요?
θ(n)이 됩니다.
반드시 cn일 필요는 없습니다. 가장 마지막의 경우에는 다른 상수를 가질 수도 있기 때문입니다.
사실은 θ(n)입니다. 그렇지만, 이 부분은 계속 cn이지요.
모든 것을 다 합해서 계산하면, cnlog n이 되고,
그것이 높이입니다. 그리고 + θ(n)이 됩니다.
cnlog n이 θ(n)보다 높은 순서의 항이니까,
남기고, 상수 c를 제거하면
θ(nlog n)이 됩니다. θ(nlog n)은
점근적으로 θ(n^2)보다 빠릅니다.
그래서 합병 정렬은 입력의 크기가 클 때
삽입 정렬보다 빠릅니다.
합병 정렬은 더 빠른 알고리즘이 됩니다.
죄송합니다. 여기 칠판이 안 보이는 것을 신경 못썼네요.
잘 안보이면 크게 말해주세요.
θ(nlog n)이 θ(n^2)보다
더 느리게 커집니다.
그래서 합병 정렬은 점근적으로 삽입 정렬을 이기게 됩니다.
여러분이 삽입 정렬을 슈퍼 컴퓨터에서 실행시켜도
입력이 많은 합병 정렬을 돌리는 PC가 훨씬 빠를 것입니다.
왜냐하면 일단 n이 커지면,
n^2는 n log n 보다 훨씬 더 크기 때문입니다.
실제로 여기에서도 30보다 큰 입력 크기를 넣게 되면 합병 정렬이
이기는 경향이 있습니다.
만약 30개의 원소들처럼 매우 적은 입력을 넣는다면,
삽입 정렬은 완벽하게 사용하기에 좋을 것입니다.
그러나 합병 정렬은 여기에서 입력의 크기가 크지 않아도
삽입 정렬 보다 훨씬 더 빠릅니다.
실제로도 더 빠른 알고리즘인 것이지요.
그것이 오늘 꼭 알아두어야 할 점입니다. 알겠죠?
설명 과제 받는 것과 금요일에 꼭 와야 하는 것 잊지 말고요.
많은 것을 다루게 될 테니
꼭 참석해야 합니다.
그러면 다음 주 월요일에 보도록 합시다.