Python에서 in 연산자의 시간 복잡도에 대해서 알아보자

환경 및 선수조건

• Python(3.X)

파이썬 in 연산

• 파이썬 in연산자란 멤버십 연산자로 문자열이나 리스트나 튜플과 같이 연속적인 자료구조에 속한 멤버를 확인하기 위한 연산자입니다.

기본 사용법

list

l = [1, 2, 3, 4, 5]

# 멤버 확인
if 1 in l :
    print("1 is in l")

# 순회
for i in l :
    print(i)

tuple

t = (1, 2, 3, 4, 5)

# 멤버 확인
if 1 in t :
    print("1 is in t")

# 순회
for i in t :
    print(i)

set

s = {1, 2, 3, 4, 5}

# 멤버 확인
if 1 in s :
    print("1 is in s")

# 순회
for i in s :
    print(i)

dictionary keys

d = {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e'}

# 멤버 확인
if 1 in d.keys() :
    print("1 is in d keys")

# 순회
for i in d.items() :
    print(i)

시간 복잡도

list, tuple

• Average: O(n)
• 하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 됩니다.

set, dictionary

• Average: O(1), Worst: O(n)
• 내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도가 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다.

참고자료

• https://wiki.python.org/moin/TimeComplexity
• https://stackoverflow.com/questions/13884177/complexity-of-in-operator-in-python
• https://www.ics.uci.edu/~brgallar/week8_2.html

Python에서 리스트를 슬라이싱해서 이용하는 방법을 알아보자

환경 및 선수조건

• Python(3.X)

파이썬 슬라이싱(slicing)이란?

• 슬라이싱(slicing) or 슬라이스(slice): 연속적인 객체들에(예: 리스트, 튜플, 문자열) 범위를 지정해 선택해서 객체들을 가져오는 방법 및 표기법을 의미합니다.
• 슬라이싱을 하면 새로운 객체를 생성하게 됩니다. 즉, 일부분을 복사해서 가져온다고 생각하면 됩니다.

기본 사용법과 형태

기본 형태

• a라는 연속적인 객체들의 자료구조(예: 리스트, 튜플, 문자열)가 있다고 가정을 했을 때 기본 형태는 아래와 같습니다.

a[start : end : step]

• 각각 start, end, step 모두 양수와 음수를 가질 수 있습니다.
• start: 슬라이싱을 시작할 시작위치입니다.
• end: 슬라이싱을 끝낼 위치로 end는 포함하지 않습니다!
• step: stride(보폭)라고도 하며 몇개씩 끊어서 가져올지와 방향을 정합니다. 옵션이며 아래의 예제를 확인하면 쉽게 이해가 가능합니다.

인덱스 값들의 위치

• 위에 설명한대로 값들은 양수 혹은 음수를 가질 수 있습니다.
• 양수: 연속적인 객체들의 제일 앞에서부터 0을 시작으로 번호를 뒤쪽으로 증가하면서 매깁니다.
• 음수: 연속적인 객체들의 제일 뒤에서부터 -1을 시작으로 번호를 앞쪽으로 감소하면서 매깁니다.
• 아래는 ['a', 'b', 'c', 'd', 'e']라는 리스트가 있을 때 인덱스를 의미합니다.

a = ['a', 'b', 'c', 'd', 'e']

// Index References
-------------------------------
|  a  |  b  |  c  |  d  |  e  |
-------------------------------
|  0  |  1  |  2  |  3  |  4  |          // 양수의 경우
-------------------------------
| -5  | -4  | -3  | -2  | -1  |          // 음수의 경우
-------------------------------

예제

• 기본적으로 모든 예제들은 a = ['a', 'b', 'c', 'd', 'e']의 리스트를 통해서 작성하겠습니다.

특정 시작위치부터 끝까지 가져오기

• a[ start : ]

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ 1 :  ]
['b', 'c', 'd', 'e']

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ -3 :  ]
['c', 'd', 'e']

시작점부터 특정 위치까지 가져오기

• a[ : end ]

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[  : 2 ]
['a', 'b']

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[  : -1 ]
['a', 'b', 'c', 'd']

특정 위치부터 특정 위치까지 모두 가져오기

• a[ start : end ]

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ 2 : 4 ]
['c', 'd']

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ -4 : -2 ]
['b', 'c']

>>> a = ['a', 'b', 'c', 'd', 'e']
# 인덱스 1 ~ 3까지의 값을 거꾸로 가져오기
>>> a[ 3 : 0 : -1]
['d', 'c', 'b']

step의 예제

• a[ start : end : step ]
• step이 양수일 때: 오른쪽으로 step만큼 이동하면서 가져옵니다.
• step이 음수일 때: 왼쪽으로 step만큼 이동하면서 가져옵니다.

>>> a = ['a', 'b', 'c', 'd', 'e']
# 2칸씩 이동하면서 가져옵니다.
>>> a[ : : 2 ]
['a', 'c', 'e']

>>> a = ['a', 'b', 'c', 'd', 'e']
# 3칸씩 이동하면서 가져옵니다.
>>> a[ -5 : : 3 ]
['a', 'd']

>>> a = ['a', 'b', 'c', 'd', 'e']
# 전체를 거꾸로 가져옵니다.
>>> a[ : : -1 ]
['e', 'd', 'c', 'b', 'a']

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ 3 : : -1 ]
['d', 'c', 'b', 'a']

참고자료

