AI Platform / Web

퀵 정렬(Quick Sort)란, 피벗(pivot, 기준값)을 기준으로 큰 데이터와 작은 데이터를 찾아서 위치를 변경하는 정렬 방식이다. 퀵 정렬(Quick sort) 동작 순서 오름차순으로 정렬하는 방법에 대해 알아보자. 기준점이 될 index를 pivot으로 설정한다.(random value) 새로운 리스트 2개를 만들고, pivot 값보다 작은 값들과 큰 값들을 모아서 각각 리스트에 담는다. pivot값을 기준으로 작은 값이 모든 리스트는 왼쪽, 큰 값들의 리스트는 오른쪽으로 붙인다. 1-3을 재귀로 반복한다. 퀵 정렬(Quick sort) 구현 퀵 정렬의 구현 방법은 아래와 같다. def quick_sort(collection): """ Examples: >>> quick_sort([0, 5, 3..

프로그램에서 가장 간단하고 대표적인 알고리즘이 탐색 알고리즘이다. 기초적인 탐색 알고리즘에는 2가지가 있다. 선형탐색알고리즘이란, 순차적으로 원하는 결괏값을 탐색하는 것이다. 이진탐색알고리즘은 중간지점을 기준으로 반씩 제외하여 원하는 결괏값을 찾는 알고리즘이다. 각각의 알고리즘에 대해 조금 더 알아보고 코드로 적어보도록 하자. 1명을 찾기 위해 100만 명을 검사한다고 생각해 보자. 어떻게 찾는 것이 효율적일까? 선형탐색의 경우에 순차적으로 원하는 것을 찾는 방식이다. 만약 원하는 사람이 마지막에 있는 경우, 최악의 효율로 100만 번을 검사를 해야 원하는 사람을 찾을 수 있다. 이진탐색의 경우에는 최악의 경우는 20번이다. 생각보다 효율차이가 큰 것을 확인할 수 있다. 각각의 알고리즘에 대해 알아보자...

사실 Python에서 Linked List를 잘 사용하지 않는 것같다. 왜냐하면 구현이 편한, list나 deque로 어느정도 커버가 가능하기 때문이다. 하지만 반드시 필요한 자료구조이기 때문에, 이번 기회에 이해해 보도록 하자. 일반적인 자료구조에서의 리스트란, 순서를 가진 데이터의 집합을 가리키는 추상 자료형(abstract data type)이다. 자료구조의 관점에서 리스트의 종류로는, 순차 리스트와 연결 리스트로 나뉜다. 오늘 다루고자 하는 내용은 리스트의 한 종류인, 연결 리스트(Linked List)에 대해 알아보자. 순차 리스트: 저장소를 배열형태로 만드는 것. 연속적인 메모리 공간에 저장(python에서 list) 연결 리스트: 저장 할때 마다 메모리를 확보해서 추가시키는 것. 메모리의 동..

Queue는 컴퓨터 과학에서 중요한 선입선출 자료구조 중 하나이다. 사실 큐의 일상 예시로 설명해 보면, 줄을 서는 개념과 비슷하다. 맛있는 마카롱 집을 가기 위해 줄을 선다고 해보자. 이 경우 먼저 줄을 선 사람이 먼저 마카롱을 사고, 나중에 온 사람이 나중에 마카롱을 사는 것과 같은 원리라고 할 수 있다. 이러한 Quere를 간단한 개념부터 시작해서, 선형 큐(Linear Queue) 원형 큐(Circlar Queue) 등등의 여러 방법으로 구현해 보자. 큐(Queue) 큐는 선입선출(FIFO : First-In-First-Out) 구조의 자료구조로 먼저 넣은 데이터를 먼저 꺼낸다. 이때, 먼저 데이터를 추가하는 작업을 인큐(enqueue)라고 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 ..

자료구조에서 가장 중요하고 기초라고 할 수 있는 후입선출(LIFO) 구조의 스택에 대해 알아보자. 기본적으로 자료구조에서 기본적으로 자료를 담을 수 있는 방식에는 배열(Array)과 스택(Stack), 큐(Queue)가 있다. 각각의 기본적인 공통점은 자료를 넣어두고 사용하는 것이다. 여기서 우리가 생각할 수 있는 점은 효율적으로 자료를 관리하기 위해, 자료를 담는 방식에 대한 차이를 이해하는 것이 중요하다. 컴퓨터 과학에서 중요한 자료구조 중 하나인 스택(Stack)에 대해 알아보도록 하자. 스택(Stack)이란 스택은 데이터를 임시 저장할 떄 사용하는 자료구조이다. 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 되어 있다. 이러한 자료구조를 직관..

자료구조의 첫 번째 정리할 부분은 배열이다. 배열은 사실 우리가 사용 중인 파이썬의 list라고도 할 수 있겠다. 그렇다면 파이썬의 list와 자료구조의 배열은 완전히 같은 개념이라고 할 수 있을까? 배열에 대해 간단히 알아보고 코딩으로 체득하도록 해보자. 자료구조의 배열이란 일반적인 자료구조에서의 배열이란, 순서를 가진 데이터의 집합을 가리키는 추상 자료형(abstract data type)이다. 즉, 순서를 가진 데이터 집합을 모두 배열이라고 할 수 있다. 배열을 종류는 크게 2가지로 나뉜다. - 순차 리스트: 저장소를 배열형태로 만드는 것. 연속적인 메모리 공간에 저장(python에서 list) - 연결 리스트: 저장 할때 마다 메모리를 확보해서 추가시키는 것. 메모리의 동적할당을 기반으로 구현 일..

전반적인 자료구조/알고리즘에 대한 기초 글을 작성하려 한다. 필요한 내용을 참고해서 확인해 보자. 알고리즘 확인하기 Python으로 자료구조 조금 더 알아보기 [자료구조 기초] Data Structure 기초 시작하기 [선형 구조 - Python] 배열 [선형 구조 - Python] 스택 [선형 구조 - Python]큐 [선형 구조 - Python] 연결 리스트 Python으로 알고리즘 조금 더 알아보기 [알고리즘 기초] Algorithm 기초 시작하기 - python [검색 알고리즘] 선형 탐색과 이진탐색 [검색 알고리즘] 해시 [재귀 알고리즘] 재귀 [재귀 알고리즘] DFS [재귀 알고리즘] BFS [정렬 알고리즘] 버블 정렬 [정렬 알고리즘] 선택 정렬 [정렬 알고리즘] 삽입 정렬 [정렬 알고리즘..

우리가 알고리즘에 대해서 대부분 학교 수업이나 코딩 테스트를 위해 처음 접하는 경우가 많다. 그렇다면, 알고리즘이란 무엇이고 왜 알고리즘을 배워야 할까? 좋은 알고리즘이란, 간단하다. 문제를 해결하는 것 문제를 더 잘 해결하는 것 알고리즘을 사용하는 이유는 문제를 더 잘 해결하기 위함이다. 따라서 어떻게 문제를 잘 해결할 수 있을지 같이 고민해볼까 한다. 여기서 제공하는 실습 문제만 암기하여 빠르게 작성할 수 있다면, 알고리즘을 공부하기 위한 기초 코딩은 완성 되었다고 할 수있다. 사실 알고리즘을 공부하고자 하는 우리의 목표는 우리가 만들고자 하는 로직을 작성할 수 있게 함에 있다. 따라서 기초적인 알고리즘을 공부하기 전에 파이썬에 대한 기본적인 숙련도가 필요하다고 생각된다. 기본적으로 for문을 100..