문돌이 Theo

퀵 정렬 (Quick Sort) 주어진 배열을 두 개로 분할하고, 각각을 정렬 그럼 병합 정렬과 동일한 것이 아닌가? 차이점 1 : 병합 정렬은 그냥 두 부분으로 나누는 반면, 퀵 정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치 차이점 2 : 각 부분 정렬이 끝난 후, 병합 정렬은 "병합"이란 후처리 작업이 필요하나, 퀵 정렬은 필요 없음 퀵 정렬 과정 알고리즘 def quick_sort(a, low, high):# (리스트, 시작 인덱스, 끝 인덱스) if low < high: pivot = partition(a,low,high) quick_sort(a, low, pivot-1) quick_sort(a, pivot+1, high) Hoar..

병합 정렬 (Merge Sort) 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘 활용 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄 top-down 방식 시간 복잡도 : O(n log n) 병합 정렬 과정 [69, 10, 30, 2, 16, 8, 31, 22] 를 병합 정렬하는 과정 분할 단계 : 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 분할 작업을 진행 병합 단계 : 2개의 부분집합을 정렬하면서 하나의 집합으로 병합 8개의 부분집합이 1개로 병합될 때까지 반복 분할 과정 def merge_sort(arr): # 리스트 길이가 1이면 최소 단위이므로 종료 if len(arr) == 1: return ar..

n진수 2진수, 8진수, 10진수, 16진수 10진수를 n진수로 변환 원하는 타진법의 수로 나눈 뒤 나머지를 거꾸로 읽는다. 예시 (149)_10 = (10010101)_2= (95)16 = (225)_8 n진수를 10진수로 변환 (135)_8 = 1 * 8^2 + 3 * 8^1 + 5 * 8^0 = (93)_10 소수점이 있을 때 (135.12)_8 = 1 * 8^2 + 3 * 8^1 + 5 * 8^0 + 1 * 8^(-1) + 2 * 8^(-2) = (93.15625)_10 n진수간 변환 음의 정수 표현 1의 보수 부호와 절대값으로 표현된 값을 부호 비트를 제외한 나머지비트들을 0은 1로, 1은 0으로 변환한다. -6 = 1000000000000110 : 부호와 절대값 표현 -6 = 111111111..

비트 연산 비트 연산자 연산자연산자의 기능 &비트단위로 AND 연산 진행|비트단위로 OR 연산 진행^비트단위로 XOR 연산 진행 (같으면 0 다르면 1)~단항 연산자로서 피연산자의 모든 비트를 반전피연산자의 비트 열을 오른쪽으로 이동 1 &#39;, end=&#39;&#39;) a ^= key Bbit_print(a) # => a^=key ==> 00101100 print(&#39;a^=key ==> &#39;, end=&#39;&#39;) a ^= key Bbit_print(a) # => a^=key ==> 10000110 엔디안 컴퓨터의 메모리와 같은 1차원 공간에 여러 개의 연속된 대상을 배열하는 방법을 의미하며 hw 아키텍처마다 다르다. 주의 : 속도 향상을 위해 바이트 단위와 워드 단위를 변환하..

