리스트 함수 정리

이번 포스팅은 파이썬 기본 리스트의 내장 함수들을 정리했습니다. 리스트는 삽입, 삭제, 인덱스 위치 찾기, 원하는 원소 갯수 찾기, 정렬 등이 기본적으로 제공됩니다.

>>> 구문이 있는 명령어는 ide상에서의 실행이 아닌 파이썬 내에서 실행 코드입니다.

삽입

1. append()

A.append(x)는 리스트 A 끝에 원소 x를 추가한다. A[len(A):] = [x] 로 사용도 가능하다. 시간복잡도는 O(1)이다.

>>> A = [1, 2, 3]
>>> A.append(4)
>>> A
[1, 2, 3, 4]
>>> A[len(A):] = [5]
>>> A
[1, 2, 3, 4, 5]

2. extend()

A.extend(iter)는 iterable한 항목 iter를 리스트 A에 추가한다. 여러 개의 리스트를 서로 연결할 때 사용된다. 혹은 A += iter로 사용이 가능하다.

>>>A = [1, 2, 3]
>>>B = [4, 5, 6]
>>>A.extend[B]
A
[1, 2, 3, 4, 5, 6]
>>>A += [7, 8, 9]
A
[1, 2, 3, 4, 5, 6, 7, 8, 9]

3. insert()

A.insert(i, x)는 리스트 A의 i 위치에 x를 삽입하는 함수이다. i 이후의 모든 원소들을 한 칸씩 옮겨야 하기 때문에 시간복잡도는 O(N)이 된다.(N은 리스트의 길이)

>>> A = [1, 2, 3]
>>> A.insert(1, 4)
>>> A
[1, 4, 2, 3]

원소 제거

1. remove()

A.remove(x)는 리스트의 원소 x를 제거한다. x는 원소의 인덱스가 아닌 원소의 값이다. x가 존재하지 않으면 ValueError가 발생한다. 시간복잡도는 O(N)이다.

>>> A = [1, 2, 3]
>>> A.remove(2)
>>> A
[1, 3]

2. pop()

A.pop(i)는 리스트의 i번째 원소를 제거하면서 해당 원소를 반환한다. remove와는 다르게 위치에 있는 값을 제거하는 함수이고 i를 지정하지 않으면 리스트의 마지막 원소를 제거하면서 반환한다. i를 지정하지 않은 경우 시간복잡도는 O(1)이고 i를 지정한 경우 시간복잡도가 O(N)이 된다.

>>> A = [1, 2, 3]
>>> A.pop(1)
2
>>> A
[1, 3]
>>> A.pop()
3
>>> A
[1]

3. del문

del문은 pop처럼 인덱스를 지정해서 항목을 삭제한다. pop과 다른 점은 삭제한 원소를 반환하지 않는 것이다. 리스트 슬라이싱을 통해서 여러개의 원소를 한 번에 삭제도 가능하다. 시간복잡도는 O(N)이다.

>>> A = [1, 2, 3, 4, 5, 6]
>>> del A[2]
>>> A
[1, 2, 4, 5, 6]
>>> del A[1:3]
>>> A
[1, 5, 6]

이외 함수들

index()

A.index(x)는 리스트 A에서 원소 x의 위치를 반환한다. 이 때 주의할 점은 리스트 A에 x가 여러 개가 있다면 가장 앞에 있는 인덱스를 반환하다. 시간 복잡도는 리스트를 순차적으로 모두 확인하므로 O(N)이 된다.

>>> A = [1, 2, 3, 4, 5]
>>> A.index(3)
2

count()

A.count(x)는 리스트 A에 x인 값을 갖는 원소의 개수를 반환한다. 시간복잡도는 O(N)이다.

>>> A = [1, 2, 2, 3, 3, 3]
>>> A.count(3)
3

sort()

A.sort(key, reverse)는 리스트 A를 값을 기준으로 오름차순으로 정렬해준다. 시간복잡도는 O(NlogN)이고 내림차순으로 정리하려면 reverse=True를 인자로 주어야 한다. 원하는 기준으로 정렬을 해주고 싶다면 key와 lambda를 사용하여 규칙을 정해주어야 한다.

>>> A = [4, 1, 3, 2]
>>> A.sort()
>>> A
[1, 2, 3, 4]
>>> A.sort(reverse=True)
>>> A
[4, 3, 2, 1]

reverse()

A.reverse()는 리스트 A의 원소들을 반전시켜서 다시 리스트 A에 저장한다. list[::-1]을 하는 것과 같다.

>>> A = [1, 2, 3, 4, 5]
>>> A.reverse()
>>> A
[5, 4, 3, 2, 1]

[백준][파이썬] 17406번 - 배열 돌리기 4

문제 번호 : 17406번 - 배열 돌리기 4
문제 출처 : https://www.acmicpc.net/problem/17406

Code

from itertools import permutations

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
val = []


def matrix_value(ans):
    for i in range(n):
        ans = min(ans, sum(matrix[i]))
    return ans


