https://heo-it-til.tistory.com/48 [백준] 웜홀 : 1865 Python 이 문제를 봤을 때, 플로이드 와샬로 풀 수 있을까 고민했지만 tc의 개수가 5개, N의 크기가 500인 것을 보고 플로이드와 샬을 포기하고, 음의 가중치라는 점에서 벨만 포드 알고리즘을 시도했다. heo-it-til.tistory.com
CS 기본
이분 탐색(binary Search) 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 데이터가 정렬되어야지 사용할 수 있음. 시간복잡도 O(log n) start, mid, end 가 존재 ex) 17, 28, 43, 67 , 88, 92, 100 에서 43을 찾아보자 여기서 끝나면 아쉽다. 위 같은 경우는 쉽지만 이분 탐색 하면 항상 헷갈리는 조건들이 존재 요약 [s, e]가 Check(s) != Check(e)가 되도록 구간을 설정 while (s + 1 < e)동안 mid = (s + e) / 2에서 Check(mid) = Check(s)라면 s = mid, 아니라면 e = mid 구한 경계에서 답이 s인지 e인지 생각해보고 출력 (1에서 경계는 항상 [s, e] 내에 ..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 비선형 자료구조 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조 일반적으로 트리나 그래프를 말함 그래프(Graph) 정점과 간선으로 이루어진 자료구조 https://ltsgod.tistory.com/147 그래프 이론 그래프 데이터(노드)들을 잘 정리하는(노드간의 관계를) 방법 중 하나 데이터들과 그 관계를 보여주는 방법 중 하나 서로 연관 있는 노드의 집합 G = (N, E) 네트워크 형태의 관계를 보여주기에 적 ltsgod.tistory.com 트리 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터 집합 https://ltsgod.tistory.com/125 트리(Tree), 이진..
그래프 데이터(노드)들을 잘 정리하는(노드간의 관계를) 방법 중 하나 데이터들과 그 관계를 보여주는 방법 중 하나 서로 연관 있는 노드의 집합 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?? -> 실제 주소로 하면..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 관계형 데이터베이스 행과 열을 가지는 표 형식 데이터를 저장하는 형태의 데이터베이스 SQL 언어로 조작 MySQL, PostgresSQL, 오라클, SQL server, MSSQL MySQL 가장 많이 사용하는 데이터베이스 C, C++ 기반 B-트리 기반의 인덱스, 스레드 기반 메모리 할당 시스템, 빠른 조인, 최대 64개의 인덱스 제공. NoSQL(Not only SQL) SQL을 사용하지 않는 데이터베이스 MongoDB, Redis MongoDB JSON을 통해 데이터 접근 Binary JSON(BSON)형태로 데이터 저장 키-값 데이터 모델에서 활장된 도큐먼트 기반 DB 확장성 뛰어남 Redis 인메모리 데이터베이스, 키-값..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. 트랜잭션(transaction) 데이터베이스에서 하나의 논리적 기능을 수행하기 위한 작업의 단위 여러 개의 쿼리들을 하나로 묶는 단위 트랜잭션 특징(ACID) 원자성(Atomicity) 일관성(Consistency) 격리성(Isolation) 지속성(Durability) 원자성 All or nothing 트랜잭션에 속한 연산이 모두 수행되거나 하나도 실행되지 않아야함. 일관성 트랜잭션이 성공적으로 수행된 후에도 데이터베이스가 일관된 상태를 유지해야 함. 격리성 트랜잭션 수행 시 서로 끼어들지 못하게 하는 것 지속성 성공적으로 수행된 트랜잭션은 영원히 반영되어야 함. 이는 DB에 시스템 장애가 발생해도 원래 상태로 복구하는 회복 기..
본 포스팅은 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다. ERD(Entity Realationship Diagram) 데이터베이스를 구축할 때 가장 기초적인 뼈대 역할 릴레이션 간의 관계들을 정의 시스템의 요구사항을 기반으로 작성 ERD를 기반으로 DB구축 비정형 데이터를 충분히 표현할 수 없다는 단점 예시 정규화 과정 릴레이션 간의 잘못된 종속 관계로 인한 이상현상을 제거하기 위함. 릴레이션을 여러 개로 분리하는 과정 정규형 원칙을 기반으로 정규형을 만들어 가는 과정 정규형(NF, Normal Form) 1, 2, 3, 보이스/코드 정규형 존재 이상(anomaly) 현상 삽입 이상 : 새 데이터를 삽입하기 위해 불필요한 데이터도 함께 삽입해야 하는 문제 갱신 이상 : 중복 튜플 중 일..
