카운팅 정렬, 혹은 계수 정렬은 O(n + k)의 시간복잡도를 가진 정렬이다. 여기서 다소 낯선 k는 정렬을 수행할 배열의 가장 큰 값을 의미한다. k가 단순히 상수로 취급되어 생략되지 않고 남아있는 것은 그만큼 k에 따라 수행시간에 영향을 미치기 때문이다. 만약 k가 n보다 작다면 정렬의 수행시간은 O(n)이 되겠지만, 무한대로 크다면 정렬의 수행시간도 무한대가 된다. 작동 방식 1. 배열을 이용한 방식 계수 정렬은 counting이라는 말 답게 배열에 존재하는 수의 개수를 세어주고, 이 정보를 바탕으로 정렬을 수행한다. 그리고 여기서 수와 수의 개수는 배열 혹은 딕셔너리의 인덱스와 해당 값을 통해서 기록할 수 있다. 먼저 배열을 통한 계수 정렬은 누적합의 개념을 적용하여 구현할 수 있다. 배열을 이용..
파이썬
매직 메소드 (Magic Method)란? 매직 메소드 혹은 스페셜 메소드라고 불리며, 메소드의 양쪽을 두 개의 언더스코어(__)로 감싼 메소드를 말한다. 일반적으로 파이썬의 클래스 내에 내부적으로 구현되어 있다. 매직 메소드를 적절히 사용하면 클래스를 보다 폭넓게 사용할 수 있고, 사용자가 직접 만든 클래스를 마치 파이썬의 내장 클래스처럼 사용할 수 있다. 아마 파이썬을 사용하며 가장 처음 접하거나 구현하는 매직 메소드는 __init__() 혹은 __str__() 일 것이다. __init__() 해당 메소드는 파이썬 클래스의 인스턴스를 생성할 때 자동으로 호출되며, 일반적으로 인스턴스 생성과 함께 인스턴스 변수를 선언하기 위해 사용된다. class Person: def __init__(self): pr..
아스키코드란? 미국정보교환표준부호(영어: American Standard Code for Information Interchange), 또는 줄여서 ASCII( /ˈæski/, 아스키)는 영문 알파벳을 사용하는 대표적인 문자 인코딩이다. 아스키는 컴퓨터와 통신 장비를 비롯한 문자를 사용하는 많은 장치에서 사용되며, 대부분의 문자 인코딩이 아스키에 기초를 두고 있다. - 위키백과 쉽게 말해 아스키코드는 알파벳을 비롯한 문자들을 통신하기 위해 일대일 대응시켜 숫자로 정해둔 코드이다. 아스키코드 테이블은 다음과 같다. 물론 이 표를 다 외우고 있을 필요는 없다. 파이썬에서는 ord()와 chr() 함수를 통해 문자를 아스키코드로, 아스키코드를 문자로 변환할 수 있다. print(ord("A")) print(o..
In CPython, the global interpreter lock or GIL is a mutex that protects access to Python objects, preventing multiple threads from executing Python bytecodes at once. The GIL prevents race conditions and ensures thread safety. CPython에서 global intertreter lock(GIL)은 멀티 스레드가 파이썬 바이트코드들을 동시에 실행시키는 것을 막으며 파이썬 object에 대한 접근을 보호하는 뮤택스이다. GIL은 경쟁상태(race condition)을 예방하고 thread-safety를 보장한다. https://wi..
문제 (링크) https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline seq_1 = input().rstrip() seq_2 = input().rstrip() seq_3 = input().rstrip() x = len(seq_1) y = len(seq_2) z = len(seq_3) arr = [[[0] * (z+1) for _ in range(y+1)] for _ in range(x+1..
파이썬의 heapq 라이브러리를 통해 손 쉽게 최소힙과 최대힙을 구현할 수 있다. 우선, heapq는 기본적으로 최소힙으로 구현되어있다. 즉, heapq의 heappush를 통해 값들을 삽입하면 해당 값들은 숫자가 가장 작은 순서대로 트리 구조로 값이 저장된다. heapq의 연산을 사용하기 위해선 각 연산의 파라미터로 큐로 사용할 리스트와 원소를 넘겨주면 된다. 1. heappush - 값 추가 import heapq heap_q = [] heapq.heappush(heap_q, 3) heapq.heappush(heap_q, 10) heapq.heappush(heap_q, 1) heapq.heappush(heap_q, 0) heapq.heappush(heap_q, 4) print(heap_q) # [0,..
파이썬은 집합(고등수학에서 배우는 그 집합)을 처리하기 위한 자료형 set을 제공한다. 집합 자료형은 set()으로 선언하며, 안에 들어갈 원소들을 리스트 형태로 넘겨주면 된다. data = set([1, 4, 9, 11, 3]) print(data) # {1, 3, 4, 9, 11} 집합 자료형의 특징은 크게 두 가지가 있다. 중복값을 허용하지 않는다. 원소들 간 순서가 정해져있지 않다. 중복값을 허용하지 않기 때문에 동일한 값의 원소를 여러 개 넣더라도 집합 안에는 하나의 원소만 남게된다. data = set([1, 4, 4, 4, 9, 11, 3]) print(data) # {1, 3, 4, 9, 11} 순서를 갖지 않기 때문에 리스트처럼 인덱싱하는 것이 불가하다. data = set([1, 4, ..
문제 (링크) https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 나의 풀이 n = int(input()) schedule = [] for _ in range(n): schedule.append(list(map(int, input().split()))) schedule = sorted(schedule, key= lambda x: x[0]) schedule = sorted(schedule, key= lambda x: x[1]) ans = 1 end_time = schedule[0][1] for i in range(1, n): if end_time
