[python] list, map, heapq(priority Queue), sorted

markyang92·2021년 7월 30일

python

목록 보기

11/43

List

list 특징

Feature
- Python List는 Stack에 가까운 듯 하다.
  - push 기능 = list.append()
  - pop 기능 = list.pop()이 LIFO
- list[-1] + len(list) = list[+N] 으로 바꿔준다.

선언

``python

list는 import 할 것 없음

a = []
b = list()
c = [1, 2, 3, 4]
d = [1000, 10000, 'Ace', 'Base', 'Captine']
e = [1000, 10000, ['Ace', 'Base', 'Captine']]

print(e[-1])
print(e[2][2])
--- 출력 ---
['Ace', 'Base', 'Captine']
Captine


---

# List 메서드

## `len(list)`: 리스트 길이
```python
a = [1,2,3,4,5]

print( len(a) )

---- 출력 ----
5

`len(list)` 주의점

문자열, 리스트 길이를 구하는 len()은 for문으로 실행되기 때문에 $O(N)$ 을 일단 잡아먹는다.
- 그래서 아래와 같은 경우 ${O(N^2)}$ 이 된다.

따라서 아래와 같이 미리 길이를 구해두어야 혹은 길이는 for문 아래서 즉각 즉각 처리해줘야 $O(N)$

for문 전에 미리 길이 구하기

list_len=len(list)
for i in range(0, list_len):
	# do somthing

dynamic 하게 가변하는 상황에서는

list_len=len(list)
for i in range(0, list_len):
    del list[idx] # for문 내에서 리스트를 삭제 조작 -> list_len에 반영해야함
    list_len-=1

특정 값 초기화 혹은 크기 지정

Python list에서 C, C++ 처럼 memset() 같은 것이 없다. 그래서 여러 방법 중 하나를 선택한다.
- 이 내용의 출처 링크

1. `[내용] * 크기`

arr=([init_value] * size)

arr=([0] * 10)

${1M, 1*10^6}$ 길이시 117 ms
장점: 제일 빠르다.
단점: 1,2,3.. 으로 채우는 순차 채움이 불가

2. `[i for i in range(N)]`

arr = [i for i in range(size)]

${1M, 1*10^6}$ 길이시 612 ms, 방법 1번보다 6배 느림
장점: 1,2,3.. 순차 채울 수 있다.

`a = [0 for i in range(10)]`

arr = [0 for i in range(10)]

print(arr)
==== 출력 ====
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

0 으로 길이 10 list

`a = [i for i in range(10)]`

arr = [i for i in range(10)]

print(arr)
==== 출력 ====
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

0 .. 9 로 채워진 길이 10 list

3. `a.append(value)`

a=list()
for i in range(size):
    a.append(i)

${1M, 1*10^6}$ 길이시 842 ms, 방법 1번보다 8배 느림. 방법 2번보다 200ms 느림

4. 입력이 한 줄로 들어오는 경우

입력 예시
10
8 24 27 18 20 6 17 19 30 11
정석

import sys

readl=sys.stdin.readline
N=int(readl())
A=list(map(int, readl().split())

A=list(map(int, readl().split())

5. 기타 여러가지 list 초기화법

참고: https://velog.io/@markyang92/algorithm-timedecreasing

list comprehension

list comprehension

string = ' '.join( [x for x in string.strip().split() if x.find(pword) == -1 ] )

list.append(): 뒤에 붙이기

a = [1,2,3,4,5]
a.append(6)
print(a)
--- 출력 ---
[1, 2, 3, 4, 5, 6]

`+=` 해도됨

n=20
arr=[-1,0,1,1,2,3,2,3,3,2,3]
#     0,1,2,3,4,5,6,7,8,9,10
if n > 10:
    arr+=([0]*(n-10)) #위 값에서 붙여서 그대로 0으로 채워 append 됨

=== 출력 ===
[-1, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

list.insert(): 특정 idx에 삽입

a=list()
a.insert(idx, val)

a = [1, 2, 3, 4, 5]
a.insert(0,10)
print(a)
--- 출력 ---
[10, 1, 2, 3, 4, 5]

지정 idx 에 삽입되고, 나머지는 뒤로 밀림

list.remove(): '값'을 찾아 제거

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

a.remove(3)
print(a)

=== 출력 ===
[1,2,4,5]

a.remove(3)은 a[3]을 제거하는게 아닌!! value 3이 있는 걸 찾아 제거

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

a.remove(2)

print(a)

=== 출력 ===
[1, 2, 3, 4, 5]

a.remove(2) 해서 2인 값을 모두 제거하는게 아닌!!! value 하나만 제거

del a[idx]: 리스트의 'idx'를 제거

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

del a[0]	
print(a)

=== 출력 ===
[2, 2, 3, 4, 5]

del a[0] => idx 0 번째 제거!

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

del a[-1]
print(a)	# [1, 2, 2, 3, 4]

del a[0:]
print(a)	# []

슬라이싱도 잘먹는다

del a: a 객체 자체 제거

a=list()
del a

del a 로 a 객체 자체를 제거한다.

list.pop(): '맨 마지막' 제거

queue의 FIFO가 아님..!

a = [1, 2, 3, 4]

a.pop()
print(a)

=== 출력 ===
[1, 2, 3]

list.pop(index) 번호를 넣으면, index의 element를 제거!!

순차 탐색 제거

list.count(): value 갯수

a = ['감자', '사과', '사과', '배']

cnt=a.count('사과')

print(cnt)

=== 출력 ===
2

list.index('val'): val의 idx 찾기

<list>.index('val', start index, end index)

리스트 전체에서 val: 2를 찾아 그 index 출력

리스트 전체에서 val: 2를 찾되, start idx: 0, end idx: 3

못찾아서 익셉션 발생 즉, start와 end는 아래와 같다.

못찾으면 바로 Except ValueError

list.reverse() : 뒤집음

list의 함수로 list의 element를 뒤집음
- <list>.reverse(): -> None

A=['a', 'b', 'c']
A.reverse()
print(A)

---- 출력 ----
['c', 'b', 'a']

Slicing

Slicing을 이용한 Shallow copy : https://velog.io/@markyang92/python-copy#shallow-copy

[:]

${0 ≤ idx < len(list)}$

[ 0 : 10 ]

${0 ≤ idx < 10}$

[::-1]

slicing에서 3번째 idx는 step 이다.

[2:0:-1]

for ( int i=2; i > 0; i--)

'`*`' 사용

* 사용

print(*A) 로 리스트 element를 하나씩 띄워 STDOUT에 표시할 수 있다.

물론 slicing도 잘 먹힌다.

# A=['2', '5', '8', '2', '1']
print(*A[0:2])


# ------ 출력 ------- #
2 5

map

map은 Iterable 객체의element를 지정된 함수로 하나 하나 처리, 원본 변경X

list(map(func, input_list)) -> list
tuple(map(func, input_tuple)) -> tuple

map은, 하.나.씩. 매핑 해준다고 생각!

1. float -> int

map 사용
list( func , input: list) -> output: list

for文 없이 간단하게 한 줄로 처리

2. str -> int

3. `N,M=map(int,<'str'>)`

한 str 을 받아서 int인 N,M에 뿌리기

import sys

readl=sys.stdin.readline
N, M=map(int,readl().strip().split())
print(N,M)

2차원 list

$10$ x $10$ list 생성

방법 1.
maps=[]
for i in range(0,10):
    maps.append([])
    maps[i]="i행 내용"
    # e.g., maps[i]=[0]*10

방법 2.
maps=[ [] for _ in range(0,10)]
for i in range(0,10):
    maps[i]="i행 내용"
    # e.g., maps[i]=[0]*10

R=2
C=3
maps=[]
for i in range(R):
    maps.append([])
    for j in range(C):
	maps[i].append((i+1)*(j+1))

그래프 생성

V=N+1
maps=[]
for i in range(0,V):	# 1. Vertex 노드 생성
    maps.append([])

for i in range(0,E):	# 2. 각 Edge 이어주기
    start=sys.stdin.readline()
    end=sys.stdin.readline()
    maps[start].append(end)

예, Vertex=1~7 일 때, Edge를 아래와 같이 주어진다.

# sample edge
7 8
1 2
1 4
1 5
2 3
3 4
3 7
4 6
5 6

----
maps=[]
for i in range(0, V+1):
    maps.append([])
for i in range(0, E):
    get_line=sys.stdin.readline()
    start=get_line[0]
    end=get_line[1]
    maps[start].append(end)

for i in range(0, V+1):
    print(f'maps[{i}]: {maps[i]}').

sort

sorted()

sorted( sorted_target: <type> [, key= <function>] [, reverse= <bool>] ) -> <type>

sorted가 가능한 type:
  <list>, <tuple>, <dict>, <str>
reverse:
  True	내림차순
  False	오름차순

원본이 수정되지 않는다.
1)target 대상을 선정하고 2)소팅 기준값인 Key를 설정하고 이걸 3)reverse할 것인지 정한다.

key 값 설정

dict를 element로 가진 list를 age 오름차순 정렬

def comp(item: dict):
    return item['age'] # 정렬 기준
    
if __name__ == '__main__':
    student1={'name': 'yang', 'age': 28}
    student2={'name': 'kim', 'age': 20}
    
    students=[student1, student2]
    
    students=sorted(students, key=comp)
    print(students)

# === 출력 === #
[{'name': 'kim', 'age': 20}, {'name': 'yang', 'age': 28}]

object를 element로 가진 list를 self.age 순으로 오름차순 정렬

class Student():
    def __init__(self, name:str, age: int):
        self.name=name
        self.age=age

def comp(item):
    return item.age
    
if __name__ == '__main__':
    student1=Student('yang',28)
    student2=Student('kim',20)

    student_list=[student1, student2]

    students=sorted(student_list, key=comp)

    for now_student in students:
        print(now_student.age)
 
 # ====== 출력 ====== #
20
28

key를 lambda로!!

python은 인터프리터 언어로, 한줄에 다 꾸역꾸역 넣는게 속도면 에서 유리
lambda 함수를 어렵게 생각하지 말고, 먼저 위 comp함수에 익숙해지면, 이를 한줄로 옮기기도 쉽다.
- 바로 위 object의 age 순으로 오름 차순을 한다고 생각할 때
  1. comp 함수
```
def comp(item):
    return item.age