def rotate(rcs):
    r, c, s = rcs
    for i in range(1, s+1):
        tmp = matrix[r - 1 - i][c - 1 - i]
        x = r - i - 1
        y = c - i - 1
        for j in range(4):
            for k in range(2*i):
                nx = x + dx[j]
                ny = y + dy[j]
                matrix[x][y] = matrix[nx][ny]
                x, y = nx, ny
        matrix[r-1-i][c-i] = tmp


n, m, k = map(int, input().split())
a = [[] for _ in range(n)]
for h in range(n):
    a[h] = list(map(int, input().split()))
rotation = [[] for _ in range(k)]
for i in range(k):
    rotation[i] = list(map(int, input().split()))
answer = 1e9
orders = permutations(rotation)

for order in orders:
    matrix = [a[row][:] for row in range(n)]
    for rcs in order:
        rotate(rcs)
    answer = matrix_value(answer)

print(answer)

Idea

1. 회전하는 경우의 수를 순열을 통해서 구한다. K의 최대값이 6이기 때문에 6! = 720개의 경우가 만들어진다.
2. 각 경우의 수마다 배열을 복사하고 회전을 시킨 후 각 행마다 최솟값인지 확인한다.

[백준][파이썬] 17089 - 세 친구

문제 번호 : 17089번 세 친구
문제 출처 : https://www.acmicpc.net/problem/17089

Code

import sys

n, m = map(int, input().split())
relations = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

friends = [set() for _ in range(n)]
for relation in relations:
    friends[relation[0]-1].add(relation[1])
    friends[relation[1]-1].add(relation[0])

num_friends = m
for a in range(n):
    for b in friends[a]:
        for c in friends[b-1]:
            if c in friends[a]:
                num_friends = min(num_friends, len(friends[a]) + len(friends[b-1]) + len(friends[c-1]) - 6)
if num_friends < m:                
    print(num_friends)
else:
    print(-1)

Idea

1. 입력된 친구가 모두 A, B, C의 친구인 경우 세 친구의 친구 수 합의 최대는 m - 6이다.
2. A를 정하고 B는 A의 친구 중 한명이고 C는 B의 친구이면서 A의 친구인 경우에서 친구 수의 최소값을 찾아낸다.
3. b > a, c > b 조건을 넣은 이유는 먼저 순회한 조합을 순회하지 않기 위함이다. 이 두 조건이 없다면 순열처럼 동작할 것이지만 이 조건으로 인해서 조합이 되어서 시간 복잡도가 줄어든다. 이 조건 두 줄만으로 1880ms에서 92ms로 시간이 확 줄었다.

[백준][파이썬] 2422번 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

문제 번호 : 2422
문제 출처 : https://www.acmicpc.net/problem/2422

Code

import sys

n, m = map(int, input().split())
answer = n * (n - 1) * (n - 2) // 6
nomat = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    answer -= (n-2) - len(nomat[a-1] | nomat[b-1])
    nomat[a-1].add(b)
    nomat[b-1].add(a)

print(answer)

Idea

1. 초기 answer 값은 ${}_n{\mathrm{C}}_3$ 을 수로 나타낸 것이다.
2. nomat 리스트에는 각 맛 별로 조합이 좋지 않은 맛을 넣는다.
3. 2 가지가 정해진 상황에서 나머지 한 가지 맛을 고르는 경우의 수는 n - 2 이다.
4. 그 전에 경우의 수에서 없앤 경우의 수는 합집합의 길이가 된다.

예제 입력을 넣었을 때를 예시로 들면 다음과 같다.

    1. 모든 경우의 수는 5가지 맛 중 3가지를 뽑는 경우로 총 10이다.  
    2. 처음 (1, 2, X) 를 뽑는 경우의 수는 3가지이므로 전체 경우의 수에서 3을 빼준다.  
    3. (3, 4, X) 를 뽑는 경우의 수 중 전에 뽑은 경우가 없으므로 `nomat\[2\]`와 `nomat\[3\]`의 합집합의 길이는 0이다.  
    4. (1, 3, X) 를 뽑는 경우에는 (1, 2, 3) 인 경우와 (1, 3, 4) 인 경우를 그 전의 입력에서 뺐으므로 전체 경우의 수에서 1만 빼준다.

처음에 코드 제출했을 때는 파이썬 언어에서 시간 순위 1등이었는데 글 적을 때 되니까 밀려났다.

자료구조 with Python : Stack(스택)

스택(Stack)은 마지막에 들어온 데이터가 가장 먼저 나가게 되는 후입선출(LIFO)의 자료구조이다. 스택도 결국에는 리스트의 특별한 케이스일 뿐이다. 입력과 출력이 한 쪽 끝단에서만 이루어진다.

스택의 구조

스택은 가장 위의 데이터를 알리는 top, 스택에 데이터를 삽입하는 push, top의 데이터를 내보내는 pop함수가 기본적인 구성이다. 이 외에도 peak나 is_empty를 구현하기도 하지만 이건 부수적인 것일 뿐이다.

Push(item)

