유진's 공부로그

스택(Stack) 스택은 후입선출(LIFO)로 처리되는 자료구조이다. 즉, 스택에 가장 마지막에 들어간 요소가 가장 처음으로 꺼내진다. Stack은 무엇인가가 쌓여있는 걸 지칭한다는 점을 생각해보면 가장 마지막에 쌓여진 것이 가장 처음으로 꺼내진다는 것의 개념은 쉽게 이해될 것이다. 스택은 흔히 연결리스트로 구현된다. 이 경우에 스택 선언을 위해 메모리 내의 연속된 공간을 할당할 필요가 없어지며, 실제로 스택 내의 요소 간 순서가 메모리 내의 물리적 순서와는 무관하게 될 것이다. 그러나 파이썬에서는 리스트가 스택으로 충분히 기능할 수 있기 때문에 연결리스트로 스택을 구현하지 않아도 된다. 스택의 주 연산은 삽입(push)와 제거(pop)이다. 삽입은 스택의 가장 마지막 자리에 요소가 추가되는 것이고, 제..

트라이 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 혹은 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조. 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 주로 문자열이 키인 경우가 많고, 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 트라이는 트리와 유사하지만, 우리가 주로 살펴본 이진 트리의 모습이 아닌 전형적인 다진 트리(m-ary Tree)의 형태를 띤다. 도식을 참고하면, 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. (이 부분은 어떻게 구현하냐의 차이인 것 ..

본 포스트는 "파이썬 머신러닝 완벽가이드" 책을 공부하고 정리한 글입니다. 아나콘다 환경을 설치한다면 사이킷런은 별도로 설치할 필요가 없기 때문에 colab 환경에서 실습을 진행하는 본 포스트에서는 별도의 패키지 설치는 하지 않겠습니다. 실습 colab notebook: colab.research.google.com/drive/1fDmXFwxTpDEGEbBA6Cu4T6QFbXz4UfSC?usp=sharing 1. 사이킷런 기본 모듈 설명 - sklearn.datasets: 사이킷런에서 자체적으로 제공하는 데이터셋을 생성하는 모듈 → 솔직히 실습용 데이터셋 수준이기 때문에 많이 쓰이지는 않습니다. iris 등의 데이터셋이 있습니다. - sklearn.tree: 트리 기반의 ML 알고리즘을 구현한 클래스를 ..

런너(Runner) 기법 연결 리스트 순회 시 2개의 포인터를 동시에 사용하는 기법. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. 연결리스트의 경우 중간 위치나 길이를 파악하는 데에 배열에 비해 상대적으로 복잡하다. (전체를 다 탐색해야 하므로 O(n)의 시간이 소요됨) 따라서 fast runner와 slow runner 간의 step을 2배 차이를 두는 식으로 (ex. fast, slow = 2,1) 지정한 후 fast runner가 리스트의 끝지점에 도착하면 slow는 정확히 리스트의 중간 지점에 도달하게 된다. 중간위치를 찾아냄으로써 값 비교 (palindrome linked list 문제), 뒤집기를 시도하는 등의 연결 리스트..

1. (정적)배열 : 연속된, 정해진 크기의 메모리 공간을 할당. 같은 타입의 원소만을 담을 수 있음. (정해진 크기의 메모리 공간을 할당하고, 이를 원소 타입, 원소 개수에 맞춰서 분할하기 때문) 또한 한 번 생성한 배열은 크기 변경이 불가능하다. 배열의 장점은 어느 위치에나 O(1)에 조회가 가능하다는 점이다. (배열 시작 주소 + 원소 타입에 따른 바이트 크기 * 원소 인덱스)로 해당 배열 원소 값의 주소 계산 및 메모리 접근이 가능하기 때문. (배열 원소 개수에 독립적) 그러나, 원소의 삭제나 삽입 등의 작업은 최악의 경우 O(n)의 시간복잡도를 갖는다. 예를 들어 원소의 가장 첫번째 원소를 삭제한다고 가정하면 나머지 모든 원소를 하나씩 override해야 하기 때문에 (당겨와야 하기 때문에) n..

브루트 포스 (brute force) 가능한 모든 조합을 다 탐색 (답이 나올 때까지) 답을 무조건 찾을 수는 있으나, 답을 찾는 데에 비용이 너무 크다는 단점이 있음. (시간 복잡도가 크다. 탐색해야 할 것이 많다면 코테에서 타임아웃이 뜰 것) 대체적으로 완전 탐색의 시간 복잡도는 O(n!) or O(2^n) Ex) 리트코드 15번 3Sum 합이 0이 되는 3개의 수의 조합을 찾는다. 이때 brute force는 가장 간단한 방법. but, 3개이므로 배열에서 3번의 loop을 돌아야 하기 때문에 (double nested loop) 시간 복잡도가 O(n^3)임. 따라서 매우 비효율적인 방법이라고 할 수 있다. 또한 코드 가독성 또한 떨어짐. (아래 참고) for i in range(len(nums)-..

그래프 : 연결되어 있는 객체 간의 관계를 표현하는 비선형 자료구조 가장 일반적인 자료구조의 형태로, tree도 그래프의 특수한 경우이다. 예를 들면, 전기회로의 소자 간 연결 상태나 혹은 운영체제의 프로세스와 자원 관계 또한 그래프로 표현이 가능하다. 그래프의 정의 그래프 G는 (V,E)로 표시하며, 이때 V는 정점 vertex의 집합을 E는 간선 edge의 집합을 의미함. - vertex (정점) : 여러 가지 특성을 가질 수 있는 객체를 의미함. 노드(node)라고도 함. - edge (간선) : 정점들 간의 관계를 의미. link라고도 함. 그래프의 종류 1) 무향 그래프 (undirected graph) : 무향 에지는 양방향의 의미임. 예컨대 조합(combination)처럼 (A,B) = (B..

내가 발견한 그리드 서치의 문제점 1. 많은 범위를 지정할 경우, 연산 시간이 너무 오래 걸림. --> 다양한 range의 하이퍼 파라미터 값 assign이 불가능함. 2. 1이 불가능하기 때문에, 내가 알아서 값을 정해서 param에 넣어줘야 하는데 이게 많이 힘들다. 내가 하는 방식은 범위가 넓게 그리드 서치를 하면서 그때 마다 도출된 최적값을 기준으로 해서 그 안에서 범위를 줄여나가는 방식으로 그리드 서치를 반복하는 방법인데, 마찬가지로 연산 시간이 너무 오래 걸리고, 일단 내가 찾은 최적값이 global optimum이라는 보장이 없다. 3. 여러 개 변수가 있을 경우 여러 번 돌릴 때 탐색된 최적값이 계속 변한다는 단점(?)이 있었다. --> 근데 이건 내가 코딩 잘못했을 수도 있다고 봄. 좀 ..

스크립트 파일 관리 : 코드가 너무 길면 어떤 게 어디 있는지 찾기 어렵다. 수천 줄의 코드가 담긴 스크립트 파일을 어떻게 관리할지. - 캡슐화(Encapsulation) : 특정 기능을 수행하는 코드를 가져다가 꽁꽁 싸는 것. 유지, 보수, 관리가 잘됨. 1) R studio 기능 활용 : Script 파일 목차(구역 나누기 & 목차)를 만들 수 있음. (주석 끝에 ####) 코드 접고 펼 수 있음. 2) 사용자 정의 함수 활용 : 특정 기능을 하는 코드 뭉치를 사용자 정의 함수로 만든다. 별도의 스크립트 파일에 저장하여 필요할 때 불러온다(source 함수). or 패키지로 만들어버림. - 스크립트 파일 grouping 1) 용도에 따른 구분 : 데이터 입출력, 전처리, 시각화 및 레포팅 등 2) 성..

데이터 재가공 1. cbind와 rbind 동일한(열의 수와 이름 모두 일치) 열들 또는 동일한 수의 행을 가진 두 데이터셋을 가졌을 경우 cbind -> column bind; 열 기준으로 합침(vertical), 옆에다 갖다 붙인다고 생각하면 됨 rbind -> row bind; 행 기준으로 합침(horizontal), 아래다 갖다 붙인다고 생각하면 됨 2. 조인(join) 데이터가 항상 cbind를 사용해 결합할 수 있을 정도로 잘 정렬된 형태로 존재하지는 X. 조인을 위한 가장 일반적인 함수 세 가지는 merge, plyr 패키지의 join, data.table에서의 병합 기능 1) merge merge(x, y, by.x, by.y) 이때, x, y = 병합하고자 하는 두 가지 data.fram..