```
  1. lambda로 변환 해보자
```
lambda item: item.age
```
  이렇게 쉽게 변환할 수 있다.

students=sorted(student_list, key=lambda item: item.age)

sorted 예제

1. age, name 순 정렬

1순위: age 오름차순
2순위: age가 같을 경우 name의 사전 순

2순위 정렬 후, 1순위 정렬

2. 배열 idx 사전 순

배열 idx別 길이 순

heapq(priority Queue)

python에서 priority queue를 사용하려면, 힙큐를 쓰는게 낫다.

import heapq

heapq는 모든 $k$ 에 대하여, ${a[k]}$ ≤ ${a[2*k+1]}$ && ${a[k]}$ ≤ ${a[2*k+2]}$ 이다.
element는 0 부터 시작한다.
heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap)
heapq는 생성하는 것이 아닌! 일반 list 를 사용한다!

heapq 생성?

heapq는 생성하는 것이 아닌, 기존 list를 관리한다.

import heapq

pq=[]
heapq.heappush(pq, 1)

`heapify()`

heapq.heapify( 리스트 ) 는, 기존 리스트를 min heapify 한다.

heapq.heapify( 리스트 )

pq=[5,4,3,2,1]
heapq.heapify(pq)

사용 예:

`heappush()`

기존 리스트에 heap push 한다.

heapq.heappush( 리스트 , 값)

a=[]
heapq.heappush(a, 1)

만약 기존 리스트가 있고, 이를 heapq로 사용하고 싶다면 반드시!!! 먼저 heapify !

pq=[5,4,3,2,1]
heapq.heapify(pq) # 꼭 기존 리스트에서 heap을 사용하려면, heapify 해야함
heapq.heappush(pq, 6)

`heappop()`

기존 리스트에서 heap pop 한다.

heapq.heappop( 리스트 ) -> value

여러 type을 사용

tuple

tuple의 첫째 값을 기준으로 min heap관리한다.

Max heap 사용

https://hellominchan.tistory.com/231

BFS에서 priority_queue 사용의 예

import heapq

if __name__ == '__main__':
    pq=[]
    heapq.heappush(pq,(1,'hello'))
    while pq:
        prio, val=heapq.heappop(pq)
        print(prio,val)


# ===== 출력 ===== #
1 hello

markyang92

pllpokko@alumni.kaist.ac.kr

이전 포스트

[python] Python의 copy / id / is, is not, bit 연산, shift 연산

다음 포스트