개요 따로 알고리즘 포스팅을 하는건 union-find 이후 1년만이다사실 코테에 나올 확률이 매우 드문 알고리즘이라고 생각해 본인이 코테 대비만 한다면 굳이 알 필요는 없을 것 같지만.. 개인적인 호기심으로 작년 말부터 정리해야겠다 생각은 했는데, 그동안 놓았던 ps를 다시 감을 잡고 돌아오는데 시간이 많이 걸렸다. 위키를 보면 Travelling Salesman Problem(이하 TSP)를 다음과 같이 설명하고 있다."Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and return..
mysql에 이어 두 번째 데이터베이스 익히기 https://redis.io/ Redis Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache, and message broker redis.io NoSQL '데이터베이스에는 관계형 데이터베이스(RDBMS) 이외에도 여러가지 형태의 데이터베이스가 존재한다' 라고 데이터베이스 전공수업때 배운 적이 있다. 지금까지 내가 써온 Mysql은 관계형 데이터베이스(RDBMS)의 대표적인 예시로, SQL이라고 불리는 쿼리에 의해 저장되며, 모든 데이터는 정해진(정적) 스키마에 맞추어 테이블 형태로 저장되며, 테이블은 열과 행으로 구성되어 관계를 표현..
유니온 파인드 알고리즘 유니온 파인드 알고리즘은 그래프상에서 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 다음과 같이 노드들이 존재할 경우, 유니온 파인드 알고리즘을 위해서는 노드를 나타내는 일차원 정수배열을 이용한다. 이 배열의 값은 노드가 속한 그래프의 정보이자, 대표 노드의 정보를 나타낸다. 당연히 배열의 초기값은 자기 자신으로 세팅한다. 연결된 노드가 없을 경우 자기 자신이 부모노드가 되기 때문이다. 초기화 처음에는 노드들 사이에 관계가 존재하지 않으므로 모든 노드는 자기 자신의 인덱스를 값으로 갖도록 초기화해준다. int[] parent = {1,2,3,4,5,6,7,8}; Union 두 노드가 같은 그룹에 속하도록 합쳐주는 함수이다. 가장 먼저 생각할 수 있는 방법은 한 노드의 값..
SQL 데이터베이스 시스템에서 자료를 처리하는 용도로 사용되는 언어. 목적에 따라서 DDL(데이터 정의어 - 테이블이나 관계 생성), DML(데이터 조작어 - 테이블의 데이터 CRUD), DCL(데이터 제어어 - 데이터의 사용 권한 관리)로 구분된다. DDL (데이터 정의어) 테이블을 구성하거나, 속성과 기본키(pk)/외래키(fk)를 정의하는 쿼리문을 말한다. 테이블을 생성하는 create문, 테이블 구조를 수정하는 alter문, 그리고 테이블을 삭제하는 drop문이 있다. CREATE : 테이블을 생성하기 위한 쿼리문. 속성명과 데이터타입을 명시해주고 뒤에 속성의 제약을 정의해줄 수 있다. 속성을 모두 정의하고 나서 pk와 fk를 정의해줄 수도 있고, 제약을 정의할 때 같이 정의해줄 수도 있다. ALT..
부분 배열의 합을 구하기 위해서 다양한 방법을 사용할 수 있다. 1차원 누적합 다음과 같은 배열이 있다고 하자. int[] arr = {1,2,3,4,5}; 두 번째부터 다섯 번째 원소까지의 합을 구하기 위해서는, for문을 이용해서 직접 구해줄 수 있다. for(i=1...5) rst+=arr[i] 그런데 만약 arr이 충분히 크다면, dp를 이용하여 누적합을 저장해두고 갖다 쓸 수 있다. 두번째~다섯번째 원소합 = (첫번째~다섯번째 원소 누적합) - (첫번째~첫번째 원소 누적합) var s5=0, s1=0 for(i=0...4까지) s5+=arr[i] for(i=0...0까지) s1+=arr[i] var arr[1]부터 arr[5]까지 합 = s5-s1 일반화하면 다음과 같은 식이 나온다. 따라서 누..
개요 잘못 설계된 데이터베이스는 삭제이상, 삽입이상, 수정이상 등의 문제를 일으킬 수 있다. 삭제이상: 튜플을 삭제했는데 유지되어야 하는 정보도 연쇄삭제되는 현상 삽입이상: NULL입력시 튜플 삽입이 거부되는 이상현상 수정이상: 튜플 수정시 데이터의 일부만 수정되어 데이터의 불일치현상이 나타나는 현상 - 삭제이상: 5번 튜플(안중근)의 정보 삭제시 AI융합학부의 정보가 같이 삭제된다. - 삽입이상: 글로벌미디어 학과에 대한 정보를 삽입하고 싶지만 학생명, 학번이 NULL값이라 삽입되지 않는다. - 수정이상: 소프트웨어학부의 과사무실 정보를 수정하기 위해 3번튜플의 과사무실 정보를 변경하면 3,4번튜플에 불일치가 발생한다. 이러한 이상현상은 테이블의 잘못된 설계로 인해 발생한다. 따라서 테이블의 구조를 수..
트랜잭션 트랜잭션이란 데이터베이스에서 하나의 공통된 목적을 위한 작업을 의미한다. 예를 들면, A에서 B로의 '송금'이라는 거래를 위해서는 A의 잔고에서 임의의 금액을 빼고, B의 잔고에 임의의 금액만큼을 더해주는 2가지 일이 한 가지 일처럼 실행되어야 한다. 두가지 일 중에서 하나의 작업이라도 누락된다면 문제가 발생할 수 있는데, 트랜잭션은 모든 하위 작업을 묶어서 모두 실행되거나, 모두 실행되지 않도록 만든다. 만약에 모든 작업이 성공하여 DB에 변화가 반영되었다면 해당 작업이 커밋(commit)되었다고 하고, 하나라도 실패해서 작업 이전으로 되돌아가는 것을 롤백(rollback)이라고 한다. 트랜잭션의 성질 트랜잭션은 ACID로 불리는 4가지 대표적인 성질을 갖는데, 각각 원자성, 일관성, 고립성,..
플로이드 알고리즘 플로이드 알고리즘은 시간복잡도 조건에 여유가 있는경우(O^3) 사용할 수 있는 알고리즘으로, 한 시작점에서 다른 정점까지의 최단 거리를 구하는 다익스트라 알고리즘과 다르게 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구하는 알고리즘이다. 위 가중치 그래프에서, A에서 E로 가기 위한 방법은 (1) A에서 E로 직접 가는 방법과, (2) 중간에 C를 거져가는 방법 총 2가지 방법이 존재한다. 따라서 두 정점 쌍의 최단 거리를 구하기 위해서는 두 정점 사이에 존재하는 경유점을 거쳐가는 방법들을 탐색하며 그 방법들 중에 최소값을 구하면 된다. len[A][E] = Min(len[A][E], len[A][C] + len[C][E]) N개의 노드에 대한 플로이드 알고리즘은 O(N^3)의 시간복..
SQL 데이터베이스 시스템에서 자료를 처리하는 용도로 사용되는 언어. 목적에 따라서 DDL(데이터 정의어 - 테이블이나 관계 생성), DML(데이터 조작어 - 테이블의 데이터 CRUD), DCL(데이터 제어어 - 데이터의 사용 권한 관리)로 구분된다. DML (데이터 조작어) 테이블에 데이터를 검색/삽입/수정/삭제하는데 사용되며, select, insert, delete, update문 등이 있다. - SELECT : 테이블에 데이터를 검색하여 출력하는 목적으로 사용되는 쿼리문. 1. ALL | DISTINCT : ALL은 중복허용을 의미하고 (default값), DISTINCT는 중복을 제거하고 집계하는 것을 의미한다. ex) select distinct * from Book; 2. WHERE 절에는 ..
키 키: 특정 튜플을 식별할 때 사용하는 속성(의 집합) 슈퍼키: 유일성을 가진 속성(의 집합) 후보키: 유일성&최소성을 가진 속성(의 집합) 기본키(pk): 후보키 중 대표로 삼는 하나의 키 대리키(pk): DBMS가 임의로 생성하여 사용하는 기본키 외래키(fk): 다른 릴레이션의 기본키를 참조하는 속성 관계대수 1. 셀렉션: 릴레이션에서 조건에 맞는 튜플을 추출하는 연산 2. 프로젝션: 릴레이션의 속성을 추출하기 위한 연산 3. 합집합: 속성이 동일한 두 릴레이션을 합침. 동일튜플 존재시 하나만 표시한다. 4. 교집합: 합병가능한 두 릴레이션이 공통으로 가지고 있는 튜플을 반환 5. 차집합: 첫번째 릴레이션에는 속하고 두번째 릴레이션에는 속하지 않는 튜플을 반환 6. 카티전 프로덕트: 두 릴레이션의 ..
다익스트라(Dijkstra) 알고리즘은 BFS와 dp를 활용한 최단경로 검색 알고리즘이다. 다익스트라 알고리즘은 가중치가 존재하는 그래프의 하나의 정점에서 다른 정점들로 가는 최단 경로를 알려준다. 만약에 가중치가 존재하지 않는다면 단순 BFS를 통해서 최단 경로를 구할 수 있지만, 이 경우 일반적으로 인접 행렬(O(N^2))이나 우선순위 큐(O(ElogV), E:edge, V:vertex)를 사용하여 구현한다. 시작 전에 간단하게 설명하면, 다익스트라 알고리즘은 방문하지 않은 노드들 중에서 시작점으로부터 최소거리를 갖는 노드를 선택하여 노드들의 거리를 갱신하는 것을 반복하는 알고리즘이다. 일단 시작 노드부터 탐색을 시작한다. 정점에 붙어있는 간선 중에서 시작 노드로부터의 거리가 짧은 노드부터 선택하여 ..
예전에 풀고 정리했었는데 까먹어서 다시 정리해봄. 분명히 이해하고 넘어갔는데 왜 지금 보니깐 이해가 안되지?? BOJ 12865) 평범한 배낭 물건을 쪼개어 가져갈 수 있는 fraction knapsack문제에서는 무게당 가치(v/w)가 높은 순으로 가져가면 된다. 하지만 위와 같은 0-1 knapsack 문제는 greedy한 방법으로는 풀 수 없다. for(int i = 1; i