본문 바로가기

CS

 (18)
[CS] 데이터베이스 [ 데이터베이스 ] 데이터베이스(DB, DataBase)는 일정한 규칙, 혹은 규약을 통해 구조화되어 저장되는 데이터의 모음입니다. 해당 데이터베이스를 제어, 관리 통합 시스템을 DBMS(DataBase Management System)라고 하며 DB안에 있는 데이터들은 특정 DBMS마다 정의된 쿼리 언어를 통해 삽입, 삭제, 조회 등을 수행할 수 있습니다. [ 엔터티 ] 엔터티(entity)는 사람, 장소, 물건, 사건 등 여러 개의 속성을 지닌 명사를 의미합니다.  ex) 회원 -> 이름 아이디 주소 전화번호 등의 속성을 갖습니다.  [ 릴레이션 ] 데이터베이스에서 정보를 구분하여 저장하는 기본 단위를 말합니다. 엔터티에 관한 데이터를 데이터베이스는 릴레이션 하나에 담아서 관리합니다. 관계형 데..
[CS] 운영체제 [ 운영체제 ] 운영체제란 컴퓨터 전체를 지휘하는 핵심 프로그램을 말합니다. 프로그램에게 CPU를 어떻게 할당할건지, 메모리는 어떻게 관리할건지, 프로세스는 어떻게 실행할 건지, 파일은 어떻게 관리할건지, 입출력 장치는 어떻게 활용할 것인지 등의 역활을 합니다. 즉 운영체제는 실행할 프로그램에게 필요한 자원을 할당해주고 , 프로그램이 올바르게 실행할수 있도록 돕는 특별한 프로그램입니다. 운영체제는 메모리에서 커널 영역에서 따로 적재 되어 실행됩니다. 나머지 프로그램은 사용자 영역에 적재됩니다. [ 커널 ] 운영체제에서 메모리에 올라와 있는 부분을 의미합니다. -> 운영체제의 핵심 부분 [ Byte Ordering ] Byte Ordering이란 데이터가 저장되는 순서를 의미합니다. 빅에디안(Big ..
[CS] 네트워크 [네트워크] 둘 이상의 컴퓨터가 연결 되고 소통하는 것을 의미합니다. [프로토콜] 네트워크 통신을 위한 규칙 , 약속 , 규약을 말합니다. 전 세계의 모르는 사람끼리 네트워크 통신을 하더라도 미리 정해진 규약이 있다면 그 규약에 맞춰 네트워크 통신을 편하게 할 수 있습니다. [ OSI 7계층 ] 1 계층(물리 계층) -> 데이터를 전기 신호로 바꾸는 계층입니다. 2 계층(데이터링크 계층) -> 데이터의 물리적인 전송과 에러 검출, 흐름 제어를 담당하는 계층입니다. 3 계층(네트워크 계층) -> 패킷을 목적지까지 가장 빠른 길로 전송하기 위한 계층입니다. 4 계층(전송 계층) -> 최종 수신 프로세스로 데이터의 전송을 담당하는 계층입니다. 5 계층(세션 계층) -> 컴퓨터끼리 통신을 하기 위해 세션을 만드..
[알고리즘] 투포인터(Two_Pointer) 알고리즘 투포인터 알고리즘이란 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘입니다. 두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는데 배열이나 리스트가 정렬되어 있을 때 사용합니다. 투포인터의 동작 방식과 구현 투포인터 알고리즘의 대표 문제로서 구간합 찾는 문제가 있습니다. ex) 아래와 같은 배열에서 구간합이 9인 구간을 찾아주세요 1 2 5 3 7 2 4 3 2 해당 문제는 완전탐색을 이용하여 시작구간 i 와 i+1 시작하는 j를 사용하여 찾을 수 있지만 시간복잡도는 O(N^2) 임으로 데이터가 클수록 시간이 오래걸립니다 -> 이때 사용하면 좋은것이 투포인터 알고리즘입니다. start 와 end 는 첫번째 원소를 가르킵니다. 현재 내가 ..
[알고리즘] 크루스칼(Kruskal) 알고리즘 이란 크루스칼(Kruskal) 알고리즘 의 개념 크루스칼 알고리즘은 그리디 알고리즘을 이용하여 모든 정점을 최소 비용으로 잇는 최소 비용 신창 트리를 찾는 알고리즘입니다. 크루스칼(Kruskal) 알고리즘 동작 방법 1. 그래프의 간선들을 가중치를 기준으로 오름차순 정렬합니다. 2. 정렬된 간선 리스트들 중 최소 가중치인 간선을 선택하여 사이클 발생 여부를 확인합니다. 3. 사이클이 없는 경우 해당 간선을 선택하여 최소신장트리에 추가해준후 같은 세트로 합쳐줍니다(unionSet) 4. V개의 모든 정점을 연결하는 간선의 수가 V-1 까지 반복합니다. 예제 그래프에서 최소 신장 트리를 구해보는 과정을 보여줍니다. 최소 간선 리스트중 최소 가중치인 간선을 고릅니다 -> 1 1과5를 잇는 간선은 사이클을 발생시..
[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라(Dijkstra) 알고리즘 의 개념 다익스트라 알고리즘은 음의 가중치가 없는 한 정점에서 각 모든 정점까지의 최단거리를 구하는 알고리즘입니다. 이 과정에서 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로를 모두 찾을 수 있습니다. 다익스트라 알고리즘은 BFS 알고리즘과 다이나믹 프로그래밍을 사용한 알고리즘입니다. 다익스트라 알고리즘 동작 방법 초기세팅 1. 거리를 업데이트 해줄 배열 Array : [Int] 2. 방문 했는지 안했는지 체크해줄 배열 Array : [Bool] 3. 우선순위 큐 (Heap 구조) -> 일반 큐도 가능하지만 비용이 작은 것부터 탐색하는 과정을 거치면 시간복잡도에서 이득입니다. 동작과정 1. 시작할 정점에 방문 처리한후 거리를 0으로 잡아줍니다. ..
[알고리즘] 동적계획법(DP , Dynamic Programming) 동적계획법(DP , Dynamic Programming) 이란 큰 문제를 작은문제로 나누어 푸는 문제를 말합니다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 말하고 일반적인 방법에 비해 빠른 시간 내에 풀때 사용합니다. 분할 정복과 유사하지만 차이점은 작은 문제가 중복이 일어나는지에 대한 유무 입니다. 분할정복은 작은 문제에서 반복이 일어나는 부분이 없습니다. 동적계획법 의 조건 부분 반복 문제 -> 어떤 문제가 여러개의 부분 문제로 쪼개질 수 있을때를 의미합니다. 최적 부분 구조 -> 부분 문제의 최적 결과 값을 사용하여 전체 문제의 최적 결과를 낼 수 있는 경우를 말합니다. 예를 들어 피보나치 수열 f(5)의 값을 구하기 위해서는 f(4) 의 값 + f(3) 의 값 으로 나눌수 있습..
[알고리즘] BFS(너비 우선 탐색) 알고리즘 이란 BFS(너비 우선 탐색) 알고리즘의 개념 트리 혹은 그래프를 탐색하는 기법 중 하나로 시작 노드에서 자식의 노드들을 순서대로 탐색을 하면서 방문할 수 있는 인접한 노드들을 우선으로 탐색하는 알고리즘 입니다. 자료구조는 Queue 또는 Array 를 통하여 구현 가능합니다. BFS 탐색 과정 큐를 사용하였을때 탐색 과정을 설명하면은 1. 시작 노드 1을 방문하여 1의 노드에서 방문 가능한 2, 3 ,4 를 큐 안에 넣습니다 [ 2, 3, 4 ] 2. 큐에 있는 2 , 3 , 4 를 꺼내 방문할수 있는 곳을 큐에 추가해줍니다. [ 5, 6, 7, 8 ] 3. 5, 6, 7, 8 노드도 2번 과정을 반복해줍니다. 위의 과정을 반복하면 깊이에 따라 차례차례 방문하는것을 확인할 수 있습니다. 1층에 있는 1 번 ..

티스토리툴바