• https://stackoverflow.com/questions/509211/understanding-pythons-slice-notation
• https://docs.python.org/3/library/functions.html?highlight=slice#slice

업데이트(2021.04.18): 내용과 예시 추가

Python에서 리스트에 있는 튜플이나 클래스를 통해서 생성한 객체를 정렬하는 방법을 알아보자.

환경 및 선수조건

• Python(3.X)

sort()함수와 sorted()함수

• Python에서 제공하는 정렬함수는 기본적으로 stable을 보장한다. (관련문서)

sort()

• sort(): 현재 리스트를 정렬

a = [3,5,7,8,2,6]
a.sort()

sorted()

• sorted(): 함수의 인자로 들어온 리스트를 정렬해서 반환

a = [3,5,7,8,2,6]
b = sorted(a) # b에 정렬된 리스트가 새로 생성됨

key 매개변수 이용하기

• key매개변수를 이용하여 비교하기전에 함수를 정의 할 수 있다.
• key매개변수는 하나의 인자를 갖는 함수여야하며 정렬에 사용할 key를 반환해야한다.

튜플(tuple)을 사용하는 경우

• 사용 예시

example_tuples = [ ('A', 3, 'a'), ('B', 1, 'b'), ('C', 2, 'c') ]

# 정렬
# 튜플의 2번째 원소 기준으로 정렬
example_tuples.sort(key = lambda element : element[1])

print(example_tuples)

• 결과

[('B', 1, 'b'), ('C', 2, 'c'), ('A', 3, 'a')]

객체(Object)를 사용하는 경우

• 사용 예시

class Example:
	def __init__(self, big, number, small):
		self.big = big
		self.number = number
		self.small = small

example_objects = [ Example('A', 3, 'a'), Example('B', 1, 'b'), Example('C', 2, 'c') ]

# 정렬
# 객체의 number 속성을 기준으로 정렬
example_objects.sort(key = lambda object : object.number)

for example_object in example_objects:
    print(example_object.big
          + " " + str(example_object.number)
          + " " + example_object.small)

• 결과

B 1 b
C 2 c
A 3 a

정렬 관련 기타

내림차순 정렬

• sort( reverse=True ): 현재 리스트를 내림차순으로 정렬

a = [3,5,7,8,2,6]
a.sort(reverse=True)

print(a)

[8, 7, 6, 5, 3, 2]

참고자료

• https://docs.python.org/3/howto/sorting.html

Python에서 is와 ==의 차이를 알아보자

환경 및 선수조건

• Python

is와 ==의 차이

• is는 변수가 같은 Object(객체)를 가리키면 True
• ==는 변수가 같은 Value(값)을 가지면 True

‘is’의 예시

• a와 b는 같은 리스트 객체를 가리킨다.
• a와 b는 같은 객체이기 때문에 True
• a와 c는 값은 같지만 다른 객체이기 때문에 False

>>> a = [1,2,3]
>>> b = a
>>> c = [1,2,3]
>>> a is b
True
>>> a is c
False

’==’의 예시

• a와 b는 같은 리스트 객체를 가리킨다.
• a와 b는 값들을 가진 리스트이기 때문에 True
• a와 c는 값들을 가진 리스트이기 때문에 True

>>> a = [1,2,3]
>>> b = a
>>> c = [1,2,3]
>>> a == b
True
>>> a == c
True

참고자료

• https://stackoverflow.com/questions/132988/is-there-a-difference-between-and-is-in-python

해시 테이블에서 문자열을 받았을 때 해싱하는 방법을 알아보자

환경 및 선수조건

• C++
• Hash의 개념
• Hash Table의 개념

String을 Key값으로 받았을 때

• 1번의 방식은 단순하나 중복이 될 가능성이 크며 2~3번의 방식이 분포를 더 크게 만들 수 있다.
• 만약 연산중에 혹은 결과 값이 해시 테이블의 크기보다 크다면 해시 테이블의 크기만큼 나누어서 나머지의 값을 취하면 된다.

1. 문자열에 있는 문자들을 모두 더하기

• 문자열에 있는 문자들을 다 더해서 계산하는 방식
• 단, 아래와 같은 경우에는 “abc”, “acb” 그리고 “cba”의 결과가 모두 같다는 단점이 있다. 즉 hashCode("abc")==hashCode("acb")==hashCode("cba")

int hashCode(String s){
	int r = 0;

	for(int i = 0; i < s.length(); i++){             
		 r += s[i];
	}

	return r;
}

2. 다항식을 이용해서 구하기

• h(s) = xk-1 × ak-1 + xk-2 × ak-2 + ... + x0 × a0와 같은 다항식을 바탕으로 만드는 방식
• 특정한 값 a(일반적으로 소수가 좋다고 한다.)를 곱하고 문자열에 있는 문자를 더하면서 완성해가는 방식

int hashCode(String s){
	int i;
	int r = 0;

	// Special Prime Number
	int a = 33;

	for(i = 0; i < s.length(); i++){
		 r += r*a + s[i];   
	}

	return r;
}

3. 시프트(Shift) 연산자를 이용해서 구하기

• 위에 2번에 있는 다항식의 방법과 똑같은데 시프트(Shift)연산을 이용해서 값을 곱하는 방식

int hashCode(String s){
	int i;
	int r = 0;

	for(i = 0; i < s.length(); i++){
		 r += (r<<4) + s[i];   
	}

	return r;
}

참고자료

• http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/hash-func.html