개발뚱땅

큐를 사용해서 조건에 맞게 반복하고, 실행된 횟수를 출력

def solution(priorities, location):
    answer = 0
    wait_list = list(zip(priorities, list(i for i in range(len(priorities)))))
    c = 0
    while wait_list !=0:
        ex = wait_list.pop(0)
        if ex[0] == max(priorities):
            c += 1
            priorities.remove(max(priorities))
            if ex[1] == location:
                return c
        else:
            wait_list.append(ex)
    return answer

옷의 카테고리 별로 옷의 개수를 넣은 사전을 만들고 옷을 안입은 경우를 포함해서 1을 더해주고 모든 조합을 구한다.

안입은경우, 카테고리 내의 옷을 입은경우의 수 곱 반복.

그리고 모두 안입은 경우를 뺀다.

import collections 

def solution(clothes): 
    answer = 1 
    myCounter = collections.Counter(typ for name,typ in clothes) 
    print(myCounter) 
    for num in myCounter.values(): 
        answer *= num+1 
    return answer-1

collections라는 라이브러리를 쓰면 코드가 짧아진다.

문자열.startswith(시작문자열)

문자열이 시작문자열로 시작하는지 알 수 있는 함수

예 'abcd'.startswith('abc') 는 True값 리턴

endswith라는 함수도 있다. 문자열이 인자 문자열로 끝나는지 알 수 있는 함수

n개의 엔트리가 있는 사전이 BST로 표현될 때 Get, Insert, Delete는 O(n) 시간이 걸린다.

이 연산들은 균형 BST를 이용하면 O(log n) 시간 내에 수행된다.

여기서는 Get, Insert, Delete를 O(1) 기대 시간에 수행할 수 있는 기법인 해싱에 대해 살펴본다.

1. 정적해싱

1.1해시 테이블

정적 해싱에서는 키와 값의 쌍이 해시 테이블에 저장된다.

해시 테이블은 ht[0], ..., ht[b-1]과 같이 b개의 버킷으로 분할된다.

각 버킷에 s개의 키 와 값의 쌍이 포함된다.

한 버킷에는 s개의 슬롯으로 구성되며 한 슬롯에는 하나의 사전 쌍을 저장할 수 있다.

보통 s=1이기에 각 버킷은 정확히 하나의 키와 값을 포함한다.

키와 값의 위치는 해시함수에 의해서 결정된다.

이 해시함수는 키값과 버킷을 매핑한다. 즉, 어떤 키값 k를 해시함수에 넣으면 0과 b-1사이의 정수가 된다.

즉, 키 값을 해시함수에 넣었을 때 나온 값을 해시라고 한다.

키 값은 다른데 해시함수에 넣어서 나온 값이 같은 경우 충돌이 일어났다고 한다.

만약 해시값이 같아 같은 버킷에 값이 들어가는데 버킷이 꽉찬경우 오버플로가 발생했다고 한다.

요약하자면, 해싱 기법은 해시함수를 사용하여 키를 해시 테이블의 버킷과 매핑하는 것.

해시함수는 연산이 적으면서 충돌이 최소화 되도록 해야한다.

1.2 해시함수

해시함수는 키를 해시테이블 내의 버킷에 매핑한다.

임의의 키 k를 해시함수에 넣었을 때 나오는 값의 확률이 균일한 것이 좋다. 즉 각 버킷에 배정될 확률이 균일.

이런 특성을 만족하는 해시 함수를 균일 해시함수라고 한다.

다양한 종류의 해시함수가 사용되는데 그 중 일부는 산술 연산을 통해서 계산한다.

많은 응용에서는 키의 데이터타입이 스트링과 같아서 산술 연산을 할 수 없는 경우도 있다. 이럴 땐 키를 정수와 같이 산술 연산이 가능한 데이터 타입으로 변환한 뒤 연산을 수행한다.

다음은 많이 사용되는 해시함수에 대해 소개한다.

1.2.1 division 함수

division함수는 실제로 가장 많이 씅이는 해시함수로 키 값이 음이 아닌 정수라고 가정한다.

해시 값은 mod(%)연산자에 의해 결정된다.

