나를 잃지 말자

-Full text search가 가능

->이 말은 토큰 analyer같은게 내장디ㅗ어 있다는 것, document사이 relevancy를 측정할 measure가 있다는 것

->inverted index 사용

구체적으로는 참고자료 inverted index이해하기 참고

요약하면,

row는 field1(term11,term12,...)field2(term21,term22,...),...

column은 document로 document에 대해

term(in each field)의

doc freq(term을 포함하는 document개수),

position(term이 doc내에서 몇번째 token인지)

term freq(term이 각 doc마다 몇번 나타나는가),

offset(term이 doc내에서 몇번째 위치에서 시작하고 끝나는지)

정보를 분석하여 저장해둔다는 것이 핵심

이에 ES는 Standard Analyzer라는 Tokenization기능이 내장되어 있다.

->따라서 NRT(Near Real Time)검색이 가능

-Platform-indenpendent

->RESTful API를 사용하기 때문에

-같은 field명이면 다룬 index에 속하는 document도 한번에 조회가 가능하다.

->검색 특화

다중 Shard의 존재로 병렬처리가 가능

->Scalibility가 존재

단점으로는

-롤백, 트랜잭션 기능이 제공되지 않음(트랜잭션 기능이란게 뭐지?)

-Real Time은 불가능, NRT만 가능, 이는 indexed data는 내부적인 commit/flush같은 과정을 거치기 때문(commit/flush가 뭐지?)

참고자료:

medium.com/@AIMDekTech/what-is-elasticsearch-why-elasticsearch-advantages-of-elasticsearch-47b81b549f4d

cloudingdata.tistory.com/45

deviscreen.tistory.com/17

velog.io/@jakeseo_me/%EC%97%98%EB%9D%BC%EC%8A%A4%ED%8B%B1%EC%84%9C%EC%B9%98-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0-2-DB%EB%A7%8C-%EC%9E%88%EC%9C%BC%EB%A9%B4-%EB%90%98%EB%8A%94%EB%8D%B0-%EC%99%9C-%EA%B5%B3%EC%9D%B4-%EA%B2%80%EC%83%89%EC%97%94%EC%A7%84

참고자료가 너무나 잘 정리되어있다.

핵심은

document2word방식(이를 forward index)의 index를 뒤집어서 word2document(Inverted index)로 저장한다는 것

document를 database에 추가할 때 추가 cost가 들더라도, full text search때 fast하게 하겠다는 것이 목적

inverted file은 word마다 document만 mapping

inverted list은 word마다 document + position정보까지 mapping, 따라서 document를 insert할 때 더 cost가 들긴 하지만 강력한 검색엔진이 됨

참고자료:

cloudingdata.tistory.com/45

en.wikipedia.org/wiki/Inverted_index

-d ->detached mode

-p port1:port2 -> port1으로 받으면 container 내에 port2 service로 접속할 수 있게 설정

-e "STH" -> environment variable 설정

-v: host_dir:container_dir -> host_dir를 container_dir로 mount

-c "CMDs" -> docker 내부에서 commands를 실행하면서 켜짐

mkdir:make directory

  -p:parent 경로가 필요하다면 같이 만듦

tree:현재 경로 내 하위 폴더들의 tree 구조를 보여줌

numpy는 기본적으로 array-wise하게 계산할 때 효율성을 얻는다.

그것을 위해서 다음과 같은 method를 활용하고자 하는데

def aux(x):

  if x:

    return x*np.log(x)

  else:

    return 0

func = np.vectorize(aux)

func(ndarray)

이 때, 사실 array-wise하게 계산하지 않는다.

따라서 large ndarray에 대해서 계산이 느리다.

이 때, 다음과 같이 aux를 수정하고 aux를 그대로 사용하자.

def aux(x):

  return np.where(x > 0, x*np.log(x), 0)

aux(ndarray)

# 하 코테에서 조금만 시간있었으면 해결헀을 텐데, 너무나 짜증난다.

np.select(condition_list, choice_list, default)

x = np.arange(10)

>>> condlist = [x<3, x>5]

>>> choicelist = [x, x**2]

>>> np.select(condlist, choicelist)

