𝐓𝐨𝐝𝐚𝐲 𝐈 𝐋𝐞𝐚𝐫𝐧 2022.04.04.월

Today I Learn 2022.04.04

---

리스트만 다루다가 딕셔너리를 오랜만에 다루니 기초 문법도 기억이 잘 나지 않았다. 코딩테스트를 위해서라도 딕셔너리를 틈틈히 사용하며 잊지 않도록 해야겠다. hash 이용 방법이 낯설어서 아직은 어려움이 있는거 같다. 다른 사람들의 코드를 익혀 내 것으로 만들어야겠다.

 

Hash - 빠른 검색 O(1)의 속도

---

해시가 무엇? (원리가 무엇인지?) what (그래서 왜, 언제 사용하는지?) why when (그래서 어떻게 사용하는지?) how

빠른 탐색을 위한것.. **DAT**가 있었다.

<DAT의 한계>

• DAT는 음수는 불가 했음! 또한 문자열 저장된 것도 불가 — 인덱스화 시키기 어렵기 때문에
• 또한 메모리의 비효율

Direct Address Table의 upgrade판!

• 해쉬는 DAT의 한계를 어떻게 극복했나?

해시함수 예>

n=int(input()) # n개의 정수 입력
arr=list(map(int,input().split()))
bucket=[0]*10002

def hashf(key):
    return key+100

for i in range(n):
    hashcode=hashf(arr[i])
    bucket[hashcode]=1

그래서 숫자 하나 입력받고 그 숫자가 arr 배열안에 존재 하는지 확인 하고자 한다면?

target=int(input())
getcode=hashf(target)  # 입력받은 값의 해쉬코드를 얻은 후
if bucket[getcode]==1: # dat 검색
    print("있음")
else: print("없음")

*하지만... 해쉬펑션을 어떻게 만들었느냐? 또는 key 값이 무엇이냐에 따라서 충돌이 일어남(collision)*

충돌을 해결하는 방법

---

1. **체이닝 (linked list)** - c/c++ java

hash는 체이닝 된 갯수만 확인하면 되어서 O(n)의 속도가 난다!

1. **오픈 어드레싱** - 충돌이 발생하면 bucket테이블 의 빈공간을 찾아서 해결함으로 오픈 어드레싱 같은 경우에는 key에 따른 value가 자신(key)의 해시코드에 일차하는 주소에 저장하지는 않는다. (루비 파이썬) ( 오픈 어드레싱 방법은 여러가지가 있는데 리니어 탐색 방식으로 예를 들어 드림)

중복이 되어버리면 bucket배열의 빈 공간에 알아서 새로 hash코드를 만들어 주소 값을 할당 받아 자리를 잡아 연결 시키는 방법

 

 

그래서 결론. 해시 언제 사용하냐?

---

1. **리스트 사용할수 없을때 ** 리스트는 정수값으로 된 인덱스로 원소에 접근 하는데 인덱스가 문자열일때는 불가능
2. **데이터에 빠른 접근 및 탐색이 필요할때** 빠른 탐색이 필요할때 사용 (파이썬의 딕셔너리는 O(1)의 속도로 데이터를 저장하고 탐색하고 삭제한다.) 그래서 빠른탐색과 동시에 어떠한 데이터가 몇개 있는지 셀때
3. **하나 더 붙이자면 보안을 강화할때! ** 공공와이파이.. 보안에 상당히 취약..만약에 여기 접속했다! 그러면 이 공유기를 사용하여 전송되는 데이터내용을 모두 볼수 있다. 어떤 사이트에 접속 했는지? 아이디랑 비번은 무엇을 쳤는지 다 확인 노출 가능
4. 카페에서 제공하는 와이파이 이른과 동일하거나 비슷한 이름으로 가짜 와이파이 만든후 사용자가 자신의 공유기에 접속하도록 기다린다.

또는 서울시 등의 지하철의 공공 와이파이의 공유기에 직접 접근하여(해킹)하여 관리자 페이지를 조정하기도 함! 그래서 웹사이트에서는 암호화 기능을 지원한다. 또는 공공장소 공유기의 관리자 페이지로 직접 접근해 관리자 권한으로 와이파이 사용자 정보를 빼오거나 악성프로그램 설치

Dictionary

---

• value출력, value안의 특정 값 출력, key값이 없을 때 '없음!'출력하기

dict1={}
dict2=dict()
hamster={'name':'도토리','age':1,'weight':1}
animals={
    'cat':{'name':'야옹이','age':2,'weight':4,},
    'dog':{'name':'댕댕이','age':12,'weight':8,},
}

