꿈 많은 사람의 이야기

퀵 정렬(quick sort)에 대해서 많이 들어보셨을 겁니다. 정렬에는 삽입 정렬(insertion sort), 선택 정렬(selection sort) 등이 있는데요. 퀵 정렬은 이러한 정렬 알고리즘보다 훨씬 빠른 속도로 정렬을 해주는 알고리즘입니다. 퀵 정렬은 분할 정복(divide and conquer) 방법을 사용하는 알고리즘 중 하나입니다 분할 정복 문제를 작은 2개로 분리하고 각각 해결한 다음 이를 합쳐서 원래의 문제를 해결하는 방법입니다. 보통 재귀 호출 등으로 사용하게 됩니다 퀵 정렬 과정 퀵 정렬을 위와 같은 과정을 통해 정렬이 진행됩니다. 1. 리스트 안에 한 요소를 선택합니다. 이를 pivot(피벗)이라고 합니다. 2. pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분리시..

최대공약수, 최소공배수 구하는 것은 심심하면 나오는 과제입니다 처음 이 문제를 접했을 때는 최소공배수, 최대공약수가 뭐였는지도 기억이 안났던게 기억이 나네요 크흠.. 그래서 이번 글은 파이썬으로 최대공약수, 최소공배수를 구현해봅니다 먼저 최대공약수입니다 최대공약수는 소인수분해를 이용해서 구하는 방법도 있습니다. 뭐 예를 들어 60과 48이 있다고 가정하면 60 = 2^2 * 3 * 4 48 = 2^4 * 3 이니까 공통된 수 중 지수가 작은 것을 골라내면 2^2 * 3 = 12가 최대공약수가 됩니다. 근데 이 방법 말고 유클리드 호제법을 사용하면 더 쉽게 구현할 수 있습니다 유클리드 호제법은 위의 설명에도 나와있지만, 192와 72가 있으면 큰 숫자를 작은 숫자로 나누어 나머지를 구합니다. 192 % 7..

파이썬 알고리즘 기본을 계속 하고 있다. 지난 번에 공부 했던 힙 정렬, 삽입 정렬, 선택 정렬, 버블 정렬 등도 계속 복습도 해야하는데.. 주말에 해야하는데 참 쉽지 않다. 아무튼 이번 포스팅은 정말 기본적인 알고리즘이다. 숫자 뒤집는 방법(거꾸로 출력하는 방법), 소수 값 출력하는 방법과 배수 출력하는 방법이다. 너무 간단한다 먼저 배수이다 만약 3의 배수를 구하고 싶으면 어떤 값을 3으로 나누었을 때 0으로 떨어지면 그 값은 3의 배수이다 3과 5의 배수를 동시에 구하고 싶으면 n % 3 == 0 and n % 5 == 0 의 조건이 성립되면 된다 이 조건을 가지고 코드를 작성하면 된다. 아래와 같다. 숫자를 거꾸로 출력하는 방법(혹은 문자열을 거꾸로 출력)은 reverse 방법을 이용하는 방법이나..

이번 포스팅은 힙 정렬(heap sort)에 대해서 공부를 합니다. 먼저 힙(heap)에 대해서 알아야겠죠. 힙은 크기(우선 순위)을 중심으로 정렬된 시퀀스를 활용할 때 유용한 자료구조입니다. 힙은 한 노드가 최대 두 개의 자식노드를 가지면서 마지막 레벨을 제외한 모든 레벨에서 완전 이진트리(complete binary tree)를 기본으로 구조를 가지고 있습니다. 바로 위 사진처럼 되어 있는 구조가 힙 구조입니다. 잘 보면 이진 탐색 트리(binary search tree)와 구조가 살짝 차이가 있는데요 각 노드의 값은 자신의 자식노드보다 크거나 같습니다. 이게 이진 탐색 트리와는 차이점이죠. 이진 탐색 트리에서는 자식의 노드가 부모의 노드보다 값이 클 수도 있습니다. 하지만 힙에서는 그렇지 않습니다...

이번 포스팅은 합병정렬(Merge sort)에 대해서 정리합니다. 병합정렬이라고도 불리우는 이 정렬은 데이터를 잘게 쪼개고(divide) 크기를 비교해 정렬합니다(conquer) 그리고 이를 합칩니다(merge) 이를 더 이상 합칠 array가 없을 때까지 반복합니다. 위 그림을 보시면 쉽게 나와있습니다. 칸아카데미 페이지에 나와있는 설명인데요. 위에선 2개씩 잘개 쪼갭니다. 쪼갠 뒤 정렬을 하면서 합쳐줍니다. 그러면 최종적으로 정렬된 데이터가 나오게 되겠죠! 그럼 코드로는 어떻게 될까요? 파이썬을 활용해서 코드를 작성해봅니다. 풀 코드를 보기 전에 merge_sort가 어떻게 보이는지 봅니다. list가 1보다 작거나 같으면 return하고 그게 아니면 mid 값을 // 2로 해서 절반을 기준으로 합니..

