Tip:
Highlight text to annotate it
X
(번역 : Jisoon Lim) 이번 비디오에서는 리스트를 정렬하는 방법들에 대해 얘기해볼까 합니다.
(번역 : Jisoon Lim) 이번 비디오에서는 리스트를 정렬하는 방법들에 대해 얘기해볼까 합니다.
아마 가장 떠올리기 쉬운 방법은 직접 수동으로 정렬을 하는 거겠지만,
이건 사실, 별로 효율적이지 못한 방법이죠.
이건 사실, 별로 효율적이지 못한 방법이죠.
하지만 ...
리스트를 정렬하는 방법의 첫번째로는 이걸 알려주는 게 좋겠군요.
리스트를 정렬하는 방법의 첫번째로는 이걸 알려주는 게 좋겠군요.
"삽입 정렬" 이라는 방법인데요. 삽 ... 입 ... 정 ... 렬 ...
이 삽입 정렬의 알고리즘을 한 번 그림으로 그려서 설명해 볼게요.
이 삽입 정렬의 알고리즘을 한 번 그림으로 그려서 설명해 볼게요.
알고리즘이란 단어를 쓰면 뭔가 쿨한 느낌을 주긴 하는데
알고리즘이란 단어를 쓰면 뭔가 쿨한 느낌을 주긴 하는데
사실 그냥 정렬하는 과정, 방법을 말하는 것 뿐이에요.
사실 그냥 정렬하는 과정, 방법을 말하는 것 뿐이에요.
사실 그냥 정렬하는 과정, 방법을 말하는 것 뿐이에요.
프로그램은 결국 어떤 일을 하기 위한 알고리즘이란 걸 수행하는 거죠.
프로그램은 결국 어떤 일을 하기 위한 알고리즘이란 걸 수행하는 거죠.
무슨 일을 하기 위한 일반적인 알고리즘이 있으면,
그걸 파이썬으로 작성하거나, C로 작성하거나, 자바로 작성할 수도 있어요.
그걸 파이썬으로 작성하거나, C로 작성하거나, 자바로 작성할 수도 있어요.
그걸 파이썬으로 작성하거나, C로 작성하거나, 자바로 작성할 수도 있어요.
서로 다른 언어로 짠 프로그램들이지만, 알고리즘이 같다면 결국 정렬하는 방식도 같은 거에요.
서로 다른 언어로 짠 프로그램들이지만, 알고리즘이 같다면 결국 정렬하는 방식도 같은 거에요.
서로 다른 언어로 짠 프로그램들이지만, 알고리즘이 같다면 결국 정렬하는 방식도 같은 거에요.
자 ... 그러니까 이제 삽입 정렬 알고리즘을 얘기해봅시다.
자 ... 그러니까 이제 삽입 정렬 알고리즘을 얘기해봅시다.
간단한 예를 들어 보죠.
리스트 ... 그러니까, 파이썬 리스트가 하나 있습니다.
리스트 ... 그러니까, 파이썬 리스트가 하나 있습니다.
우리는 파이썬에서 코드를 짤 거니까, 파이썬 리스트에요.
우리는 파이썬에서 코드를 짤 거니까, 파이썬 리스트에요.
그리고 그 리스트가 [7, 3, 1, 2, 4, 6] 이라 치고 ...
이 리스트를 삽입 정렬을 하려면 말이죠
원소 하나씩 확인해 보면서, 앞에 있는 원소하고 크기를 비교해요.
원소 하나씩 확인해 보면서, 앞에 있는 원소하고 크기를 비교해요.
한 원소를 바로 앞에 있는 원소랑 비교해서, 만약 작다면,
한 원소를 바로 앞에 있는 원소랑 비교해서, 만약 작다면,
두 원소의 순서를 바꿔 주는 거죠.
자, 무슨 말이냐면
여기 있는 0번째 원소인 7부터 시작합니다.
여기 있는 0번째 원소인 7부터 시작합니다.
근데, 보아하니 0번째부터 시작할려면,
근데, 보아하니 0번째부터 시작할려면,
어랏? 앞에 다른 원소가 없으니까 비교할 수가 없네요.
그러니까 0번째 원소부터 시작하는 건 의미가 없죠.
이 알고리즘을 구현하려면 결국은 3번째 원소부터 시작해야 ...
이 알고리즘을 구현하려면 결국은 3번째 원소부터 시작해야 ...
아이고, 죄송 ... (ㅋㅋㅋ) 3번째가 아니라, 이게 0번째고 ... 1번째 원소부터 시작해야 되요.
아이고, 죄송 ... (ㅋㅋㅋ) 3번째가 아니라, 이게 0번째고 ... 1번째 원소부터 시작해야 되요.
아이고, 죄송 ... (ㅋㅋㅋ) 3번째가 아니라, 이게 0번째고 ... 1번째 원소부터 시작해야 되요.
이게 0 번째, 이게 1 번째 ... 좀 헷갈릴 수도 있지만, 원소 3 이 1 번째고 원소 7 이 0 번째인 겁니다.
이게 0 번째, 이게 1 번째 ... 좀 헷갈릴 수도 있지만, 원소 3 이 1 번째고 원소 7 이 0 번째인 겁니다.
이게 0 번째, 이게 1 번째 ... 좀 헷갈릴 수도 있지만, 원소 3 이 1 번째고 원소 7 이 0 번째인 겁니다.
자, 그러니까 이 3 부터 시작해서, 앞에 있는 모든 원소와 비교를 해 보는 거죠.
자, 그러니까 이 3 부터 시작해서, 앞에 있는 모든 원소와 비교를 해 보는 거죠.
만약 3 이 앞의 원소보다 작다면, 3 과 앞의 원소를 바꿔넣어요.
만약 3 이 앞의 원소보다 작다면, 3 과 앞의 원소를 바꿔넣어요.
그럼 아, 3 이 7 보다 작군? 7보다 작네.
그럼 아, 3 이 7 보다 작군? 7보다 작네.
그럼 아, 3 이 7 보다 작군? 7보다 작네.
그럼 뭘 하냐면, 7 을 3 이 있던 자리로 옮깁니다.
그럼 뭘 하냐면, 7 을 3 이 있던 자리로 옮깁니다.
자, 여기에다가 ...
그러니까 우린 ... 지금 3 을 앞의 모든 원소와 비교해서,
그러니까 우린 ... 지금 3 을 앞의 모든 원소와 비교해서,
그러니까 우린 ... 지금 3 을 앞의 모든 원소와 비교해서,
자, 3 이 7 보다 작죠? 3 이 7 보다 작네요.
자, 3 이 7 보다 작죠? 3 이 7 보다 작네요.
그러니까 7 을 3 이 있던 자리에 놓고,
3 을 7 이 있던 자리에 놓읍시다.
자, 이렇게 해놓으니 3 앞에 비교할 다른 원소가 없네요?
자, 이렇게 해놓으니 3 앞에 비교할 다른 원소가 없네요?
0 번째 앞에는 아무것도 없으니까,
3 을 이 자리에 그냥 둡시다.
자, 이제 우리의 리스트는 ...
이제 우리의 리스트는 [3, 7, 1, 2, 4, 6] 이 됐어요.
여기서, 주목해야 될 재미있는 점이 있는데요.
여기서, 주목해야 될 재미있는 점이 있는데요.
이렇게 리스트를 만들고 나니,
0 번째 원소는 반드시 1 번째 원소보다 작게 됐어요.
그러니까 0 번째랑 1 번째는 정렬이 끝난 거죠.
그러니까 0 번째랑 1 번째는 정렬이 끝난 거죠.
0 번째랑 1 번째는 정렬이 끝난 거에요.
0 번째랑 1 번째는 정렬이 끝난 거에요.
그러니까, 이런 식으로 계속해 나가면,
원소 인덱스를 늘려 가면서 똑같이 하다 보면,
원소 인덱스를 늘려 가면서 똑같이 하다 보면,
전부다 정렬이 되겠죠.
계속하면서 설명할게요.
자, 1 번째 원소까지 됐으니까 2 번째 원소로 넘어갑니다.
자, 1 번째 원소까지 됐으니까 2 번째 원소로 넘어갑니다.
2 번째 원소는 1 이네요.
이 1 을 ... 여기다 적어놓고,
이 1 을 ... 여기다 적어놓고,
이 1 을 ... 앞의 다른 원소와 비교하면,
이 1 을 ... 앞의 다른 원소와 비교하면,
어, 1 은 7 보다 작나? 네, 작네요.
어, 1 은 7 보다 작나? 네, 작네요.
그러니까 7 을 1 이 있던 자리로 옮깁시다.
그리고 1 을 그 앞의 원소와 비교하거나 ... 아니면 일단 7 이 있던 자리에다 옮겨놓을 수도 있겠네요.
그리고 1 을 그 앞의 원소와 비교하거나 ... 아니면 일단 7 이 있던 자리에다 옮겨놓을 수도 있겠네요.
그 다음은, 1 은 3 보다 작나요? 아, 작지요 물론.
그 다음은, 1 은 3 보다 작나요? 아, 작지요 물론.
그러니까 3 을 1 이 있던 자리에 놓고,
1 을 3 이 있던 자리에 놓읍시다.
자, 그럼 우리 리스트는
이렇게 됐네요.
[1, 3, 7, 2, 4, 6] 이 됐어요.
그러니까, 우리가 n 번째 인덱스까지 하면 ...
지금의 경우 2 번째 인덱스까지 했죠. 원래 1 이란 값을 갖고 있었고요.
지금의 경우 2 번째 인덱스까지 했죠. 원래 1 이란 값을 갖고 있었고요.
하고 나니 2 번째 인덱스까지 정렬이 끝났네요.
이 부분까지 정렬됐어요.
계속 정렬하다 보면 또 순서가 바뀔진 몰라도 아무튼 이 부분만은 정렬된 거죠.
계속 정렬하다 보면 또 순서가 바뀔진 몰라도 아무튼 이 부분만은 정렬된 거죠.
계속 정렬하다 보면 또 순서가 바뀔진 몰라도 아무튼 이 부분만은 정렬된 거죠.
계속 정렬하다 보면 또 순서가 바뀔진 몰라도 아무튼 이 부분만은 정렬된 거죠.
그러니까 알겠죠? 끝까지 이런 식으로 하면 다 정렬될 거에요.
그러니까 알겠죠? 끝까지 이런 식으로 하면 다 정렬될 거에요.
그러니까 알겠죠? 끝까지 이런 식으로 하면 다 정렬될 거에요.
그럼 이제 리스트의 다음 인덱스, 3 번째 인덱스에 있는 ... 2 로 갑시다.
그럼 이제 리스트의 다음 인덱스, 3 번째 인덱스에 있는 ... 2 로 갑시다.
그럼 이제 리스트의 다음 인덱스, 3 번째 인덱스에 있는 ... 2 로 갑시다.
2 입니다.
마찬가지로, 2 와 7 을 비교하면, 당연히 2 는 7 보다 작으니까 ...
마찬가지로, 2 와 7 을 비교하면, 당연히 2 는 7 보다 작으니까 ...
7 을 2 가 있던 자리에 놓고,
2 를 7 이 있던 자리에 놓고요.
이제 2 와 3 을 비교해요. 2 는 3 보다 작으니까,
이제 2 와 3 을 비교해요. 2 는 3 보다 작으니까,
3 을 2 가 있던 자리에 놓고,
2 를 3 이 있던 자리에 놓고요.
이제 2 와 1 을 비교해요. 2 가 1 보다 작나요?
이제 2 와 1 을 비교해요. 2 가 1 보다 작나요?
안 작죠. 그러니까 그냥 냅두면 되요.
안 작죠. 그러니까 그냥 냅두면 되요.
이제 앞쪽으로 더 갈 데가 없네요.
자, 이렇게 우리는 이 2 를 앞에 있는 모든 원소와 비교했고요.
자, 이렇게 우리는 이 2 를 앞에 있는 모든 원소와 비교했고요.
자, 이렇게 우리는 이 2 를 앞에 있는 모든 원소와 비교했고요.
다 하고 나니까, 우리 리스트가 이렇게 됐네요.
[1, 2, 3, 7, 4, 6] 이 됐습니다.
결국 3 번째 원소까지 정렬됐죠.
0번째, 1번째, 2번째, 3번째 원소까지 정렬됐어요.
0번째, 1번째, 2번째, 3번째 원소까지 정렬됐어요.
자, 그럼 다음 원소로 넘어갑시다.
자, 그럼 다음 원소로 넘어갑시다.
한 가지 짚고 넘어갈 게, 여러분이 실제로 구현할 때는
한 가지 짚고 넘어갈 게, 여러분이 실제로 구현할 때는
다른 방법을 써도 되요. 그러니까 꼭 굳이 ...
다른 방법을 써도 되요. 그러니까 꼭 굳이 ...
이걸 예로 들면, 2 가 7 보다 작으니까 2 와 7 의 위치를 바꿨잖아요?
이걸 예로 들면, 2 가 7 보다 작으니까 2 와 7 의 위치를 바꿨잖아요?
이걸 예로 들면, 2 가 7 보다 작으니까 2 와 7 의 위치를 바꿨잖아요?
이걸 예로 들면, 2 가 7 보다 작으니까 2 와 7 의 위치를 바꿨잖아요?
이걸 예로 들면, 2 가 7 보다 작으니까 2 와 7 의 위치를 바꿨잖아요?
하지만 실제로는, 바로 2 의 위치를 바꾸지 않고 계속 앞의 원소와 비교할 수도 있어요.
하지만 실제로는, 바로 2 의 위치를 바꾸지 않고 계속 앞의 원소와 비교할 수도 있어요.
하지만 실제로는, 바로 2 의 위치를 바꾸지 않고 계속 앞의 원소와 비교할 수도 있어요.
그리고 비교가 다 끝난 다음에 2 의 위치를 바꿔주는 거죠.
그리고 비교가 다 끝난 다음에 2 의 위치를 바꿔주는 거죠.
물론 이렇게 하나씩 옮기는게 이해하기는 쉽지만 ...
사실 막상 구현하다 보면 다른 방법이 더 생각날걸요.
사실 막상 구현하다 보면 다른 방법이 더 생각날걸요.
아무튼, 다음은 4 네요.
똑같은 방식으로 ... 4 는 7 보다 작으니까,
똑같은 방식으로 ... 4 는 7 보다 작으니까,
7 을 4 의 자리에 놓고
4 를 7 의 자리에 놓고요.
4 는 3 보다 작나요? 아니죠.
4 는 3 보다 작나요? 아니죠.
그러니까 여기까지. 끝났습니다.
이제 4 번째 원소까지 전부 정렬돼서 0 1 2 3 4 가 됐습니다.
이제 4 번째 원소까지 전부 정렬돼서 0 1 2 3 4 가 됐습니다.
이제 4 번째 원소까지 전부 정렬돼서 0 1 2 3 4 가 됐습니다.
이제 우리 리스트는 ... 화면을 좀 내릴게요.
이제 우리 리스트는 ... 화면을 좀 내릴게요.
이제 우리 리스트를 써보면 ...
이제 우리 리스트를 써보면 ...
[1, 2, 3, 4, 7, 6] 이 됐습니다.
마지막 원소만 남았어요.
이제 6 을 앞과 비교할 거에요. 이게 마지막이겠네요.
이제 6 을 앞과 비교할 거에요. 이게 마지막이겠네요.
아까는 4 를 비교했는데 이제는 6 이에요.
아까는 4 를 비교했는데 이제는 6 이에요.
6 이 7 보다 작나요? 그렇죠.
그러니까 7 을 6 이 있는 자리에 놓고,
6 을 7 이 있던 자리에 놓고요.
6 이 4 보다 작나요? 아니죠.
그럼 여기까지.
정렬이 끝났다는 걸 알 수 있죠.
앞으로 더 가 봤자 전부 4 보다 작은 원소들이거든요.
앞으로 더 가 봤자 전부 4 보다 작은 원소들이거든요.
끝났어요. 정렬 끝입니다.
정렬된 리스트는 이제 ... [1, 2, 3, 4, 6, 7] 이군요.
수고하셨고, 다음 비디오에선 이번에 설명한 알고리즘을 실제파이썬 함수로 구현해 볼게요.
수고하셨고, 다음 비디오에선 이번에 설명한 알고리즘을 실제파이썬 함수로 구현해 볼게요.
수고하셨고, 다음 비디오에선 이번에 설명한 알고리즘을 실제파이썬 함수로 구현해 볼게요.
수고하셨고, 다음 비디오에선 이번에 설명한 알고리즘을 실제파이썬 함수로 구현해 볼게요.