건망증 환자의 뇌장하드

정렬 알고리즘 시리즈를 시작해보려고 한다. 기초 정렬 알고리즘인 selection sort부터 시작해서 Insertion sort, merge sort, heap sort, bubble sort 등등.. 오늘은 그 첫번째인 선택정렬이다. Sorting algorithm 1. 선택정렬 선택정렬은 가장 작은 수를 선택하여 교환을 반복하는 정렬이다. interger type 배열의 정렬으로 예를 들어보자. 아래와 같은 배열이 있다. 이 배열을 순차적으로 돌며 가장 작은 값을 교환해줄 것이다. 1. 0번째 index부터 시작하여, 0번째 이후의 원소 중 가장 작은 값을 찾아서 값을 교환한다. 2. 1번째 index를 가리키며 1번째 이후의 원소 중 가장 작은 값을 찾아서 값을 교환한다. 3. 1번과 2번을 반복..

Divide and conquer, 분할 정복 알고리즘 단어 그대로 "분할", "정복", "합치기" 세개로 나누어 진행하는 알고리즘이다. divide and conquer알고리즘의 대표적인 예로는 merge sort가 있으며 quick sort, ip 주소 할당, memorization알고리즘 등이 있다. 1. 분할(divide) - 가장 작은 단위가 될때 까지 쪼갠다. - 주어진 문제의 최소단위로 나누어질때 까지 같은 작업을 반복하기 때문에 recursion으로 구현할 수 있다. 2. 정복(conquer) - 쪼개진 단위들을 정렬하며 합쳐나간다. merge sort의 time complexity는 O(logn)이 된다. 프로그래밍언어마다 내장되어 있는 sort method가 있다. //javascrip..

BST - 이진탐색과 연결 리스트를 결합한 자료구조이다. - 트리형태이며 하나의 노드는 left, value, right를 가진다. - value는 unique이다. - 어떤 노드를 기준으로 왼쪽노드의 value는 더 작은 값이 들어간다 - 어떤 노드를 기준으로 오른쪽노드의 value는 더 큰 값이 들어간다 - 루트 노드를 기준으로 왼쪽의 노드들의 value는 루트 노드의 value보다 작다. - 루트 노드를 기준으로 오른쪽의 노드들의 value는 루트 노드의 value보다 크다. - 현재 노드를 기준으로 큰 값은 오른쪽 작은 값은 왼쪽에 있으므로 time complexity는 O(logn)이다 1. 삽입 알고리즘 - root node부터 검색하여 큰값이면 오른쪽 작은값이면 왼쪽으로 위치시킬 수 있도록 ..

웹 소켓이란? - 웹 표준 프로토콜 중 하나이다. - 웹 페이지의 한계에서 벗어나 실시간으로 상호작용 하는 웹 서비스를 만드는 표준 기술 이다. - Chrome, Safari, Firefox, Opera등의 브라우저에서 사용할 수 있다. - 80번 포트를 통해 웹 서버에 연결한다. 웹 소켓의 특징 양방향 통신(Full-Duplex) - 데이터 송수신을 동시에 처리한다. - 서버와 브라우저 간 연결을 유지한 상태로 데이터를 교환할 수 있다. - 패킷(packet) 형태로 데이터를 송수신하며, 양방향 통신이다. - connection의 중단과 추가 요청 없이 양방향으로 이루어진다. - 통상적인 HTTP통신은 Client가 요청을 보내는 경우에만 Server가 응답하는 단방향 통신이며, 웹 소켓은 양방향 통신..

위상정렬이란? 순서가 정해져있는 작업을 차례로 수행해야 될 경우, 그 순서를 결정하는 알고리즘 이다. 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것이다. 위상정렬 알고리즘 - 그래프가 존재 - 그래프에는 노드가 존재하며 각 노드에는 방문 순서가 존재한다. - 하나의 그래프에는 여러개의 위상정렬이 가능하다. - 위상정렬 도중 그래프에 남아있는 노드 중 incoming이 0인 정점이 없다면, 위상정렬 알고리즘으로 해결할 수 없는 그래프이므로 알고리즘 실행 종료 - Queue를 이용한다 - 알고리즘 실행 순서 1. incoming이 없는 node부터 시작한다. 2. outgoing node로 이동 3. outgoing node에서 incoming 숫자 1감소 4. 해당 ..

Database, DB - 여러 사람이 공유하여 사용할 목적으로 체계화하여 관리하는 데이터의 집합. - 작성된 카테고리별 통합 정보를 저장하여 운영할 수 있는 공용 데이터의 묶음 - 컴퓨터 시스템에 전자 방식으로 저장된 구조화된 정보 또는 데이터의 체계적인 집합 - DBMS에 의해 관리 된다. - Data의 작성 및 Query 작업에 구조화 된 질의언어인 SQL을 사용한다. SQL(Structured Query Language)이란? - SQL은 데이터를 Query, 조작 및 정의하고 액세스 제어를 제공하기 위해 거의 모든 Relational DB에서 사용되는 언어이다. - 목적에 따라 3가지 로 나눈다. 종류 역할 예시 DDL(Data Definition Language) DB 테이블 생성, 삭제, 업..

노드와 노드가 양방향으로 연결되어 있는 자료구조이다. 각 노드는 value를 저장하는 부분, 이전노드(previous, head방향)와 다음노드(next, tail방향)를 가리키는 부분이 있다. Doubly Linked List는 아래와 같은 모양으로 구현이 된다. 단방향인 단순 Linked List에 비해 양방향이므로 저장공간이 더 필요하다. linked list의 front에는 head가 있고, linked list의 마지막에는 tail이 있다. 1. 삽입 push_front - head쪽에 노드를 추가한다 - 기존노드prev와 새로운노드next와 연결시킨다. - head와 새로운 node를 연결 시킨다. push_back - tail쪽에 노드를 추가한다 - 기존노드next와 새로운노드prev를 연결..

Hashing 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환 Hash Table - hash table은 Key, Value로 데이터를 저장하는 자료구조이다 - 검색하고자 하는 Key값을 입력받아, hash함수의 결과물인 hash code를 배열의 index로 Value에 접근 - Time complexity : O(1) - Key, Hash function, Hash code, Value, Bucket slot으로 이루어져 있음 - Key ‣ Unique value이며 Hash function에 input되는 값이다. ‣ Key는 character, string, number, filedata 등이 올 수 있다. - Hash function ‣ Key를 입력받아 hash code를 ..