즉, 키를 어떤 정해진 수로 나눈 나머지 값을 해시값으로 사용하는 것이다.

h(key) = key % D;

이 때 버킷의 범위는 0~D-1이고 테이블에는 D개의 버킷이 있어야한다.

D의 선택이 오버플로 발생에 큰 영향을 미친다. 만약 D가 짝수라면 홀수 값을 가진 키들은 모두 나머지가 홀수이므로 홀수 버킷에 사상될 것이고 짝수 값을 가진 키들은 짝수 버킷에 매핑될 것이다.

최상의 성능을 내기 위해서는 소수인 D를 선택해야한다.

1.2.5 스트링 키를 정수로 변환하기

위의 해시함수를 쓰려면 키를 먼저 0 또는 자연수로 변환해야한다.

스트링을 16비트 정수로 매핑하는 방법

unsigned int StringToInt(string s)

{

    int length = (int)s.length();//스트링의 문자 수

    unsigned int answer = 0;

    if(length % 2 == 1)

    {

        answer = s.at(length-1);

        length--;

    }

    for(int i = 0; i<length;i+=2)

    {

        answer += s.at(i);

        answer += ((int)s.at(i+1))<<8;

    }

    return answer;

}

위 함수에서는 문자의 쌍을 유일한 정수로 변환한 뒤 이 유일한 정수들을 모두 더한다.

모든 문자들을 8비트씩 이동시키지 않고 더하면 8비트 이하의 정수가 생성되기 때문에 쉬프트하여 더한다.

C++ STL은 T타입의 개체를 음이아닌 정수 size_t로 변환시키는 hash<T>라는 STL템플릿 클래스를 제공한다.

이러한 템플릿 클래스를 사용하여 스트링 값을 음이아닌 정수로 변환하면 된다.

1.3 안전 해시 함수

해시함수는 컴퓨터 보안 분야에서도 사용된다.

메시지 인증이 그런 응용 중 하나이다.

메시지 M이 보안없는 채널을 통해 A에서 B로 전송된다고 할 때.

메시지와 H(msg)값을 함께 보내고 B는 받은 메시지를 해시함수에 넣어서 받은 해시값과 일치하는지 확인하여 원본임을 인증할 수 있다.

하지만 해시 충돌이 일어나지 않도록 해야한다.

이런 특성을 약한 충돌 저항이라고 한다.

해시값을 보고 해시함수에 넣은 값을 알아내기 힘든 특성을

단방향 특성이라고 한다.

h(x)=h(y)인 x, y쌍을 계산을 통해 찾기 힘들게 하는 특성을

강한 충돌 저항이라고 한다.

1.4 오버플로우 처리

오버 플로우를 처리하는 방법에는 open addressing과 chaining이 있다.

DATE_FORMAT함수를 아는지 확인하는 문제.

SELECT ANIMAL_ID, NAME, DATE_FORMAT(DATETIME, "%Y-%m-%d") AS 날짜 FROM ANIMAL_INS ORDER BY ANIMAL_ID;

DATEDIFF함수 아는지 확인하는 문제.

첫번째 인자 - 두번째 인자를 반환.

SELECT O.ANIMAL_ID, O.NAME FROM ANIMAL_OUTS O, ANIMAL_INS I WHERE O.ANIMAL_ID = I.ANIMAL_ID ORDER BY DATEDIFF(O.DATETIME, I.DATETIME) DESC LIMIT 2;

if문 사용할 수 있는지 확인하는 문제. true면 두번째 인자가 리턴, false면 세번째 인자가 리턴.

SELECT ANIMAL_ID, NAME, IF(SEX_UPON_INTAKE LIKE 'Neutered%' OR SEX_UPON_INTAKE LIKE 'Spayed%', 'O', 'X') AS 중성화 FROM ANIMAL_INS ORDER BY ANIMAL_ID;

LIKE프레디킷은 서브 스트링 패턴을 비교하는 비교연산자로 사용된다.

'%'는 문자가 있거나 없을 수 있다는 의미.

'_'는 문자 하나를 나타낸다.

SELECT ANIMAL_ID, NAME FROM ANIMAL_INS WHERE NAME LIKE '%EL%' AND ANIMAL_TYPE='Dog' ORDER BY NAME;