print(animals['cat']) #value 출력
print(animals['dog']['name']) #value의 name 출력

 # 키에러 발생 get 사용하면 에러 발생하지 않음
print(animals['cat'].get('nickname','없음!')) 
# nickname이라는 키값 없으면 없음 출력

• 새로운 key,value 추가하기

dict1={}
dict2=dict()
hamster={'name':'도토리','age':1,'weight':1}
animals={
    'cat':{'name':'야옹이','age':2,'weight':4,},
    'dog':{'name':'댕댕이','age':12,'weight':8,},
}

#새로운 key,value추가하기
animals['hamster']= {'name':'토토리','age':1,'weight':1}

• 특정 key값 삭제하기, 없는 key값이면 '없는 key값 출력'

# 딕셔너리 값 삭제  // 1. del   2. pop
dict1={}
dict2=dict()
hamster={'name':'도토리','age':1,'weight':1}
animals={
    'cat':{'name':'야옹이','age':2,'weight':4,},
    'dog':{'name':'댕댕이','age':12,'weight':8,},
    'hamster':{'name':'토토리','age':1,'weight':1}
}

del animals['cat'] #삭제
print(animals)
# del animals['cat'] 을 한번 더 하면 key 값이 없으면 error

#없는 키값이면 '없는 키값'출력
animals.pop('cat','없는 키값') # 없는 고양이를 한번더 삭제시 pop 사용하면 error 안남
print(animals.pop('cat','없음'))

# 딕셔너리에 해당키가 없으면 key에러가 아니라 "없음" 반환한다.
# key 값에 대한 value가 있으면 value 반환.. 그런데 value가 없으면 "없음" 반환
# 그래서 딕셔너리 카운팅 할때에 get 함수 사용하세요~

# 딕셔너리 전부 삭제
animals.clear()
print(animals)

• 특정 key값의 특정value 바꾸기

• dict1={}
  dict2=dict()
  hamster={'name':'도토리','age':1,'weight':1}
  animals={
      'cat':{'name':'야옹이','age':2,'weight':4,},
      'dog':{'name':'댕댕이','age':12,'weight':8,},
      'hamster':{'name':'토토리','age':1,'weight':1}
  }
  
  
  #hamster의 age를 바꾸기
  animals['hamster']['age'] = 101
  #바꾼 hamster age를 출력하기
  print(animals['hamster']['age']) 

• key값만 출력

#키값만 출력
hamster={'name': 3,'age': 2,'weight': 1,}
#방법1
print(hamster.keys())
#방법2
for i in hamster.keys():
    print(i,end=' ')
#방법3
for i in hamster:
    print(i,end=' ')
print()
#방법4
list=(hamster.keys())
print(*list)
print()

• value만 출력

#value만 출력
hamster={'name': 3,'age': 2,'weight': 1,}
#방법1
for i in hamster.values():
    print(i,end=' ')
print()
#방법2
print(hamster.values())
#방법3
list=hamster.values()
print(*list)

• key,value 출력

• hamster={'name': 3,'age': 2,'weight': 1,}
  #방법1
  for i,j in hamster.items():
      print(i,j)
  #방법2
  # 리스트 안에 key와 value가 튜플의 형태로 저장됨
  print(hamster.items()) 
  #방법3
  for i in hamster.items():
      print(*i, sep=':')

• key값 정렬하기(오름차순)

hamster={'name': 3,'age': 2,'weight': 1,}

#방법1
ham1=sorted(hamster.items(),key=lambda item:item[0])
# sorted 함수에 key 옵션을 lambda 로 이용
# 아까와 마찬가지로 리스트 안에 key와 value가 튜플의 형태로 저장이 된다.

#방법2
list=ham1
for i in list:
    for j in i:
        print(j,end=' ')
    print()
    
#방법3
ham2=sorted(hamster.items(),key=lambda item:item[1] )
list=ham2
for i in list:
    for j in i:
        print(j,end=' ')
    print()
    
#그 외
print(sorted(hamster.items(), key=lambda x:x[0]))
print(sorted(hamster.items()))

• value값 정렬하기(내림차순)

#value 값 정렬하기(내림차순)
hamster={'name': 3,'age': 2,'weight': 1,}
# 방법 1
# -item[1] 에 음수 붙이기
ham2=sorted(hamster.items(),key=lambda item:-item[1] )

# 방법 2
 ham2=sorted(hamster.items(),key=lambda item:item[1],reverse=True )

