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)라고 ..

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

아래의 내용은 파이썬 알고리즘 인터뷰 책을 참고하여 작성하였다. 이전 내용은 아래의 링크를 참고하자 문자열 유형 기초 정리_1 유형 4. 특정 단어 추출 > 이 유형은 NLP에서도 자주 사용되는 스킬이다. paragraph = "Bob hit a ball, the hit BALL flew far after it was hit" 위의 예제에서 "hit"을 제외한 단어 중 가장 많이 등장하는 단어를 뽑는 코드를 작성하자. 대소문자는 구분하지 않고 구두점은 무시한다. 1단계 정규식을 사용해서 불필요한 구두점을 지우자 import re re.sub('[^\w]', ' ', paragraph) [^\w] 은 모든 문자와 숫자를 제외하고는 공백으로 바꾼다. 2단계 정규식에 추가적으로 처리를 해보자. banned =..

python의 꽃. DFS의 필수 개념인 재귀 함수에 대해 알아보자. 왜 재귀 함수를 알아야 할까? 미로 찾기 문제를 생각해보자. 미로를 찾기 하기 위해서는 매 순간 갈림길에서 선택을 해야 하는 순간이 생긴다. 갈림길에서 한 선택의 결과가 막힌 길이라면, 그 즉시 갈림길이 있었던 위치로 순간 이동하는 것을 가능하게 해주는 것이 재귀 함수다. 0. 기본 모양 재귀 함수란 호출한 함수 안에서 그 함수를 다시 호출(recursive call)함으로 반복하는 것을 의미한다. 쉽게 말하면 def를 통해 함수를 만든다. 그리고 만든 함수 안에서 다시 그 함수를 호출하는 것을 의미한다. 아래의 예를 참고하자. def recursive_call(x): print(x) recursive_call(x+1) recursiv..

아래의 내용은 파이썬 알고리즘 인터뷰 책을 참고하여 작성하였다. 코딩 테스트에서 점수를 받으려면, 주어진 문제를 에러 없이 주어진 시간 안에 정해진 정답을 출력해야 한다. 따라서 우리가 집중을 해야 할 부분은 첫째, 정답을 도출해 낼 수 있는 알고리즘을 짜야한다. 둘째, 주어진 시간 안에 코딩 정답을 도출해야 한다. 이러한 2가지 포인트에 집중하여, 아래의 글을 읽어주기 바란다. 문자열 유형 코딩 테스트에서 주로 1번 문제로 등장하는 문자열에 대해 정리해보고자 한다. 아래의 유형이 나오면 5분 안에 풀고 넘어가면 된다. 물론 아래의 유형으로 문자열을 요구사항에 맞게 정렬 후 다른 유형과 결합되어 나오기도 한다. 유형 1. 회문(Palindrome) 회문, 즉 팰린드롬이란 앞뒤가 똑같은 단어나 문장을 의미..