취미와 밥줄사이

공간 복잡도 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현할 수 있다. 시간 복잡도: 얼마나 빠르게 실행되는지 공간 복잡도: 얼마나 많은 저장 공간이 필요하는지 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이다. 시간과 공간은 반비례적인 경향이 있다. 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함 총 필요 저장 공간 고정 공간(알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수(일정한 양의 메모리 공간) 가변 공간(알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간 입력값의 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 의미 S(P) = c + Sp(n) c: 고정공간 Sp(n)SP(n): 가변 공간 고정 공간은 상수이므로 공간 복잡도는 ..

트리(Tree)란 트리는 노드로 이루어진 자료구조 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖는다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 수 없다. 노드들은 특정 순서로 나열될 수 도 있고 그럴 수 없을 수도 있다. 각 노드는 부모 노드로의 연결이 있을 수도 있고, 없을 수도 있다. 각 노드는 어떤 자료형으로 표현 가능하다. 비선형 자로구조로 계층적 관계를 표현한다. Ex) 디렉터리 구조, 조직도 그래프의 한 종류 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) DAG(Directed Ac..

배열(Array)이란? 배열은 메모리 상에 데이터(원소)를 연속하게 배치한 자료구조 배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조 연속적인 메모리 공간에 순차적으로 데이터를 저장 배열은 선언할 때 크기를 정하면, 그 크기로 고정이 된다. 선언된 값은 다시 배열을 선언하지 않으면 변경할 수 없다. 배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가지고 있따. 배열의 자료형이 int라면, 배열 한 칸의 크기는 int(4byte)가 되는 것이다. 배열은 인덱스를 통해서 배열에 있는 요소에 접근할 수 있다. 배열의 특징 추가적으로 소모되는 메모리 양(=overhead)가 거의 없다 Cache hit rate가 높다. cache hit ratio: 적중률 = (캐시히트 횟수)/(전체 참조횟수..

선형 검색(Linear Search) 순차 검색(Sequential Search)이라고도 한다. 데이터가 모인 집합(배열, lined List)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘 데이터를 정렬할 필요가 없음 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있음 10개의 데이터가 있을 경우 마지막에 있는 데이터를 찾는 경우 10번의 비교가 필요하지만 100만개의 데이터가 있는경우 100만번의 비교가 필요함 선형검색은 linked list에서 자주 쓰임 def linear_search(sequence, key): for i in range(len(sequence)): if sequence[i] == ..

이터레이터(Iterator)란? 순서대로 다음 값을 리턴할 수 있는 객체 iterator 객체 - 값을 차례대로 꺼낼 수 있는 객체 이터레이터 사용이유 값이 필요한 시점이 되었을 때 값을 만들기 위해서 데이터 생성을 뒤로 미루기 위함(lazy evaluation) # 반복 가능한 객체인지 확인하는 방법 # iter함수의 존재 여부로 반복가능한 객체인지 확인할 수 있음 li = [1, 2, 3] print(dir(li)) # `__iter__`가 있는지 확인하기 컬렉션 타입(Collection Type) List, Tuple, Set, Dictionary와 같이 여러 개의 요소(object)를 갖는 데이터 타입 시퀀스 타입(Sequence Type) List, Tuple, Range, Str 등과 같이 순..

type check 파이썬은 동적 프로그래밍 언어 dynatic typing language 실행하는 시점에서 변수의 타입을 고려하지 않음 변수 type을 신경쓰지 않고 코딩이 가능함 애플리케이션 규모가 커지게 되면 파이썬의 다이나믹함이 치명적인 버그로 이어질 확률이 높아짐 type annotation은 파이썬 코드에 타입을 명시하기 위한 표준을 정리하기 위한 것 python 3.5에서 추가됨 Type Annotation 문법이 추가됨 def add (a: int, b: int) -> int: return a + b 표준에 따라 변수나 함수에 타입을 명시된 파이썬 코드는 정적 타입 검사기(static type checker)를 통해 코드를 실행하지 않고토 타입 에러를 찾을 수 있음 mypy # mypy ..

Python 정적분석 정적 코드 분석이란 프로그램을 실행하지 않고 프로그램 문법 상의 오류나 코딩 규약 위반 등을 분석하는 행위 프로그램을 실행하기 전 정적 분석을 실행함으로써 오류를 사전에 제거하고 가독성을 향상 pyflake8으로 실시간으로 코드를 생성하면서 PEP 8 가이드라인과 다른 부분을 확인가능 flake8 파이썬의 문법 및 코드 스타일을 검사해주는 패키지 기본적으로 PEP8(Python Enhace Proposal 8) 스타일 가이드로 검사 원하는 부분만 설정하여 검사 가능 스타일을 통일해야하는 이유 작성한 코드는 본인 뿐만 아니라 다른 사람들도 함께 보게 됨 모두 같은 코드 스타일을 따를 경우 훨씬 편하게 코드를 보고 읽을 수 있음 VScode에서 flake8 사용하기 # flake8 설치..

문제 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 개를 칠판에 써주었다. 그 다음에 크기가 큰 수를 말해보라고 했다. 상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다. 두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 칠판에 적은 두 수 A와 B가 주어진다. 두 수는 같지 않은 세 자리 수이며, 0이 포함되어 있지 않다. 출력 첫째 줄에 상수의 대답을 출력한다. 예..