array([ 0, 1, 2, 0, 0, 0, 36, 49, 64, 81])

-condition_list에서 여러개  condition을 만족한다면 first encounter condition에 해당하는 choice를 적용함

-default는 어떠한 condition 도 만족하지 않는 경우 output value

ex)

condlist = [

(score_df['average'] >= 90),

(score_df['average'] < 90) & (score_df['average'] >= 80),

(score_df['average'] < 80) & (score_df['average'] >= 70)]

choicelist = ['A','B','C']

score_df['Grade'] = np.select(condlist, choicelist)

문제:www.acmicpc.net/problem/14888

비고:

-Brute force

-next permutation만 있으면 해결됨

-난이도중

문제:www.acmicpc.net/problem/10819

비고:

-Brute force

-다 세지 않고선 규칙을 발견하기 힘들며, 영역 나누기도 힘들어 보이며, 주어진 조건이 가용 시간/메모리 내에 해결 가능

-이런 문제에서 모든 경우를 세기 위해서 next permutation함수를 잘 짜야 한다.

-입력받은 list을 next permutation으로 바꾸며, return은 True/False로 작성

-next permutation을 처음작성하는 거라면 난이도가 있다.

  -기본 규칙은, 배열의 index 0부터(=좌측부터) 우측으로 훑으며 "마지막" 증가(increase)인 index(i)를 찾는다.

  ex) 124653에서 46가 마지막 증가(<)고 4의 index인 2

  -마지막 증가에서의 값보다 크며 가장 우측에 존재하는 값의 index(j)를 찾는다.

  ex) 124653에서 65중에서 5가 더 오른쪽, 5의 index인 4

  -i,j에서의 값 교환

  ex) 124653 -> 125643

  -j보다 우측의 값들을 정렬시킨다.

-난이도중

내소스코드:

boj.kr/33b0cb84fe5d4b48b02c860081023606

문제:www.acmicpc.net/problem/1920

비고:

-Binary search

-문제를 딱보고, 찾아야하는 수를 region에 for문 돌리는 상황생각하면, region 전체를 훑는게 비효율적임을 느껴야한다.

-실무에서도 그냥 search가 자주 일어난다면, 기존 region을 정렬해둬야 함을 알아차려야한다.

-그리고 찾아야하는 것과 region 사이에 대소비교를 할 key field가 필요해야함을 알아야 한다.

-재귀함수를 작성함에 있어서, (성공, 불가능, 오답, 계속) 형태로 작성하자. 즉, 종료하는 케이스가 일찍이 나오게 해줘야 무한 루프에 빠지지 않을 가능성을 높여준다. 

-난이도하

내소스코드:

boj.kr/9016f079aa1344f59b645ee752dc460c

문제:www.acmicpc.net/problem/1912

비고:

-Dynamic programming

-예제2에서 문제 포인트를 알아차려야했는데 놓쳤다.

2 1 -4 3 4 -4 6 5 -5 1 에서 6 5->11이 답이라고 착각하였다. 답은 3 4 -4 6 5로 14다.

-여기서부터 문제를 파악하고 해결해 나가자.

-각 index마다 left max값과 right max값 그리고 index에서의 값을 다 더하고 취합하고 취합한 것에서 max를 구하면 된다.

-각 점마다 left max를 dictionary로 박자. 이 때, index가 작은 순부터 left max를 구하는 것에서 dynamic programming

-0에서는 left max가 0, 1에서는 left max가 0에서의 leftmax + 0에서의 값, 이 때 이 더한 값이 음수면 1에서의 leftmax는 0, 양수면 그 값을 1에서의 left max로 택한다.

-이러면 n번의 계산으로 모든 점에서의 left max를 구한다.

-마찬가지로 n번의 계산으로 모든 점에서의 right max를 구한다.

-문제파악에서 차질이 생겼다. 다음에는 반드시 예제의 정답을 믿자. 예제가 틀렸다고 생각하다니...ㅉㅉ

-게다가 사람들이 많이 푼 문제에 오류가 있다고 생각하면 되겠냐

-난이도중

내소스코드:

boj.kr/12104c7b668241f7b7ef8ee4d6ab8541