Dev

[알고리즘] 정렬의 정의와 분류

정렬의 정의 2개 이상의 자료를 오름차순(ascending)이나 내림차순(descending)으로 재배열하는 것 정렬 방법의 분류 1. 실행 방법에 따른 분류 (1) 비교식 정렬 (Comparative Sort) 비교하고자 하는 각 키 값들을 한 번에 두 개씩 비교하여 교환하는 방식 (2) 분산식 정렬 (Distribute Sort) 키 값을 기준으로 자료를 여러 개의 부분 집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식. ※ 여기서 키(key)란, 자료를 정렬하는 데 사용하는 기준이 되는 특정 값을 의미. 2. 정렬 장소에 따른 분류 (1) 내부 정렬 (Internal Sort) - 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식 - 정렬 속도가 빠르지만 메모리 용량의 제한을 받음..

[자료구조][파이썬/Python] 큐(Queue)

큐(Queue) 큐(Queue)는 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다. 기본적으로 값을 저장하는 연산 enqueue와 저장된 값을 꺼내는 연산 dequeue가 제공되어야 한다. 부가적으로 큐의 길이를 반환하는 연산이나 큐가 비어있는지 확인하는 연산, 큐의 가장 아래에 있는 값이 무엇인지 확인하는 연산을 추가할 수도 있다. 가장 먼저 들어간 값이 가장 먼저 나오게 되는 원칙(First In First Out, FIFO)을 따른다. 클래스로 구현하기 & 리스트 메서드 활용하기 스택과 큐는 매우 유사한 형태이고 따르고 있는 원칙만 약간 달라 설명도, 특징도, 구현하는 방식도 유사한 점이 많다. 그래서 큐도 마찬가지로 클래스로 구현하는 일반적인 방법은 (1) 양방향 연결리스트(Do..

[자료구조][파이썬/Python] 스택(Stack)

스택(Stack) 스택(Stack)은 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다. 기본적으로 값을 저장하는 연산 push와 저장된 값을 꺼내는 연산 pop이 제공되어야 한다. 부가적으로 스택의 길이를 반환하는 연산이나 스택이 비어있는지 확인하는 연산, 스택의 가장 위에 있는 값이 무엇인지 확인하는 연산을 추가할 수도 있다. 가장 나중에 들어간 값이 가장 먼저 나오게 되는 원칙(Last In First Out, LIFO)을 따른다. 클래스로 구현하기 일반적으로 클래스로 구현하는 방법은 (1) 양방향 연결리스트(Doubly Linked List)를 통해 구현하는 방법, (2) Python 내 리스트 메서드로 구현하는 방법이 존재한다. 다만, 실제로 코딩테스트 문제를 풀 때 어떻게 빠르..

[파이썬/Python] for - else / while - else 활용

반복문 (for / while) - else 문 개념 파이썬에서는 다른 프로그래밍 언어와 다르게 반복문 for과 while문에 else를 같은 indentation에 놓을 수 있다. 그 else의 기능은 무엇일까? 반복문 도중 break가 되지 않고 끝까지 반복을 실행했을 경우 else에 있는 코드를 실행하게끔 하는 것이다. 코드를 통해 바로 알아보자. 코드 예시 (1) 간단한 예시 특정 요소가 리스트 안에 있는지 없는지 확인하고 싶다고 해보자. for-else 문을 이용하면 다음과 같이 깔끔하게 코드를 짤 수 있다. bucket = ['딸기', '당근', '수박', '참외', '메론'] for fruit in bucket: if fruit == '딸기': print('딸기가 바구니에 있습니다!') br..

[파이썬/Python] 리스트의 정렬 방법 - sort함수와 sorted함수

리스트의 정렬 프로그래밍 언어에서 리스트 혹은 배열을 정렬하는 알고리즘은 다양하다. 가장 간단한 선택 정렬, 버블 정렬부터 삽입 정렬, 쉘 정렬, 병합 정렬, 퀵 정렬 등의 효율성을 높인 알고리즘들이 존재하고 특별한 형태로 기수 정렬이나 트리 정렬 등의 알고리즘도 존재한다. 하지만 이런 내용들은 알고리즘과 관련된 포스팅할 때 더욱 자세히 하도록 하고, 오늘은 파이썬 내장함수를 이용한 정렬 방법을 정리해보려고 한다. 파이썬에서 리스트를 정렬하는 내장 함수는 대표적으로sort와sorted가 존재한다. 기본적인 함수의 사용 방법과 활용 예시를 살펴보고, 두 함수의 차이를 비교하여 두 함수를 어떻게 하면 더욱 효율적으로 사용할 수 있는지 파악해보자. sort와 sorted 함수 (1) sort 함수의 기본 형태..

[파이썬/Python] 순열과 조합 (Permutation and Combination)

순열과 조합 순열 (Permutation) 순열이란 서로 다른 n개에서 r개를 선택할 때 순서를 고려하여 선택한 경우의 수를 나열하는 방법이다. 보통 Permutation의 첫 글자 P를 따서 nPr로 표현하며 계산식은 아래와 같이 쓸 수 있다. 0 ≦ r ≦ n nPr = n x (n-1) x (n-2) x (n-3) x …… x (n-r+1) ※ n부터 (n-r+1)까지 곱해지는 수는 총 r개 nPr = n! / (n-r)! 가령, 알파벳이 써져 있는 카드 4개가 있다고 해보자. 각 카드에는 A, B, C, D가 써져 있는데 이 중에서 순서를 고려하여 2장을 뽑고 싶다고 하자. 공식에 따르면 4P2 = 4 x 3 = 12 혹은 4P2 = 4! / (4-2)! = 4 x 3 x 2 x 1 / 2 x 1..

[파이썬/Python] 재귀함수(Recursive function)와 메모이제이션(Memoization)

재귀함수(recursive function)란 함수 내부에서 자기 자신(함수)을 다시 호출하는 함수이다. 잘만 활용하면 참 좋다고 생각하는데, 가장 중요한 탈출 조건을 생각해내는 것이 상당히 까다로운 편이라 권장되지는 않고 있다. 또한, 재귀함수만 이용할 경우 과도하게 스택메모리를 이용하게 되고 탈출 조건을 잘못 세울 경우 스택오버플로우 에러가 발생할 위험도 존재한다. 그래서 동적 프로그래밍(Dynamic Progrmming)처럼 재귀함수의 각 단계 결과값을 저장하여 성능을 높여주는 방법도 존재한다. 우선 재귀함수의 예시를 두 개 들어보자. 1. 팩토리얼 구하기 일반적인 for문을 이용하여 팩토리얼을 구하면 다음과 같은 코드를 짤 수 있다. def factorial_for(n): if n == 0 or ..

[파이썬/Python] 리스트 안에서 반복문, Comprehension

요즘 틈 나는 대로 프로그래머스의 코딩 테스트 문제를 풀고 있다. 지금 Python으로 풀 수 있는 Level 1 문제들은 세 문제만을 남겨두고 있으며, 슬슬 Level 2 문제들도 풀어나가고 있다. 코드 정리는 귀찮아서 못하고 있는데 일단 Git에만 푸쉬해두고 있는 상태다. (Git에도 사실 다 푸쉬는 못했다..ㅎ) 아 글은 언제 쓰냐아으ㅏ으아아ㅏㅏ 귀찮다. 아직 저레벨 수준의 코딩 테스트 문제들이었지만, 문제를 풀어나가며 유용했던 함수 및 메소드를 정리해볼까 한다. 오늘은 그 첫 번째 순서로 Python에서 아주 유용한 comprehension이다. Comprehension Comprehension이란, iterable한 객체를 생성하는 방법 중 하나로 아주 유용하게 쓰고 있다. 나는 list랑 di..