1. 정렬

정렬이란 데이터를 순서대로 나열하는 방법

1) 버블 정렬

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식

작은 숫자, 큰 숫자 순서로 있으면 내버려두고
큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경

2) 선택 정렬

주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

3) 병합 정렬

병합 정렬은 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘

2. 스택

한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조.
[컴퓨터인터넷IT용어대사전]

3. 큐

한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조.
[컴퓨터인터넷IT용어대사전]

4. 해쉬

해쉬 테이블(Hash Table)은 "키" 와 "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조

해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수

해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장

그렇기 때문에 즉각적으로 데이터를 찾고, 추가가능

만약, 해쉬 값 혹은 인덱스가 중복되어 충돌 발생시,
체이닝과 개방 주소법 방법으로 해결

몰랐던 개념

swap in python

a,b = b,a

하면 a 값과 b 값이 swap됨
배열의 요소들도 swap 가능 array[i], array[i+1] = array[i+1], array[i]

>>> a = 3
>>> b = 4
>>> a, b = b, a
>>> print(a)
4
>>> print(b)
3

while 리스트:

while array:는 array가 빈 상태가 아닐 때 까지 반복한다는 뜻이다.

def get_receiver_top_orders(heights): # 총 시간 복잡도 O(N^2)
    answer = [0]*len(heights)
    while heights: # heights가 빈 상태가 아닐 때 까지 O(N)
        height = heights.pop()
        for idx in range(len(heights)-1, 0, -1): #O(N)
            if heights[idx] > height:
                answer[len(heights)] = idx+1
                break
    return answer

range 거꾸로

큰 수에서 작은 수로 index를 바꿔가며 반복하고 싶을때
for i in range(시작점(제일 큰 수), 끝점(제일 작은수-1), -n)
range는 끝점의 직전까지 i에 넣고 반복하고, n은 시작점에서 끝점에 도달하기 까지 마이너스할 양을 의미

아래 코드는 5부터 시작해서 0직전까지 -1만큼 반복

>>> for idx in range(5, 0, -1): print(idx)
5
4
3
2
1

sort 함수

sort : 정렬, 기본값은 오름차순 정렬, reverse옵션 True는 내림차순 정렬

>>> a = [1, 10, 5, 7, 6]
>>> a.sort()
>>> a
[1, 5, 6, 7, 10]
>>> a = [1, 10, 5, 7, 6]
>>> a.sort(reverse=True)
>>> a
[10, 7, 6, 5, 1]

reverse 함수

reverse : 리스트를 거꾸로 뒤집는다. desc 정렬이 아님

>>> a = [1, 10, 5, 7, 6]
>>> a.reverse()
>>> a
[6, 7, 5, 10, 1]

딕셔너리 관련 함수들

Key 리스트 만들기(keys)

a.keys()는 딕셔너리 a의 Key만을 모아서 dict_keys 객체를 돌려준다.

>>> a = {'name': 'pey', 'phone': '0119993323', 'birth': '1118'}
>>> a.keys()
dict_keys(['name', 'phone', 'birth'])

dict_keys 객체는 다음과 같이 사용할 수 있다. 리스트를 사용하는 것과 차이가 없지만, 리스트 고유의 append, insert, pop, remove, sort 함수는 수행할 수 없다.

>>> for k in a.keys():
...    print(k)
...
name
phone
birth

dict_keys 객체를 리스트로 변환하려면 다음과 같이 하면 된다.

>>> list(a.keys())
['name', 'phone', 'birth']

Value 리스트 만들기(values)

Key를 얻는 것과 마찬가지 방법으로 Value만 얻고 싶다면 values 함수를 사용하면 된다. values 함수를 호출하면 dict_values 객체를 돌려준다.

>>> a.values()
dict_values(['pey', '0119993323', '1118'])

Key, Value 쌍 얻기(items)

items 함수는 Key와 Value의 쌍을 튜플로 묶은 값을 dict_items 객체로 돌려준다. dict_values 객체와 dict_items 객체 역시 dict_keys 객체와 마찬가지로 리스트를 사용하는 것과 동일하게 사용할 수 있다.

>>> a.items()
dict_items([('name', 'pey'), ('phone', '0119993323'), ('birth', '1118')])

Key: Value 쌍 모두 지우기(clear)

clear 함수는 딕셔너리 안의 모든 요소를 삭제한다. 빈 리스트를 [ ], 빈 튜플을 ( )로 표현하는 것과 마찬가지로 빈 딕셔너리도 { }로 표현한다.

>>> a.clear()
>>> a
{}

Key로 Value얻기(get)

get(x) 함수는 x라는 Key에 대응되는 Value를 돌려준다. 앞에서 살펴보았듯이 a.get('name')은 a['name']을 사용했을 때와 동일한 결괏값을 돌려받는다.

다만 다음 예제에서 볼 수 있듯이 a['nokey']처럼 존재하지 않는 키(nokey)로 값을 가져오려고 할 경우 a['nokey']는 Key 오류를 발생시키고 a.get('nokey')는 None을 돌려준다는 차이가 있다. 어떤것을 사용할지는 여러분의 선택이다.

>>> a = {'name':'pey', 'phone':'0119993323', 'birth': '1118'}
>>> a.get('name')
'pey'
>>> a.get('phone')
'0119993323'

해당 Key가 딕셔너리 안에 있는지 조사하기(in)

'name' 문자열은 a 딕셔너리의 Key 중 하나이다. 따라서 'name' in a를 호출하면 참(True)을 돌려준다. 반대로 'email'은 a 딕셔너리 안에 존재하지 않는 Key이므로 거짓(False)을 돌려준다.

>>> a = {'name':'pey', 'phone':'0119993323', 'birth': '1118'}
>>> 'name' in a
True
>>> 'email' in a
False

딕셔너리 안의 값으로 정렬하기(sorted, lambda)

sorted 함수는 items라는 배열을 받고, key라는 lambda라는 함수를 받는다. lambda의 의미는 item을 받아서 item[1]값으로 정렬하겠다는 의미
lambda 특정 인자를 받아서 어떤 값으로 돌려줄 건지를 간단한 수식으로 표현하는 함수

>>> a = {"fast":33, "slow":22}
>>> a.items()
dict_items([('fast', 33), ('slow', 22)])
>>> sorted(a.items(), key=lambda item:item[1])
[('slow', 22), ('fast', 33)]
>>> sorted(a.items(), key=lambda item:item[0])
[('fast', 33), ('slow', 22)]
>>> sorted(a.items(), key=lambda item:item[0], reverse=True)
[('slow', 22), ('fast', 33)]

reverse=True하면 내림차순으로 정렬