B-tree란? 이진트리를 확장한 자료구조로, 탐색 성능을 높이기 위해 평소에 데이터들의 높이를 균형있게 유지하는 Balanced Tree의 일종이다. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있다. 하나의 노드가 가질 수 있는 자식의 최대 숫자가 2보다 크다. 모든 단말(leaf) 노드는 같은 레벨에 있어야 한다. 항상 균형을 유지한다 (균형 잡힌 트리). 최대 M개의 자식을 가질 수 있는 B 트리를 M차(M-way) B트리라고 한다. 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다. (e.g. 3차 B트리 : 1~3개의 자식 노드 가능) 노드 내에 **데이터(key)**는 floor(M/2)-1개부터 최대 M-1개까지 포함될 수 있다 특정 노드의 데이터(key)가 K개라면, 자식 노드의 ..
인덱스란? : 테이블 안의 데이터를 쉽고 빠르게 찾을 수 있도록 만든 데이터베이스 객체. 책의 목차나 색인을 통해 더 빠르게 내용을 찾는것과 같은 개념이다. 특정 속성에 인덱스를 생성하면, 해당 속성에 대한 데이터들을 정렬해서 별도의 메모리 공간에 데이터의 물리적 주소값(디스크 블록의 주소값)과 함께 저장된다. DB와 디스크DB 데이터가 물리적으로 저장되는 곳은 디스크(보조기억장치)이기 때문에, SQL 실행시 디스크로부터 필요한 데이터를 찾게 된다. DBMS는 필요한 디스크 블럭을 반복해서 주기억장치로 읽어오게 되는데, 문제는 디스크 접근 속도가 주기억장치보다 비교할 수 없을 정도로 너무 느리다는 점이다.DB의 테이블 데이터들은 모두 블록 단위로 관리된다. 만약 쿼리를 통해 1개의 레코드를 읽고 싶더라도..
컴공 복수전공 시작 2021년은 휴학을 하면서 내 진로를 찾았던 중요한 해다. 친구의 권유로 프론트엔드 (html, css, JS)를 배워봤고, 웹 앱 개발에 관심을 갖게 되면서 부트캠프 백엔드 과정을 등록, 수료했다. 부트캠프는 효율성 측면에서 그닥 좋지 않았지만, 개발에 뜻을 가진 사람들(다른 분야에 종사하시다 개발에 관심을 갖게된 분들과 커뮤니케이션해보는 경험이 새로웠다.) 2021년은 방황을 멈추고 진로를 정했기 때문에 굉장히 뜻깊은 해였다. 그렇게 2022년도 컴퓨터학과 복수전공을 신청했다. 1학기에 배우게 된 미적분과 확률통계는 생각보다 재미있었다. 교수님의 강의보다는 책에 담겨있는 내용이 재밌었다. 편입 수학을 공부하면서 수학적인 사고방식에 재미를 붙였던게 도움이 됐다. 이 사고방식은 당장 ..
관계형 데이터 모델 관계형 데이터 모델은 릴레이션(relation)이라는 수학적 개념에 기초하고 있다. 결국 릴레이션(relation)은 동일한 구조로 이뤄진 튜플(tuple)의 집합이고, 2차원 테이블(table) 형태의 단순한 구조다. (테이블 개념은 내부 저장 구조에 대한 추상적인 표현일 뿐이고, 물리적으로는 복잡한 구조 속에 데이터가 저장된다.) 관계형 데이터베이스는 데이터 묶음을 릴레이션(테이블)의 형태로 저장한다. 주로 테이블이라고 불린다. 💡 릴레이션(테이블) Student라는 릴레이션을 상상해보자. 학번이름학과나이전화번호MBTI 170 원석 컴퓨터SW 27 010123123 INTP 180 영두 컴퓨터SW 24 010456456 ISTP 181 성욱 정보보호 24 010789789 INFP..
데이터베이스 시스템(DBMS)을 쓰는 이유 파일 정보 시스템의 문제점: 데이터 중복성, 비일관성 검색의 비효율성 데이터들간에 연결성 부족(여러 파일에 같은 종류의 데이터가 흩어져있을 수 있음) 동시 접근 불가능 및 데이터 무결성 부족(여러 사용자가 접근할 때 데이터에 손상이 생길 수 있다) 복구 어려움 데이터베이스 관리 시스템(DBMS)의 장점: 데이터의 독립성 물리적 독립성 : 데이터베이스 사이즈를 늘리거나 성능 향상을 위해 데이터 파일을 추가하더라도 관련된 응용 프로그램을 수정할 필요가 없다. 논리적 독립성 : 데이터베이스는 논리적인 구조로 다양한 응용 프로그램의 논리적 요구를 만족시켜줄 수 있다. 데이터 종속성 최소화 데이터 저장 방식과 접근 방식에 변화가 생기더라도 관련된 응용 프로그램 수정의 부..
선형 자료구조 Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way. 스택, 큐, 데크는 모두 추상 자료형(ADT)이다. 즉, 언어에서 기본적으로 제공되는게 아니라 데이터와 연산들에 의해 정의되는 추상적인 자료구조이다. 각각을 구현하는건 프로그래머의 몫이다. 스택, 큐, 데크 모두 선형 자료 구조이며 각자 특정 방향으로 **삽입(push), 삭제(pop)**가 된다는 특징을 갖고 있다. 그리고 n개의 원소들로 이뤄진 선형 리스트이다. 그렇기 때문에 보통 is_empty() ..
배열이란? 배열은 연속적인(인접한) 메모리 공간에 저장된, 같은 타입의 데이터들의 모임이다. 가장 기초적인 자료구조. 배열의 연산들 접근 연산 : 항상 O(1) 배열의 접근 연산은 index를 이용하고 이는 random access로, 빠른 속도를 보여준다. 탐색 연산(선형 탐색이라고 가정할 때 배열의 길이에 비례한다. O(n) ) # 선형 탐색 def lenear_search(arr, n, key): for i in range(n): # found if (arr[i] == key): return i # If the key is not found return -1 삽입 연산 : 맨 끝자리에 대한 삽입은 해당 자리를 찾아서 넣기만 하면 끝이다. 즉 접근 연산과 할당 연산 두개이기 때문에 O(1) 이다. 그..
알고리즘을 평가하는 두 가지 주요 기준은 시간과 공간이다. 이 두 요소는 서로 상충하는 경우가 많다. 메모리를 아끼려면 속도를 희생하고, 속도를 높이려면 메모리를 희생하는 식. 통상 더 중요시되는 기준은 시간이다. 프로그래밍 대회를 나가거나 알고리즘을 발명할게 아니라면 대부분 코딩 테스트를 보는 입장에서, 시간 제한을 지키는 것이 문제를 해결하는 것 다음으로 중요한 태스크다.시간 복잡도란?시간 복잡도(time complexity)란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다. 알고리즘의 속도를 비교하는 가장 직관적인 방법은 실제 실행시간 측정이다. 그러나, 이는 알고리즘의 속도를 일반적으로 논하는 ..
파인만 알고리즘. 칠판에 문제를 적는다. 골똘히 생각한다. 칠판에 답안을 적는다. 구종만 선생님께서 제시하신 문제해결과정. 문제를 읽고 이해하기백준 알고리즘을 풀면서 정말 많이 느낀 점이다. 입력과 출력 예시가 부족하다고 할 수도 있겠지만, 애초에 ‘문제’를 꼼꼼히 읽었다면 문제를 오해하는 일은 일어나지 않을 것이다.변수의 값, 시간 등 제약조건을 이해하기 위해선 알고리즘 시간복잡도, 공간복잡도 분석과 언어의 값 범위에 대한 이해가 선행되어야 한다.문제에서 나오는 개념이나, 지문에서 묻는 전반적인 요구조건과 제약조건을 일단 이해하자. 문제의 재정의와 추상화…자신이 다루기 쉬운 개념을 이용해서, 문제를 자신의 언어로 풀어 쓰는 것입니다. 이 과정은 문제가 요구하는 바를 직관적으로 이해하기 위해 꼭 필요합니..
구조체란구조체(structure)란, 각각 다른 type의 요소들로 구성될 수 있는 데이터이다. 배열과 달리 각 원소들은 이름을 갖고 이름을 통해 접근할 수 있다..굳이 따지자면 파이썬의 dictionary와 비슷하다고 할 수 있다. (실제로 C언어의 struct를 dictionary로 변환하는 파이썬 모듈이 있다고 한다…) 그래서 구조체가 뭔데?결국 struct 은 하나의 데이터 타입이고, int 란 키워드가 데이터타입으로써 여러 곳에 쓰이듯이 struct 키워드도 다양하게 쓰인다. (구조체의 이름을 tag라고 부르는데, 그냥 이름이라고 부르겠다)struct Car { char brand[50]; char model[50]; int year; }; struct Point { int x; int y; }..
