사진과 음악을 좋아하는 개발자 지망생의 블로그

1. 비교 모델에서의 정렬1) 비교모델이란?데이터 항목 간의 비교 연산만을 이용해 정렬을 수행하는 방식병합, 퀵, 힙 등 전통적인 정렬 알고리즘이 비교모델에 속함  2) 비교모델의 탐색과 정렬의 하한탐색 하한탐색의 경우 최악의 경우 $\log n$번의 비교가 필요함이유탐색 알고리즘은 이진 결정 트리(Binary Decision Tree)로 표현할 수 있음결정 트리의 각 내부 노드는 항목 간의 비교를 나타내며, 루트에서 리프까지의 경로는 탐색 과정임탐색 가능한 n개의 항목을 모두 포함하려면 트리의 최소 깊이는 $\log n$이 됨 정렬 하한정렬 문제는 최소 $n \log n$번의 비교가 필요함증명정렬된 배열의 경우의 수(모든 가능한 결과)는 $n!$(순열의 개수)임n!개의 리프를 포함하는 결정 트리의 최소..

1. 선택 정렬(Selection Sort)정의각 단계에서 남은 부분 중 가장 작은 원소를 선택해, 해당 위치에 배치하는 정렬 알고리즘제자리 정렬(In-place Sort)로 추가 메모리 공간을 거의 사용하지 않고, 배열 내에서 정렬함안정 정렬이 아니기 때문에 동일한 값의 순서가 변경될 수 있음  시간 복잡도최악/최선/평균: $O(N²)$  정렬 단계가장 작은(또는 큰) 원소 선택배열에서 아직 정렬되지 않은 부분 중에서 가장 작은(또는 큰) 원소를 찾음가장 앞의 원소와 교환찾은 원소를 현재 정렬되지 않은 부분의 첫 번째 원소와 교환함다음 위치로 이동다음 위치로 이동하여 1~2단계를 반복전체 배열이 정렬될 때까지 반복배열이 모두 정렬될 때까지 위 과정을 반복  장점 및 단점장점알고리즘이 직관적이고 구현이 ..

1. 스택(Stack)시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 출력되는 후입선출(LIFO, Last In First Out) 형식으로 데이터를 다루는 자료구조데이터를 추가하는 것을 push, 데이터를 꺼내는 것을 pop이라고 한다활용 예시: 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS)  1) 리스트(list) 기반 구현python에서 stack을 가장 간단히 구현하는 방법은 list를 이용하는 것이다.append 메소드를 사용하면 맨 뒤에 데이터가 추가 되고, pop을 하게 되면, 맨 앞의 데이터가 나온다시간복잡도: $O(1)$# stack 선언s = []# push - O(1)s.append(1) # [1]s.append(2) # [1, 2..

1. 투 포인터 기법1) 개요두 개의 포인터(slow, fast)를 이용하여 연결 리스트의 사이클을 탐지하는 방법slow 포인터는 한 번에 1칸씩 이동하고, fast포인터는 한 번에 2칸씩 이동  2) 사이클이 없는 경우만약 연결 리스트에 사이클이 없는 경우, fast포인터는 리스트의 끝(None)에 도달함예를 들어, A -> B -> C -> D -> None의 리스트에서, fast 포인터는 한 번에 두 칸씩 이동하면서 끝에 도달함slow 포인터: A -> B -> C -> Dfast 포인터: A -> C -> None  3) 사이클이 있는 경우사이클이 있을 경우, fast 포인터가 slow포인터를 따라잡고 만나게 되는 지점이 생김마치 원이 있는 트랙에서 두 사람이 달릴 때, 빠르게 달리는 사람이 결국..

1. Array미리 할당된 공간에 연관된 데이터를 연속적이며 순차적으로 저장하는 자료구조1) 정적 배열(Static Array)미리 할당된 크기를 가지며 연속적으로 순차적으로 데이터를 저장하는 자료구조특징고정된 크기를 갖는다저장 공간을 미리 확보해야 한다메모리 상에 데이터가 서로 인접한(연속적인) 메모리 위치에 저장된다 → 논리적 저장 순서와 물리적 저장 순서가 같다시간 복잡도삽입과 삭제 → 삽입 및 삭제로 인해 데이터들이 한칸 씩 움직여야 하기 때문에 $O(N)$을 갖음탐색메모리 시작 주소에 + N 만 하면 되기 때문(랜덤 접근, Random Accesss)에 시간 복잡도 $O(1)$을 갖음Random Access(Direct Access)데이터 접근 시, 어떤 순서로든, 어느 위치에 있는 데이터라도 ..

힙(Heaps)의 사전적 용어 Heap 1. 무질서하게 서로의 위에 쌓아 올린 물건들의 무질서한 집합체. 2. 많은 양 또는 수. 자료 구조에서의 힙(Heaps) - 트리 데이터 구조에서의 "힙"은 최댓값 또는 최솟값을 효율적으로 검색하고 추출하기 위한 방법 중 하나 - 이때 "힙"은 일종의 이진 트리(binary tree)를 기반으로 구성되며, 다음과 같은 특성을 갖는다 1. 힙은 완전 이진 트리(Complete Binary Tree) 구조를 가진다 2. 최대 힙(Max Heap)은 부모 노드가 항상 자식 노드보다 크거나 같은 값을 갖는 구조입니다. → 즉, 가장 큰 값이 루트 노드에 위치함 3. 최소 힙(Min Heap)은 부모 노드가 항상 자식 노드보다 작거나 같은 값을 갖는 구조입니다. → 즉, ..

1) BeautifulSoup으로 원하는 요소 추출하기 - 다음 사이트에 있는 책들의 이름 정보를 스크래핑 해보자 http://books.toscrape.com/catalogue/category/books/travel_2/index.html Travel | Books to Scrape - Sandbox £44.34 In stock books.toscrape.com - 해당 웹 페이지는 임의의 책 정보가 담긴 웹 사이트이다. - 스크래핑을 하기 위해선 특정 웹 페이지 전체에 어디 있는지 알아야 한다 - 그러기 위해선 전체 HTML을 분석할 줄 알아야 하는데, 이것을 돕는 도구가 웹브라우저의 '개발자 도구' 이다 - 알고싶은 곳에 커서를 두고 우클릭 후 검사 를 누르면 된다. - 개발자 도구를통해 요소를 확..

1) 웹 사이트와 웹 페이지 - 웹 화면에 보이는 것 = 웹 속에 있는 문서 하나 → 웹 페이지 - 관련된 웹 페이지의 묶음 → 웹 사이트 2) 웹 페이지는 어떻게 만들어질까? - 웹 페이지는 수 많은 코드로 이뤄짐 - 이 코드들은 클라이언트의 요청에 의해 서버로 부터 받아온 HTTP 응답의 Body임 - 서버와 클라이언트 간 소통 중간에서 웹 브라우저는 HTTP 형식으로 서버에서 클라이언트로 html 요청을 보내고 응답으로 받아 온 html 문서를 우리가 보기 쉬운 형태로 화면에 그려주는(렌더링하는) 역활을 함 3) HTML → 아래 게시글 참고 2023.04.17 - [데이터 엔지니어링 데브코스/웹 크롤링] - [Web Scraping 기초] HTML 기초 ")은 선택사항이 될 수도 있고 필수사힝이 ..