이것저것

Set - LinkedList 와 달리 데이터의 중복을 허용하지 않는다. - 인덱스 대신 iterator를 이용해 검색 - 순서가 보장되지 않는다. - insert, erase - 삽입/삭제 : O(logN) - Set은 Map의 축소형 => Key 만 있는 Map (Map도 Key는 중복 불가하기 때문에) set s; s.insert(1); s.insert(2); s.insert(1); s.insert(2); //s안에는 1,2,1,2 가 아닌 1,2만 있다 Map - key-value 형식으로 데이터를 저장 - 순서가 보장되지 않는다. - Key는 중복 불가, value는 중복 가능 - 삽입/삭제/탐색 : O(logN) - map m; //string : key, char : value (pair 형..

- 현재 우선순위 큐 안에서 제일 우선순위가 높은 원소가 pop됨 - 주요 명령어 : push, pop, top - Heap 을 이용해서 구현 - heap 은 트리 구조로 되어있다. (노드들로 구성되어있으며, 각 노드는 부모-자식 관계로 이루어져 있다.) - max heap : 숫자가 클 수록 우선순위가 높다. - min heap : 숫자가 작을 수록 우선순위가 높다. - 삽입/삭제 : O(logN) c++ 에서 priority queue는 max heap으로 구성된다. min heap으로 구성하기 위해서는 greater 을 사용하여 정렬하면 된다. - max heap priority queue 선언 priority_queue pq; - min heap priority queue 선언 priority_q..

www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 1. 시작점과 끝점은 중요하지 않고, 그 사이의 거리가 중요합니다. 2. 처음 시작은 1 마지막 시작은 1로 끝나야 합니다. 3. 아이디어가 딱히 떠오르지않아서 막무가내로 다 그려보고 적어보니깐 규칙이 발견되었습니다. 거리 작동횟수 1 1 2 2 3 3 4 3 5 4 6 4 7 5 8 5 9 5 10 6 11 6 12 6 13 7 14 7 15 7 이 규칙에 맞게 코..

소수와 관련된 알고리즘은 두 가지가 있다. 어떤 수 N이 소수인지 아닌지 판별하는 방법 N보나 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법 (N이하의 소수) 소수 : 약수가 1과 자기 자신밖에 없는 수 N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. ⇒O(N) N이 소수가 되려면, 2보다 크거나 같고 N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 이유 : N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문 ( N=a x b로 나타낼 수 있는데, a가 작을수록 b는 크다. 가능한 a 중에서 가장 작은 값은 2이기 때문에, b는 N/2를 넘지 않는다.) ⇒O(N/2) N이 소수가 되려면, 2보다 크거나 같고, 루트 N보다 작거나..

[데드락(교착상태)이란?] 두 개 이상의 트랜잭션이 각각 자신의 데이터에 대하여 Lock을 획득하고 상대방 데이터에 대하여 Lock을 요청하면 무한 대기 상태에 빠질 수 있는 현상 데이터베이스의 데드락은 운영체제의 데드락과 상당히 비슷합니다. 위의 정의를 풀어 설명하면, 공통된 자원을 이용하기 위해 여러 개의 트랜잭션이 서로 Lock을 걸어주다가 무한 대기 상태에 빠지는 것을 데드락이라고 한다. 예를 들어 먼저 T1에서 A에 대해 Lock을 걸고, T2에서 B에 대해 Lock을 걸었다고 가정해보자. 그리고 나서 T1에서 B에 대해 Lock을 걸고 T2가 A에 대해 Lock을 건다면, T1과 T2는 서로 A, B에 대한 Lock을 유지하며 무한루프에 빠지게 된다. 일반적으로 데드락이 발생하면 DBMS가 T..

[DB에 저장되는 데이터는 어디에 저장될까?] 하드디스크에 저장된다. 하드디스크에 저장된 데이터를 읽어 우리가 볼 수 있도록 데이터를 가져다 준다. 이 디스크를 읽는 두 가지 방식 (1) Sequential Access (2) Random Access => 디스크 헤더가 움직이는 속도때문에 Sequential Access 는 Random Access 보다 무려 100배 정도 더 빠르다. [DBMS는 데이터를 어떤 형태로 저장할까?] DB는 디스크에 데이터를 저장할 때 블록 형태로 쪼개 디스크에 쓴다. DB는 commit을 하면 바로 DB 서버에 있는 디스크 데이터를 쓰지않고, 메모리나 Sequential한 Log에 적어 이를 보관하고 데이터가 어느정도 찼으면 BLOCK으로 만들어 하드디스크에 저장한다. ..

[Spring 3.1 이하] 응답헤더에 Content-Type 지정 @RequestMapping(value = "/users",method=RequestMethod.POST) [Spring 3.2 이상] content-type 지정 @RequestMapping(value = "/users", produces = "application/json; charset=utf8")

최대공약수(혹은 최소공배수)를 구할때 유클리드 호제법을 사용하면 간단하다. a를 b로 나눈 나머지를 r이라고 했을때 GCD(a,b) = GCD(b,r) 과 같다. r=0 이면 그 때, b가 최대 공약수이다. //재귀함수를 사용하여 구현한 유클리드 호제법 int GCD(int a,int b){ if(b==0){ return a; }else{ return GCD(b,a%b); } } 세 수의 최대공약수는 다음과 같이 구할 수 있다. GCD(a,b,c) = GCD(GCD(a,b),c) 네 수, N개의 숫자도 위와 같은 식으로 계속해서 구할 수 있다. 최소공배수는 줄여서 LCM이라고 한다. 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수 최소공배수는 GCD 를 응용해서 구할 수 있다. G = ..