728x90
연결 리스트
- 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적 순서대로 저장되지 않는 것을 말한다.
- 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형(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가 되었다.
# 이러한 방식은 추가 공간을 필요로 하지 않는다는 이점이 있다.
'알고리즘 공부 > 파이썬 알고리즘 인터뷰' 카테고리의 다른 글
파이썬 알고리즘 인터뷰 - 데크, 우선순위 큐 (0) | 2022.02.03 |
---|---|
파이썬 알고리즘 인터뷰 - 스택, 큐 (0) | 2022.02.02 |
파이썬 알고리즘 인터뷰 - 배열, 투 포인터 기법, 최댓값과 최솟값 (0) | 2022.01.30 |
파이썬 알고리즘 인터뷰 - 문자열 조작 (0) | 2022.01.30 |
파이썬 알고리즘 인터뷰 - 리스트, 딕셔너리 (1) | 2022.01.22 |