Python

[알고리즘][파이썬/Python] 선택 정렬 (Selection Sort)

정의 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식의 정렬 알고리즘 동작 방식 1. 반복 시작 시, 시작 index를 최소값의 index로 지정 2. 시작 위치 이후에 있는 모든 원소를 한 번씩 방문하며 최소값과 비교 3. 더 작은 값이 발견될 경우, 해당 값의 index를 최소값의 index로 업데이트 4. 반복이 끝난 후 시작 index와 최소값 index가 다를 경우, 두 index에 위치한 원소들을 교환 5. 위 과정을 반복하면서 정렬 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우 - 비교횟수 : 처음 비교할 때 (n-1)회, 두 번째 비교할 때 (n-2)회, ..., i..

[알고리즘][파이썬/Python] 버블 정렬 (Bubble Sort)

정의 차례로 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식의 정렬 알고리즘 동작 방식 1. 배열(혹은 리스트)의 첫 번째 원소부터 마지막 원소까지 인접 원소 간 대소 비교를 반복하는데, 더 큰 값을 가진 원소가 왼쪽에 있다면 서로 자리를 바꿈 (swap) 2. 위 과정을 반복하여 한 단계가 끝나면 가장 큰 값을 가진 원소가 배열 (혹은 리스트)의 마지막 자리로 정렬되어 있음 3. 한 단계가 끝날 때마다 맨 끝에 위치한 원소는 정렬된 상태이므로 다음 단계에서는 정렬된 원소를 제외하고 대소 비교를 실행 메모리 사용 공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우 - 비교횟수 : i번째 실행 시 (n-i) 번 비교하므로..

[프로그래머스][파이썬/Python] 소수 찾기 - level 2

* 프로그래머스에는 '소수 찾기'라는 문제가 level 1과 level 2에 모두 존재한다. 구분하고자 level 2를 제목에 명시했다. 문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한 조건 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 입출력 예 제출 코드 from itertools import permu..

[자료구조][파이썬/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] 리스트의 정렬 방법 - 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] (2019 카카오 코딩테스트) 오픈채팅방

문제 설명 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 예를 들어, 채팅방..