CSKIM의 코딩로그/Python 알고리즘 검색 결과
6 개의 검색 결과가 있습니다.
CSKIM의 코딩로그/Python 알고리즘

[ Python ] 정렬 알고리즘 - 퀵정렬과 계수정렬

이전 글이었던 선택정렬과 삽입정렬에 이어 오늘은 퀵정렬과 계수정렬을 소개하고자 한다. 앞선 두 정렬은 정렬 알고리즘중에서는 속도가 느린편에 속한다. 물론 거의 정렬이 되어있는 리스트에서의 삽입정렬은 매우 효과적이지만 그것은 아주 제한적인 조건이며, 범용적으로는 느린편에 속하는 알고리즘이다. 그 중 퀵정렬은 앞선 두 알고리즘과 마찬가지로 빅-O 표기법에서의 시간복잡도는 O(N^2) 이다. 여기서 시간복잡도가 같은데 어떻게 더 효과적이라고 할 수 있는지에 대해서 짚고 넘어가자면, 빅-O 표기법은 최악의 경우에서의 시간복잡도를 나타낸다. 따라서 거의 정렬되어있는 경우에서의 삽입정렬이 O(N) 에 수렴하는 시간복잡도를 보여주기도 하지만, O(N^2) 로 나타내는 것이다. 퀵정렬도 마찬가지로 최악의 경우, 이미 ..

2021. 9. 29. 16:59
CSKIM의 코딩로그/Python 알고리즘

[ Python ] 정렬 알고리즘 - 선택정렬과 삽입정렬

정렬은 작업의 효율성을 극대화한다. 우리의 일상에서도 효율성과 정렬은 쉽게 찾아볼 수 있다. 접시를 크기에 맞춰서 진열하고, 대중교통을 줄을 서서 기다리며, 식탁에 숟가락과 젓가락을 구분해서 넣는 것 까지. 우리는 알게 모르게 많은 곳에서 정렬을 한다. 정렬이 일상생활에서도 큰 역할을 하지만, 수많은 계산을 하는 알고리즘에서의 중요성은 말하지 않아도 모두가 공감할 것이다. 정렬 알고리즘은 정말 수없이도 많고, 또 도대체 어떻게 이런 발상을 했는지 신기할 따름이다. 하지만 우리는 새로운 알고리즘을 구현할 게 아니라 이미 만들어진 효율적인 알고리즘을 사용하면 그만이다. 이미 정렬은 충분히 연구가 진행되었을뿐더러 그런 건 우리보다 더 대단한 사람이 해줄 테니까. 소개하고자 하는 정렬 알고리즘은 총 4가지로 [..

2021. 9. 1. 18:46
CSKIM의 코딩로그/Python 알고리즘

[ Python ] BFS 너비 우선 탐색과 DFS 깊이 우선 탐색 ( 2 )

앞서 소개했던 DFS ( Depth First Search ) 깊이 우선 탐색을 이어서 오늘 소개하고자 하는 알고리즘은 BFS ( Breadth First Search ) 이다. 만약에 우리 인간에게 다음 사진과 같은 트리를 주고 노드의 개수를 세어보라고 한다면, 다수가 BFS 와 같이 개수를 셀 것이다. 대다수의 문자가 가로쓰기를 기본으로 하기에 위에서 아래로 그리고 왼쪽에서 오른쪽으로 눈으로 읽는게 체화되어있다. 노드를 문자처럼 한 줄 단위로 넘어가는식으로 이해를 하니 이해도 빠르고, 알고리즘을 짜보는데도 큰 도움이 되었다. 우리가 앞에 살펴보았던 DFS 는 스택 자료구조와 유사하게 구현이 된다는 사실을 알고있다. 반면에 오늘 살펴보고자 하는 BFS 는 큐 자료구조와 유사함을 갖고, 실제로 코드를 구..

2021. 8. 14. 22:19
CSKIM의 코딩로그/Python 알고리즘

[ Python ] BFS 너비 우선 탐색과 DFS 깊이 우선 탐색 ( 1 )

우리가 매우 쉬운 미로를 풀 땐 손을 가져다 대지 않고, 특별한 알고리즘 없이 대충 보는것만으로도 직관적으로 길이 보일 때가 있다. 그걸 따라서 코딩을 하자니 그 간단한 미로조차도 풀기 위해선 알고리즘이 필요한데 내가 어떻게 출구를 찾았는지 코드화 하자니 막막하다. 당신이 수학적 사고가 뛰어나서 바로 생각이 났다면, 나와는 다르게 정형화 된 알고리즘이 필요 없겠지만. 무언가를 창조 해 내려면 모방에서부터 시작한다고 하지 않는가? 그런 알고리즘의 기초와 같은 알고리즘을 오늘 소개하고자 한다. BFS ( Breadth First Search ) 너비 우선 탐색과 DFS ( Depth First Search ) 깊이 우선 탐색이다. 흔히 이런 철자가 비슷한 약자들은 헷갈리기 마련인데, 두 알고리즘은 서로 상당..

2021. 8. 9. 22:11
CSKIM의 코딩로그/Python 알고리즘

[ Python ] 리스트와 스택 그리고 큐

실생활에서 정리정돈은 필수는 아니지만, 누구나 중요하다는 사실을 알고 있다. 정리를 하는 이유는 무엇일까? 그 이유가 몇가지정도 있겠지만 지금 생각나는 것으로는 " 첫째로, 작업공간의 확보를 위해서. 너저분해진 책상 위를 정리해서 책 또는 작업물을 펼쳐놓는다. 둘째로, 시각적인 만족감을 위해서. 정돈되지 않은 상태의 환경에서 정리 후의 환경을 보면 그 규칙성에 만족감을 느끼기 마련이다. 셋째로, 더욱 효율적작업을 위해서. 공구함이나 나사 같은 것을 나중에 빨리 찾아서 사용할 수 있게 규격과 크기에 맞춰서 정리해둔다. " 정도가 있지 않을까 싶다. 코딩에서도 정리정돈은 중요하다. 코더가 보기 쉬운 가독성 좋은 코드로서의 정리도 있을 것이고, 우리가 가장 중요하게 생각하는 시간과 메모리 차원에서도 효율적인 ..

2021. 8. 4. 18:37
CSKIM의 코딩로그/Python 알고리즘

[ Python ] 리스트 컴프리헨션 (list comprehension)

내가 알고리즘 공부를 하면서 처음으로 이유를 검색해본 문제이자 여전히, 그리고 앞으로도 계속해서 사용할 리스트 컴프리헨션을 소개하고자 한다. 알고리즘 공부를 하다보면 새로운 입력을 받기 전에 먼저 비어있는 리스트를 생성해 빈 리스트에 입력값을 넣곤 한다. 이는 메모리의 할당 문제로서 "앞으로 여기에 얼마만큼의 메모리가 사용될 예정이니 비워놔!"라는 예약의 개념이라고 보면 좋을 듯하다. 만약 메모리를 할당해놓지 않으면, 우리도 모여서 앉아있다가 한 명이 추가로 와서 자리를 내려고 하면 옆에 앉아있던 사람들이 모두 일어나서 옆으로 움직이는 작업을 하는데 오랜 시간이 걸리고 복잡하듯이 계산 시에도 미리 메모리를 할당해놓지 않고 데이터를 새롭게 추가한다면, 새롭게 메모리를 할당하고 데이터를 입력해야하므로 그만큼..

2021. 7. 22. 22:38