push는 아이템을 스택에 삽입하는 함수이다. top은 1 증가시키고 top이 가리키는 위치에 아이템을 저장한다.

Pop()

pop은 아이템을 스택에서 꺼내는 함수이다. 단순 참조가 아니라 스택에서 아예 나오게 되는 것이다. top이 가리키는 위치의 아이템을 꺼낸 후 top을 1 감소시킨다.

두 함수 모두 시간 복잡도는 O(1)이고 스택은 원하는 아이템을 찾을 때는 top에서 부터 차례대로 찾아야해서 random 접근이 불가능하다.

스택의 예시

스택을 쉽게 설명하기 위해서 스택은 상자, 데이터는 상자와 너비가 같은 책이라고 예시를 든다 (책은 항상 눕혀서 상자에 넣는다). Top은 상자의 위에서 확인하는 것이라 생각한다.

스택이라는 상자에 처음 위에서 바라보면 상자의 밑바닥을 확인할 수 있다. 스택에 처음에는 자료구조라는 책을 넣는다. 상자를 위에서 봤을 때 우리는 자료구조가 있다는 것을 확인할 수 있다. 그 다음 운영체제 책을 넣고 컴퓨터 구조 책을 넣는다. 이 때 상자의 위에서 볼 수 있는 것은 컴퓨터 구조이다. Stack의 Top이 가리키는 것이 컴퓨터 구조라는 의미이다.

상자에서 우리가 꺼낼 수 있는 책은 마지막에 넣은 컴퓨터 구조이고 다른 책을 넣을 수 있는 공간 역시 컴퓨터 구조 위이다. 우리는 상자에서 컴퓨터구조, 운영체제, 자료구조 순으로 꺼낼 수 있으며 위에서 봤을 때 상자의 밑바닥이 보이면 책을 꺼내는 것이 불가능해진다.

상자에 자료구조가 있는 지 확인하려면 컴퓨터 구조 책부터 순서대로 꺼내가면서 확인을 해야한다.

Stack의 구현

이론적인 Stack (list자료형의 append(), pop() 사용하지 않음)

주소에 의한 참조가 가능하다는 조건에서 만들기 위해 dictionary 자료형을 사용했습니다. del 함수는 사전 자료형에서 시간복잡도가 1입니다.

class Stack:
    def __init__(self):     # 스택의 정의
        self.stack = dict()
        self.top = -1

    def push(self, data):   
        self.top += 1 
        self.stack[self.top] = data

    def pop(self):          
        if self.is_empty(): # 스택이 비었으면 pop이 불가능
            return "Stack is Empty"
        tmp = self.stack[self.top]
        del self.stack[self.top]
        self.top -= 1       

        return tmp

    def size(self):
        return self.top+1

    def is_empty(self):     # stack이 비어있는지 확인
        if self.top == -1:
            return True
        else:
            return False

    def peak(self):         # top이 가리키는 값
        if not self.is_empty():
            return self.stack[self.top]
        else:
            return "Stack is Empty"

    def __repr__(self):
        return repr(self.stack)

확인 코드

stack = Stack()
stack.push("자료구조")
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
stack.push("운영체제")
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
stack.push("컴퓨터구조")
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
print("pop : {}".format(stack.pop()))
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
print("pop : {}".format(stack.pop()))
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
stack.push("알고리즘")
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
print("pop : {}".format(stack.pop()))
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))
print("pop : {}".format(stack.pop()))
print("top : {}, peak : {}, stack : {}".format(stack.top, stack.peak(), stack))

결과

위의 코드는 이론적인 부분을 확인하기 위한 코드로 실제 파이썬에서는 list 자료형의 pop 과 append를 이용하여 구현하는 것이 쉽습니다.

Stack 객체 구현 (list자료형 pop(), append() 사용 )

class Stack:
    def __init__(self):
        self.stack = []
        self.top = -1
    def push(self, data):
        self.stack.append(data)
        self.top += 1
    def pop(self):
        if self.is_empty():
            return "Stack is Empty"
        self.top -= 1
        return self.stack.pop()

    def size(self):
        return len(self.stack)

    def is_empty(self):
        if not self.stack:
            return True
        else:
            return False

    def peak(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            return "Stack is Empty"

    def __repr__(self):
        return repr(self.stack)

확인 코드 결과

파이썬에서 스택을 굳이 직접 구현해야하는가?

파이썬의 list자료형은 위의 예제에서 봤듯이 pop()함수가 사용가능하고 push대신 append() 함수를 사용하면 스택처럼 리스트의 사용이 가능하다. 두 함수 모두 시간 복잡도는 O(1)이기 때문에 스택에서의 구현과 동일하다. top 또한 len - 1로, peak 또한 list[-1] 로 구현이 가능한 만큼 제공되는 함수를 사용하는 것이 유리하다고 생각한다.

찾는 item이 있는지 확인하는 부분이 리스트는 앞에서 확인하지만 스택은 뒤에서부터 확인한다는 점이 조금 다르긴 할 것이다.