그래프 데이터(노드)들을 잘 정리하는(노드간의 관계를) 방법 중 하나 데이터들과 그 관계를 보여주는 방법 중 하나 서로 연관 있는 노드의 집합 G = (N, E) 네트워크 형태의 관계를 보여주기에 적합 용어 노드(정점, 꼭짓점) 변(간선, 선) 차수(degree) : 나한테 몇개 연결되어 있나 루프(loop): 자기자신한테 돌아오는것 그래프의 종류 방향/무방향(directed/undirected) 그래프 순환/비순환(cyclic/acyclic) 그래프 가중/비가중(weighted/unweighted) 그래프 무방향 그래프의 최대 변 개수 모든 노드가 연결되어 있는 경우 그래프의 표현 방법 인접 행렬 N * N 행렬 G[N][N] N: 그래프 G안에 있는 노드수 서로 인접한 노드를 표현 i → j로 향하는..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 선형 자료 구조 요소가 일렬로 나열되어 있는 자료 구조 연결 리스트(Linked List) 데이터를 감싼 노드를 포인터가 연결해서 공간적인 효율성을 극대화 시킨 자료구조 삽입, 삭제 : O(1) 탐색 : O(n) 단일 연결 리스트: next 포인터만 가짐 이중 연결 리스트: next 포인터와 prev 포인터를 가짐 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next포인터가 헤드 노드를 가리키는 것 배열(Array) 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있음. 인접한 메모리 위치에 있는 데이터를 모아놓은 집합 탐색: O(1) 삽입, 삭제 : O(n) 벡터(vector) 동적으로 요소를 할당할 수..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 자료구조(Data Structure) 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합 빅오 표기법 시간 복잡도: 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타냄 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지항을 다 없앰. 시간복잡도 효율적인 코드로 개선하는 데 쓰이는 척도 공간 복잡도 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함. 자료 구조에서의 시간 복잡도
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 조인의 원리 중첩 루프 조인 정렬 병합 조인 해시 조인 중첩 루프 조인(NLJ, Nested Loop Join) 중첩 for문과 같은 원리로 조건에 맞는 조인을 하는 방법 랜덥 접근에 대한 비용이 많이 증가 따라서 대용량 테이블에 사용 X 정렬 병합 조인 각각의 테이블을 조인할 필드 기준으로 정렬하고 정렬이 끝난 후 조인 작업을 수행 조인할 때 쓸 적절한 인덱스가 없을 때 대용량 테이블 조인 조인 조건으로 등 범위 비교 연산자 있을 때 사용 해시 조인 해시 테이블 기반으로 조인 하나의 테이블이 메모리에 온전히 들어간다면 중첩 루프 조인보다 더 효율적 동등 조인(=)에서만 사용가능 빌드 단계, 프로브 단계로 나뉨 빌드 단계 ..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 조인(join) 하나의 테이블이 아닌 두 개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것 inner join(내부 조인) : 왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만 표기 left outer join(왼쪽 조인) : 왼쪽 테이블의 모든 행이 결과 테이블에 표기 right outer join(오른쪽 조인) : 오른쪽 테이블의 모든 행이 결과 테이블에 표기 full outer join(합집합 조인) : 두 개의 테이블을 기반으로 조인 조건에 만족하지 않는 행까지 모두 표기 Inner Join SELECT * FROM TableA A INNER JOIN TableB ON A.key = B.key Le..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 인덱스의 필요성 데이터를 빠르게 찾을 수 있는 하나의 장치 클러스터 인덱스와 논 클러스터 인덱스가 존재 clustering index 실제 데이터 자체가 정렬 리프 페이지 == 데이터 페이지 실제 사전의 정렬 생각 non-clustering index 실제 데이터 페이지는 그대로 존재 별도의 인덱스 페이지 생성 후 그 곳에 실제 데이터의 주소가 들어감. 책 뒷편의 인덱스 페이지 생각(실제 책은 그 순서대로 정렬되어 있지 않는다.) 만약 한 테이블에서 클러스터링 논클러스터링이 동시에 만들어진다면?? 논 클러스터링 인덱스의 실제 데이터의 주소가 들어가는 것이 아닌 클러스터링 인덱스의 key값이 들어감 why?? -> 실제 주소로 하면..