print(sorted(hamster.items(),key=lambda x:-x[1]))#내림차순

연습

나이 - 내림차순, 무게 - 오름차순!

#출력예제
```
name 야옹이
age 12
weight 4
name 댕댕이
age 12
weight 8
name 토토리
age 1
weight 1
```

답

# 나이 내림차순  and 무게 오름차순
animals=[
    {'name': '야옹이','age': 12,'weight': 4,},
    {'name': '댕댕이','age': 12,'weight': 8,},
    {'name': '토토리','age': 1,'weight': 1,}
]
sorted_animal = sorted(animals, key = lambda item : (-item['age'], item['weight']))

for k in range(3):
    dict=sorted_animal[k]
    for i,j in dict.items():
      print(i,j)

animals.sort(key= lambda x: x["weight"])
animals.sort(key= lambda x: x["age"], reverse=True)

for a in animals:
    print("name ", a['name'])
    print("age ", a['age'])
    print("weight ", a['weight']
          

• 4개의 항에 각각 n개의 숫자를 입력받는다. (1<=n<1000)합이 0이 나올 수 있는 경우는 몇가지? - 제한시간 1초
• 4개의 항에서 숫자 1개씩을 뽑아서 모두 더했을 때(숫자4개를 더했을 때)

A = [4,-1,-5,3,2,7]
B = [-4,-31,-5,1,2,3]
C = [24,-61,-5,5,2,-3]
D = [54,-91,-5,6,2,7]

AB = [0]*200
CD = [0]*200
answer = 0

# A,B 의 합들
for i in range(len(A)):
    for j in range(len(B)):
        AB[A[i]+B[j]+100] += 1

# C,D의 합들
for i in range(len(C)):
    for j in range(len(D)):
        CD[C[i]+D[j]+100] += 1

for i in range(200):
    if AB[i] > 0:
        if CD[200-i] > 0:
            answer += AB[i]*CD[200-i]

print(answer) #20

• 투포인터를 이용한 방법

n = int(input())
A, B, C, D = [], [], [], []

for _ in range(n):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

# 투 포인터 사용하기 위해 AB와 CD로 묶어서 정렬
AB_sum = sorted([a+b for a in A for b in B])
CD_sum = sorted([c+d for c in C for d in D])

# 가짓 수, left pointer 초기 값, right pointer 초기 값
sol, left_p, right_p = 0, 0, len(CD_sum) - 1

while left_p < len(CD_sum) and right_p > -1:
    # 현재 포인터가 가리키는 값의 합
    now_sum = AB_sum[left_p] + CD_sum[right_p]
    # 0을 기준으로 확인
    if now_sum < 0:
        left_p += 1
    elif now_sum > 0:
        right_p -= 1
    else:
        # 연속으로 같은 값이 나올 경우
        l_move = 1
        r_move = 1
        while True:
            if left_p < len(AB_sum)-1 and AB_sum[left_p] == AB_sum[left_p + 1]:
                l_move += 1
                left_p += 1
            elif right_p > 0 and CD_sum[right_p] == CD_sum[right_p - 1]:
                r_move += 1
                right_p -= 1
            else:
                sol += l_move*r_move
                left_p += 1
                right_p -= 1
                break
print(sol)

n=6
A=[4, -1, -5, 3, 2, 7]
B=[-4, -31, -5, 1, 2, 3]
C=[24, -61, -5, 5, 2, -3]
D=[54, -91, -5, 6, 2, 7]
bucket1_plus=[0]*201
bucket1_minus=[0]*201

bucket2_plus=[0]*201
bucket2_minus=[0]*201
cnt=0
for i in range(len(A)):
    for j in range(len(B)):
        if A[i]+B[j]>=0:
            bucket1_plus[A[i]+B[j]] +=1
        else:
            bucket1_minus[-(A[i]+B[j])]+=1
for i in range(len(C)):
    for j in range(len(D)):
        if C[i]+D[j]>0:
            bucket2_plus[C[i]+D[j]] +=1
        else:
            bucket2_minus[-(C[i]+D[j])]+=1
            
for i in range(201):
    for j in range(201):
        if bucket1_plus[i] != 0 and bucket2_minus[j] !=0:
            if i-j==0:
                cnt+= bucket1_plus[i]*bucket2_minus[j]
for i in range(201):
    for j in range(201):
        if bucket2_plus[i] != 0 and bucket1_minus[j] != 0:
            if i - j == 0:
                cnt += bucket2_plus[i]*bucket1_minus[j]
print(cnt)