복잡도 분석 알고리즘의 효율 공간적 효율성과 시간적 효율성 공간적 효율성 : 연산량 대비 얼마나 적은 메모리 공간을 요하는 가 시간적 효율성 : 연산량 대비 얼마나 적은 시간을 요하는 가 효율성을 뒤집어 표현하면 복잡도(Complexity) 복잡도가 높을수록 효율성은 저하 시간적 복잡도 분석 하드웨어 환경에 따라 처리시간이 상이 부동소수 처리 프로세서 존재유므, 나눗셈 가속기능 유무 입출력 장비의 성능, 공유 여부 소프트웨어 환경에 따라 처리시간이 상이 프로그램 언어의 종류 운영체제, 컴파일러의 종류 이러한 환경적 차이로 인해 분석이 난해 복잡도의 점근적 표기 시간 복잡도는 입력 크기에 대한 함수로 표기, 이 함수는 주로 여러개의 항을 가지는 다항식 이를 단순한 함수로 표현하기 위해 점근적 표기(Asym..

OOP OOP 객체(Object) 객체지향프로그래밍(Object Oriented Programming) 클래스(Class)와 객체(Object) 1. 객체 Python에서 모든 것은 객체(object)이다. 모든 객체는 타입(type), 속성(attribute), 조작법(method)을 가진다. typeinstance int0, 1, 2str&#39;&#39;, &#39;hello&#39;, &#39;123&#39;list[], [&#39;a&#39;, &#39;b&#39;]dict{}, {&#39;key&#39;: &#39;value&#39;} 타입 : 공통된 속성(attribute)과 조작법(method)을 가진 객체들의 분류 인스턴스 : 특정 타입(type)의 실제 데이터 예시(instance)이다..

모듈 & 패키지 1. 모듈(Module) 파일 단위의 코드 재사용 모듈(Module) 패키지(Package) 라이브러리(Library) 용어 정의 모듈 특정 기능을 .py 파일 단위로 작성한 것. 패키지 특정 기능과 관련된 여러 모듈들의 집합. 패키지 안에는 또다른 서브 패키지를 포함 할수도 있음. 파이썬 표준 라이브러리 파이썬에 기본적으로 설치된 모듈과 내장 함수를 묶어서 파이썬 표준 라이브러리 (Python Standard Library, PSL) 라 불림. 패키지 관리자(pip) PyPI 에 저장된 외부 패키지들을 설치하도록 도와주는 패키지. 1.1 모듈(Module)? 모듈(module)은 특정 기능을 하는 코드를 담고 있는 파일(또는 스크립트)입니다. 1.2 모듈 생성 jupyter notebo..

1. 문자열 변경할 수 없고(immutable), 순서가 있고(ordered), 순회 가능한(iterable) 매서드출력 .find(x)x의 위치를 반환, 없으면 -1.index(x)x의 위치를 반환, 없으면 오류.replace(old, new[, count])old를 new로 변경( 해당하는 갯수만큼).strip([chars])특정한 문자들을 지정하면, 양쪽을 제거하거나 왼쪽을 제거하거나(lstrip), 오른쪽을 제거합니다(rstrip).지정하지 않으면 공백을 제거합니다..split()문자열을 특정한 단위로 나누어 리스트로 반환합니다. 디폴트는 공백‘separator’.join(iterable)iterable 요소들을 separator를 구분자로 합쳐 문자열로 반환합니다..capitalize()맨 앞만..

트리 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가며 확장되는 트리(나무)모양의 구조 정의 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족 노드 중 최상의 노드는 루트(root) 나머지 노드들은 n(>=0)개의 분리 집합 T1, ... , TN으로 분리 가능 이들 T1, ... , TN은 각각 하나의 트리로 간주 가능하며(재귀적 정의) 루트의 부 트리(subtree)라고 함 용어 설명 노드(node) - 트리의 원소 트리 T의 노드 - A, B, C, D, E, F, G, H, I, J, K 간선(edge) - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드(root node) - ..

예외처리 1. 에러(Error) 발생할 수 있는 에러의 종류를 확인해봅시다. 1.1 문법 에러(Syntax Error) 문법 에러가 있는 프로그램은 실행되지 않습니다. 에러 발생 시 SyntaxError라는 키워드와 함께, 에러의 상세 내용을 보여줍니다. 파일이름과 줄번호, ^ 문자를 통해 파이썬이 코드를 읽어 들일 때(parser) 문제가 발생한 위치를 표현합니다. parser 는 줄에서 에러가 감지된 가장 앞의 위치를 가리키는 작은 ’화살표(^)’를 표시합니다. if True: print(&#39;참&#39;) else print(&#39;거짓&#39;) File "", line 3 else ^ SyntaxError: invalid syntax print(&#39;hi) File "", line 1 ..