본문 바로가기

CS 전공지식20

3. 비선형 자료 구조 ✨비선형 자료 구조 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말함 1. 그래프 정점과 간선으로 이루어진 자료 구조 정점과 간선 A에서 B로 C를 통해 간다고 했을 때 ‘B’는 정점(vertex)이 되고 ‘C’는 간선(edge)이다. 단방향 간선 : 한쪽으로만 이동 가능 양방향 간선 : 양쪽으로 이동 가능 정점으로 나가는 간선 : 해당 정점의 outdegree 들어오는 간선 : 해당 정점의 indegree 정점은 약자로 V 또는 U라고 하며, 보통 “U에서부터 V로 간다.”라고 표현 정점과 간선으로 이루어진 집합을 ‘그래프(graph)’라고 한다. 가중치 가중치는 간선과 정점 사이에 드는 비용 1번 노드와 2번 노드까지 가는 비용이 한 칸이라면 1번 노드에서 2번 노드까지의 가중치는 한 칸 .. 2023. 8. 23.
2. 선형 자료 구조 ✨ 선형 자료 구조 요소가 일렬로 나열되어 있는 자료 구조를 말함 1. 연결 리스트 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조 앞의 그림처럼 prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결 리스트이며, 연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트 등이 있다. 참고로 맨 앞에 있는 노드를 헤드(head)라고 한다. • 싱글 연결 리스트: next 포인터만 가짐 • 이중 연결 리스트: next 포인터와 prev 포인터를 가짐 • 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것 이 책에서는 이중 연결 리스트를 기반으로 설명하겠습니다. 이중 연결 리스트는 앞에.. 2023. 8. 23.
1. 복잡도 ⭐자료 구조(data structure) 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합 복잡도 종류 1. 시간 복잡도 2. 공간 복잡도 1. 시간 복잡도 (Time Complexity) ‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계’ 어떠한 알고리즘의 로직이 ‘얼마나 오랜 시간’이 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다. 빅오 표기법 인도의 왕이 지혜로운 사람에게 상을 내리고 싶어 했는데, 이 사람은 체스판을 가득 채울 만큼의 밀알을 원했다. 조건은 체스판의 1알의 밀알을, 두번째 칸에는 2알의 밀알을, 세 번째 칸에는 4알의 밀알을... 이런 식으로 체스 판의 각 칸의 바로 이전 칸에 있는 밀알의 제곱한 양으로 채워지기를 바랐다. 왕은 흔쾌.. 2023. 8. 23.
4. 데이터베이스의 종류 1. 관계형 데이터베이스(RDBMS)란? 행과 열을 가지는 표 형식 데이터를 저장하는 형태의 데이터베이스 SQL이라는 언어를 써서 조작 종류 : MySQL, PostgreSQL, 오라클, SQL Server, MSSQL 등 표준 SQL을 지키면서도 각 제품에 따라 특화된 언어를 사용 MySQL MySQL은 대부분의 운영체제와 호환되며 현재 가장 많이 사용하는 데이터베이스 C, C++로 만들어짐 MyISAM 인덱스 압축 기술, B-트리 기반의 인덱스, 스레드 기반의 메모리 할당 시스템, 매우 빠른 조인, 최대 64개의 인덱스를 제공 대용량 데이터베이스를 위해 설계되어 있고 롤백, 커밋, 이중 암호 지원 보안 등의 기능을 제공 모듈식 아키텍처로 쉽게 스토리지 엔진( 데이터베이스의 심장과도 같은 역할)을 바꿀.. 2023. 8. 10.
3. 트랜젝션과 무결성 1. 트랜잭션이란? 데이터베이스에서 하나의 논리적 기능을 수행하기 위한 작업의 단위 데이터베이스에 접근하는 방법은 쿼리이므로, 즉 여러 개의 쿼리들을 하나로 묶는 단위를 말함 ACID 특징 원자성, 일관성, 독립성, 지속성 원자성(atomicity) all or nothing 트랜잭션과 관련된 일이 모두 수행되었거나 되지 않았거나를 보장하는 특징 ex) 트랜잭션을 커밋했는데, 문제가 발생하여 롤백하는 경우 그 이후에 모두 수행되지 않음을 보장하는 것 [주의사항] 트랜잭션 단위로 여러 로직들을 묶을 때 외부 API를 호출하는 것이 있으면 안 됨 만약 있다면 롤백이 일어났을 때 어떻게 해야 할 것인지에 대한 해결 방법이 있어야 하고 트랜잭션 전파를 신경 써서 관리해야 함 커밋과 롤백 데이터의 무결성이 보장 .. 2023. 8. 10.
2. ERD와 정규화 과정 ⭐ERD(Entity Relationship Diagram) : 데이터베이스를 구축할 때 가장 기초적인 뼈대 역할 릴레이션 간의 관계들을 정의한 것 만약 서비스를 구축한다면 가장 먼저 신경 써야 할 부분 1. ERD의 중요성은? ERD는 시스템의 요구 사항을 기반으로 작성 이 ERD를 기반으로 데이터베이스를 구축 데이터베이스를 구축한 이후에도 디버깅 또는 비즈니스 프로세스 재설계가 필요한 경우에 설계도 역할을 담당 장점 ERD는 관계형 구조로 표현할 수 있는 데이터를 구성하는 데 유용 단점 비정형 데이터(비구조화 데이터, 미리 정의된 데이터 모델이 없거나 미리 정의된 방식으로 정리되지 않은 정보)를 충분히 표현할 수 없다 2. 예제로 배우는 ERD 승원 영업부서의 ERD 요구 사항 • 영업사원은 0~n명.. 2023. 8. 9.