이번 포스팅은 파이썬으로 자료구조, 알고리즘 공부하기 쉘 정렬(shell sort)과 버블 정렬(bubble sort)에 대해서 정리합니다. 여러가지 정렬 알고리즘이 있습니다. 지난 포스팅에선 삽입 정렬, 선택 정렬에 대해서 보았는데요 기본적인 정렬 중 버블 정렬이라는 것이 있습니다! 버블 정렬은 말 그대로 거품처럼 뽀글뽀글 올라가며 정렬을 하는데요 예시를 들면 이렇게 진행됩니다. 처음부터 하나씩 비교를 하면서 큰 것을 뒤쪽으로 몰아넣죠. 그리고 fix 시킵니다. 그리고 그 다음 루틴에서 또 돌고.. 이렇게 진행합니다. 바로 파이썬 코드로 봅시다 핵심은 def bubble_sort입니다. 정렬되지 않은 list를 입력 받습니다. 2개의 for문을 돌면서 진행합니다. 맨 처음 for문은 len - 1 범위..

파이썬으로 알고리즘, 자료구조 공부하기! 이번에는 삽입 정렬, 선택 정렬이다 정렬 알고리즘에서 많이 나오는 것들이 버블 정렬, 삽입 정렬, 선택 정렬 등이 있는데 당분간 이 정렬에 대해서 공부하고 정리하려고 한다! 먼저 선택 정렬(selection sort)이다 선택 정렬은 위 그림을 보면 이해가 편하다 매 step으로 나뉘어 진행하는데 첫 번째에 스탭을 돌면 가장 작은 값이 맨 처음으로 온다. 그리고 첫 번째 값을 fixed 시켜놓고 2번째 값 부터 시작하고 또 다시 비교한다. 그렇기 때문에 비교는 N * (N-1)만큼 비교를 하게 된다. 하지만 교환 횟수는 N - 1 정도이다 파이썬으로 코드를 구현해보자 이렇게 간단한 하나의 함수로 만들 수 있다. 2개의 for문을 돈다. N * (N -1)이므로 그..

지난 포스팅까지 파이썬으로 연결 리스트(linked list)와 스택(stack), 큐(queue)를 공부했다. 이번에는 트리 구조이다 트리는 정말 많이 쓰인다. 일단 리눅스 구조만 봐도 트리구조이다. 간단하게는 족보라고 생각하면 좋다 맨 위에 최초 조상님이 계실거고 그 밑에 자녀들 등등 해서 족보가 그려진다. 이런 구조가 트리구조라고 할 수 있다. 트리도 뭐 이진 트리냐, 완전 이진트리냐 등등이 있다. 보통 이진트리가 많이 사용된다. 트리에는 root와 부모 노드(parent node), 자식 노드(child node)가 있다. 위의 구조에서 root는 A이고 A의 자식은 B, C이다. 그리고 B,C의 부모는 A이다. 이런 식으로 부모, 자식 노드를 구분할 수 있다. 형제 노드(sibling node)..

파이썬으로 자료구조, 알고리즘 공부를 다시 하고 있다 너무 오랜만에 해서 뜨문뜨문 기억이 나면서 진행하고 있다 지난 포스팅까지는 연결 리스트(linked list)와 이중 연결 리스트(doubly linked list)를 다뤄봤다 이번에는 스택과 큐이다. 먼저 스택이다. stack은 자료구조에서 정말 많이 보이는 그리고 많이 사용되기도 하는 자료구조이다 Last In First Out의 구조 즉 LIFO의 구조를 따른다 스택의 구조를 그림으로 설명하면 위와 같이 된다 A->B->C->D 순으로 들어오고 가장 맨 위를 top이 가리킨다. 그리고 마지막에 들어온 D부터 차례대로 out되는데 이 과정을 pop 이라고 한다. 또한, 스택에 들어오는 과정은 push라고 한다. 이 과정을 파이썬 코드로 작성하면 어..

지난 글에서 파이썬으로 연결리스트를 구성해봤습니다.(https://lsjsj92.tistory.com/461) 하지만 단순한 연결리스트는 단방향만 가기 때문에 양방향보다는 효율이 떨어집니다 그것을 보완하기 위해 양방향으로 갈 수 있는 연결 리스트를 구상했는데요 그게 이중 연결 리스트(doubly linked list) 입니다. 그림으로 보면 아래와 같은 구조입니다. 각 노드가 있고 노드안에 prev, next가 있어서 prev는 본인 노드 전의 지점을 가리킵니다. next는 본인 노드 다음의 노드를 가리킵니다. 어렵지 않는 구조이죠 지난 번 포스팅에서 크게 달라지는 것은 없으며 prev 구조가 추가 되었습니다. 이게 끝입니다 ㅎㅎ 단순하죠? 하지만 삽입이나 삭제 같은 연산을 할 때는 좀 많이 달라집니다...