전체 글 검색 결과

해당 글 904건
k번째 숫자 구하기 : 트라이(Trie) 구조를 이용해 봅시다.

수 x가 추가되고 제거됩니다. k번째로 작은 수를 구해야 하는 쿼리가 있습니다. 아니면, 수 x가 있는지 찾아야 합니다. 어떻게 해야 할까요? 물론, offline이 가능하면 정렬하고 좌표 압축한 다음에 세그먼트 트리를 돌릴 수 있어요. 하지만, online으로 해결해야 하는 경우, 정렬 후 좌표압축 스킬이 통하지 않습니다. 이 때, 우리는 수 x를 32bit 범위 내라면 32, 64bit 범위 내라면 길이 64의 2진수 문자열로 변환할 수 있습니다. 이 때, 우리는 Trie라는 자료구조를 생각할 수 있습니다. 이 Trie는 올해 카카오 4번에 나왔던 structure 이기도 합니다. Skip List는 상대적으로 구현하기 까다로우니, 논외로 합시다. 예를 들어서, 13을 넣는다고 생각해 봅시다. 그러면..
자료알고/자료구조 2019. 12. 5. 20:12
java 캡슐화 은닉화 : 필드와 기능을 하나로 묶는다.

이제 슬슬 OOP를 배워보도록 하겠습니다. ArrayList는 동적 배열입니다. 이 클래스 내부에 있는 변수들을 봅시다. elementData와 size입니다. elementData는 ArrayList의 실제 데이터들을 저장해 놓은 배열입니다. 그리고, size는 배열 리스트의 크기를 의미합니다. 이 둘을 가지고 어떠한 연산을 할 수 있을까요? 기능 중 하나인 add입니다. 이 함수 내에서, size와 elementData를 쓰고 있다는 것을 알 수 있어요. 그러면, 필드인 size와 실제 데이터를 담아두는 배열인 elementData. 이것과 기능인 add를 묶었나요? 즉, 메소드와 필드들을 하나로 묶었다고 할 수 있어요. 그러면 이들이, arrayList라는 클래스 안에 wrapping 되어 있다고도..
코딩/Java 2019. 12. 4. 20:51
c언어 free 함수 : 쌍이 맞아야 된다.

동적 할당은 무엇인가요? 예를 들어, 이런 코드가 있다고 해 봅시다. malloc 함수가 호출되기 전에 메모리 상태는 아래와 같습니다. 처음에 Heap 영역에는 아무 것도 할당되지 않았습니다. 그런데 malloc, 메모리 할당 함수가 호출이 되면, 힙 영역에 무언가를 위한 공간이 만들어 집니다. 그러면 이런 상태가 됩니다. 메모리에 할당된 주솟값을 p가 받고 있습니다. 그러면 stack에 있는 변수 p가 Heap 공간에 할당된 space를 가리킵니다. 이것이, 자동으로 해제가 되면 좋겠습니다만. 그렇지 않아요. 명시적으로 해제를 시켜주지 않으면, (동적으로 할당된 공간은) 프로그램이 끝날 때 까지 메모리에서 사라지지 않습니다. free 함수의 원형은 다음과 같습니다. 그냥 해제할 공간의 주소만 넘겨주면 ..
코딩/C 2019. 12. 3. 23:41
sql 자연조인 : 속성 값이 같은 것들끼리만 결합한다.

SQL의 자연 조인에 대해 알아봅시다. natural join은 기본적으로 동등 조인입니다. 그런데, 흔히 알고 있는 join A using B, 혹은 ON 조건절을 거는 것과 다른 점은, 조인 조건이 없다는 것입니다. 테이블 2개가 있을 때, 2개에 공통적으로 나타나는 속성들이 있을 거에요. 이 속성들에 대해서 같은 쌍만을 고려합니다. 예제를 들어보도록 하겠습니다. 어제 보았던 sakila를 보도록 합시다. rental과 customer를 natural join 한다고 해 봅시다. 먼저 table에 있는 속성들을 모두 봅시다. 고객 id, 인벤토리 id, 최근 업데이트 날짜, ... 이렇게 들어 있네요. 그리고 고객 테이블을 보면, customer_id가 있고, last_update가 눈에 보입니다. ..
코딩/Sql 2019. 12. 2. 18:37
mysql datediff 함수 : 두 날짜의 차이를 일 단위로 리턴해 준다.

mysql의 datediff에 대해서 알아봅시다. 물론, 다른 SQL에서는 1번째 인자로 day의 차이를 구할 것인지, year의 차이를 구할 것인지, 등등을 받습니다. 그러면 몇 일 차이나는지, 몇 달이 차이나는지 등을 구할 수 있을 거에요. 그런데 mySQL에서는 그렇지 않습니다. 2개의 인자만 있는데요. date 2개를 받아서 그 차이를 리턴해 줍니다. DATEDIFF(t1,t2); t1과 t2의 차이를 리턴해 줍니다. t1이 더 이전의 날짜라면, 0, 또는 음수 값이 리턴됩니다. 예제를 몇 개 보고, 실제 sakila 데이터 베이스에서 어떻게 적용할 수 있는지 보도록 하겠습니다. 먼저 아래 쿼리를 작성해 보겠습니다. 2010/8/25와 2011/8/25의 차이를 알고 싶어요. 그런데, 2011년은..
코딩/Sql 2019. 12. 1. 14:49