개요취직해서 지금 당장 좋은 점 중 하나는 취직 전까지는 내가 하고 싶은 공부를 할 수 있다는 것이기도 하다.사실 옛날부터 세그트리에 대한 궁금증이 있었는데, 코테의 당락을 결정하지는 않을 알고리즘이라 미뤄두었던 기억이 나서 이번에 알아두려고 한다. 세그먼트 트리는 '여러 개의 데이터가 연속적으로 존재할 때, 특정 범위의 데이터의 합/곱/최대값/최소값 등을 구하는 방법'중 하나이다. 수열을 저장하는 배열 A가 존재한다고 가정했을 때, 다음과 같은 케이스를 생각해보자. (A) 구간 l, r (l 이 경우 시간복잡도는 O(N)이다. 누적합, 구간합을 구해놓은 후 특정 구간의 합은 O(1)에 도출할 수 있기 때문이다. (B) 구간 l, r (l 이전 케이스와 다르게, 한번 구해놓은 누적합을 재사용할 수..
개요 그동안 데이터베이스 조회 성능 향상을 위해서 인덱스를 종종 사용했었는데, 따로 포스팅으로 정리한 적은 없어서 정리해보고자 한다.인덱스를 한 마디로 표현하면 "별도의 메모리를 추가로 할당하여 데이터베이스 조회 성능을 향상시킬 수 있는 방법"이라고 할 수 있다. 인덱스인덱스에 대해서 이야기하기 전에, 데이터베이스에서 어떻게 데이터를 조회하는지 서술하도록 하겠다. 우리가 흔히 말하는 Oracle이나 Mysql을 '데이터베이스 시스템' 이라고 부르는데, 데이터베이스 시스템은 데이터가 저장되는 '데이터베이스'와 데이터베이스를 관리하는 소프트웨어인 'DBMS(DataBase Management System)'으로 구성된다. DBMS에서 데이터베이스에 있는 데이터를 조회하기 위해서는 DBMS 내의 '질의 처리..
개요다들 알고 있을 기본적인 OS 내용이지만, 오랜만에 생각해보니 헷갈리는 부분도 있어서 기억을 되살릴 겸 정리해보고자 한다. 프로그램과 프로세스, 스레드 프로그램은 정적인 실행 파일을 말한다. 이러한 프로그램이 CPU에 올라와서 실행되면 그것을 프로세스라고 한다. 프로그램은 Long-Term Scheduler에 의해서 CPU에 올라오고(Ready), 메모리를 할당받아 프로세스가 된다. 스레드는 프로세스가 할당받은 자원을 이용하는 작업의 단위를 의미한다. 멀티프로세스와 멀티스레드CPU는 한번에 하나의 프로세스만 실행할 수 있다. 따라서 CPU를 점유(Run)하고 대기(Wait)하는 과정, 즉 Context Switching을 통해서 여러개의 프로세스를 번갈아서 실행시켜 사용자에게는 동시에 실행중인 것처..
개요 따로 알고리즘 포스팅을 하는건 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 returns to th..
개요 참고 문제: BOJ 11053, BOJ 12015, BOJ 14003, BOJ2568LIS 개념: https://eckrin.tistory.com/30 O(N^2)의 LIS 풀이: https://www.acmicpc.net/source/37212239O(NlogN)의 LIS 풀이: https://www.acmicpc.net/source/75537735 for(int i=0; i 반복문만을 사용하는 LIS의 경우, O(N^2)의 시간복잡도를 가진다. 여기서 12015번 문제의 경우는 N이 백만으로, O(N^2)의 시간복잡도를 가지는 일반적인 LIS를 사용하면 무조건 TLE가 날 것을 예상할 수 있다. int end = 0;for(int i=0; idp[end-1]) { // dp 최대길이 갱신 ..
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)의 시간복..