파이썬 알고리즘 인터뷰 - 연결 리스트 및 연결 리스트 활용

연결 리스트

• 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적 순서대로 저장되지 않는 것을 말한다.
• 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형(ADT) 구현의 기반이 된다.
• 새로운 노드를 삽입, 삭제가 편리하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리하기 편하다.
• 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러 가지 방법으로 다양하게 활용이 가능하다.
• 탐색에는 O(n)이 소요되고 추가, 삭제, 추출 작업에는 O(1) 소요

물리 메모리 여기저기에 배치된 연결 리스트

 

 

런너 기법

• 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법이다.
• 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나, 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다.

 

빠른 런너와 느린 런너

• 다음과 같이 빠른 런너는 두 칸씩 이동, 느린 런너는 한 칸씩 이동하게 된다. 빠른 런너가 연결 리스트의 끝에 도달할 때 느린 런너는 중간 위치에 도달하게 되므로 여기서부터 값을 비교하거나 뒤집기를 시도하는 등 여러가지 연결 리스트 문제에서 활용할 수 있어서 반드시 쓰이는 기법이기도 하다.

 

 

다중 할당

• 파이썬에서 다중 할당은 2개 이상의 값을 2개 이상의 변수에 동시에 할당하는 것을 말한다.

a, b = 1,2  # 다음과 같이 변수 a,b에 1,2를 동시에 할당하는 코드가 이에 해당된다

• 파이썬은 원시 타입(Primitive Type)이 존재하지 않는 대신 모든 것이 객체다. 따라서 = 연산자를 이용해 할당을 진행하게 되면 값을 할당하는 것이 아니라 이 불변 객체에 대한 참조를 할당하게 된다.

id(5) # 4513566608
a = 5
id(a) # 4513566608
b = 5
id(b) # 4513566608

• 다음과 같이 5라는 숫자에 대해 숫자 5와 변수 a,b 모두 동일한 ID를 갖는다. 5라는 값은 메모리 상에 단 하나만 존재하며 a, b 두 변수는 각각 이 값을 가리키는 참조라는 의미이다. 만약 5가 6으로 변경된다면 a, b 두 변수도 값이 6으로 변경 될 것이지만 그런 일은 발생하지 않는다. 숫자는 불변 객체이기 때문이다. 숫자가 아닌 리스트와 같은 가변 객체면 내부 자료값은 얼마든지 변할 수 있다.
• 또한 다중 할당으로 한 번에 처리한 것과 따로 따로 처리한 것의 값과는 다른 결과를 초래 할 수 있다.

 

연산자 우선순위

우선순위	연산자	설명
1	( )	괄호
2	f(args...)	함수 호출
3	x[index:index]	슬라이싱
4	x[index]	배열
5	x.attribute	속성 참조
6	**	지수
7	~x	비트 연산 NOT
8	+x, -x	양수, 음수
9	*, / ,&	곱, 나눗셈, 나머지
10	+, -	덧셈, 뺼셈
11	<<, >>	비트 연산 시프트
12	&	비트 연산 AND
13	^	비트 연산 XOR
14	|	비트 연산 OR
15	in, not in, is, is not, <, <=, >, >=, <>, !=, ==	비교 연산
16	not x	부울 연산 NOT
17	and	부울 연산 AND
18	or	부울 연산 OR
19	lambda	람다 표현

 

변수 스왑

• 두 변수 스왑하는 가장 일반적이고 널리 사용되는 방법은 다음과 같이 임시 변수를 사용하는 방법이다.

tmp = a   # 모든 언어에서 활용할 수 있는 가장 일반적인 방법
a = b
b = tmp


a : int = 1  # 파이썬에서 활용할 수 있는 방법
b : int = 2
a,b = b,a

• 이 방식은 파이썬에서 지원하는 매우 강력한 기능 중 하나로 앞서 설명했던 다중 할당이라고 불리며, 가독성 또한 좋으며 속도적인 면에서도 별 차이가 없다.

swap2(): 0.000183435s
swap3(): 0.000183441s

• 추가로, 숫자형인 경우, 간단한 덧셈, 뺼셈을 통해 임시 변수 없이 스왑하는 방법도 있다. 

x = 9, y = 4
x += y     # 13
y = x - y  # 9
x -= y     # 4

# 3번의 연산 후 x = 4, y = 9가 되었다.
# 이러한 방식은 추가 공간을 필요로 하지 않는다는 이점이 있다.