컴공생의 개인공부일지

데크 더블 엔디드 큐의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다. 스택과 큐의 특징 모두 가지고 있으며 이중 연결 리스트로 구현하는 편이 가장 잘 어울린다. 이중 연결 리스트로 구성시 양쪽으로 head, tail 포인터를 갖고 있다가 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결시켜 준다. 파이썬의 경우, 데크 자료형을 collections 모듈에서 deque라는 이름으로 지원한다. import collections a = collections.deque() type(a) # # collection.deque도 이중 연결 리스트로 구현되어 있다 우선순위 큐 큐 또는 스택과 유사하지만 추가로 각 요소의 우선순위와 연관되어 있다. 어떠한 특정 ..

스택 다음과 같이 2가지 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형이다(LIFO 형태) push() : 요소에 컬렉션을 추가한다. pop() : 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거한다. 거의 모든 애플리케이션을 만들 때 사용되는 자료구조, 컴퓨터 서브루틴에 대한 정보를 저장하는 자료구조 연결 리스트를 이용한 스택 ADT 구현 다음 그림은 스택 추상 자료형을 연결 리스트로 구현한 것이다. ADT는 스택의 연산을 지원하기 위해 1~5까지 각 요소를 쌓겠지만 실제로 연결 리스트로 구현하게 되면 물리 메모리 상에는 순서 관계없이 무작위로 배치되고 포인터로 가리키게 된다. 다음과 같이 연결 리스트를 담을 Node 클래스부터 정의한다. class Node: def __init__(sel..

연결 리스트 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적 순서대로 저장되지 않는 것을 말한다. 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형(ADT) 구현의 기반이 된다. 새로운 노드를 삽입, 삭제가 편리하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리하기 편하다. 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러 가지 방법으로 다양하게 활용이 가능하다. 탐색에는 O(n)이 소요되고 추가, 삭제, 추출 작업에는 O(1) 소요 런너 기법 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법이다. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나, 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. 다음과 같이 빠른 런..

배열 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다. 어느 위치에서나 O(1)에 조회가 가능하다는 장점이 있다. 자료구조는 크게 메모리 공간 기반의 연속 방식, 포인터 기반의 연결 방식으로 나뉜다. 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다. 연결 방식의 기본이 되는 자료형은 연결 리스트이다. 추상 자료형(ADT)의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으로 한다. Ex.) 스택을 연결 리스트로 구현, 큐는 배열로 구현 파이썬에서는 정적 배열 x, 동적 배열인 리스트만 제공된다. 동적 배열의 원리 : 초깃값을 작게 잡아 배열생성 -> 데이터 추가되면서 채워지면 늘려지고 복사하는 방식(더블링이라고함) 이러한 재할당 비율을 그로스 팩터(G..

문자열 슬라이싱 문자열 슬라이싱은 편리한 기능 제공과 동시에 내부에서 매우 빠르게 수행된다. 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아낸다. 문자열을 별도로 리스트로 매핑하는 등의 처리는 데이터 구조에는 좋은 방법이지만, 별도 자료형으로 매핑하는 과정에서 상당한 연산 비용이 필요하므로 전체적인 속도에서 손해를 보게 된다. 알고리즘 실행 시간 슬라이싱을 1로 했을 때의 비율 슬라이싱 0.499μs 1 리스트 reverse() 2.46μs 5 reversed() + join() 2.49μs 6 for 반복 5.5μs 12 while 반복 9.4μs 21 재귀 24.3μs 24 슬라이싱을 기준으로 한 파이썬 문자열 처리 실행시간(μs는 마이크로 초를 의..

리스트 언어 동적배열 파이썬 list() C++ std::vector 자바 ArrayList 순서대로 저장하는 시퀀스이자 변경 가능한 목록, 입력 순서가 유지되며 내부적으로 동적 배열로 구현되어 있다. 파이썬 리스트는 다양한 기능 제공하고 O(1)에 실행 가능한 연산들도 몇 가지 있다. 리스트 마지막에 요소를 .append()로 추가, pop()으로 추출, 인덱스의 요소 조회는 모두 O(1)이다. 다음 표는 리스트의 주요 연산 및 시간 복잡도이다. 연산 시간 복잡도 설명 len(a) O(1) 전체 요소 개수 리턴한다 a[i] O(1) 인덱스의 i 요소를 가져온다 a[i:j] O(K) i부터 j까지 슬라이스 길이만큼의 k개 요소를 가져온다 elem in a O(n) elem 요소가 존재하는지 확인, 처음부..

매핑 키와 자료형으로 구성된 복합 자료형(파이썬에 내장된 유일한 매핑 자료형은 딕셔너리) 집합 set이라고 쓰고 중복된 값을 갖지 않는 자료형 딕셔너리와의 차이점은 딕셔너리는 키/값 형태이지만 집합은 값만 선언한다 입력 순서가 유지되지 않으며, 중복된 값이 있을 경우 하나의 값만 유지한다 시퀀스 특정 대상의 순서 있는 나열 파이썬에서는 list라는 시퀀스 타입이 배열의 역할을 수행한다 불변, 가변으로 구분 가능하고 불변은 값 변경이 X(str, tuple, bytes) 원시타입 C나 자바 같은 프로그래밍 언어는 기본적으로 원시 타입을 제공하지만 파이썬의 경우 제공하지 않는다. 원시 타입은 메모리에 정확하게 타입 크기만큼의 공간을 할당하고 그 공간으로 값으로 채워넣는다. 원시 타입을 제공함으로써 C나 자바..

1. 파이썬의 변수명 네이밍 컨벤션은 스네이크 케이스를 따른다. Ex.) snake_case : int = 1 2. 타입 힌트, 리턴값 등 명시적으로 선언 시 가독성이 좋아지고 버그 발생 확률을 줄일 수 있다. 또한 mypy를 사용해서 타입 힌트에 오류가 없는지 확인 가능하다. Ex.) def fn(a : int) -> bool: $pip install mypy를 통해 설치 가능 3. 리스트 컴프리헨션 Ex.) 홀수인 경우 2를 곱해 출력하는 리스트 컴프리헨션 [n * 2 for n in range(1, 10 + 1) if n % 2 == 1] 4. 제네레이터 루프의 반복 동작을 제어할 수 있는 루틴의 형태 yield 구문 사용 시 제네레이터 리턴 생성해두고 필요할 때 언제든지 숫자를 만들어 낼 수 있음..

문제: 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표) 또한 무시한다. 예제: Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"] Output: "ball" Explanation: "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. Note that words in the paragraph are not..

문제: 로그를 재정렬하라 . 기준은 다음과 같다 1. 로그의 가장 앞 부분은 식별자 2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다. 3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일한 경우 식별자 순으로 한다. 4. 숫자 로그는 입력 순서대로 한다. 예제: Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"] Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"] Explanation: The letter-log contents are all different, so their orde..