[SW Intermediate] List 2

List 2 - 2차원 리스트

---

2차원 리스트

1) 1차원 리스트를 묶어 놓은 리스트이다.

2) 2차원 이상의 다차원 리스트는 차원에 따라 인덱스를 선언한다.

3) 2차원 리스트의 선언:

     세로길이(행의 개수), 가로길이(열의 개수) 를 필요로 한다. 

4) 파이썬에서는 데이터 초기화를 통하여 변수 선언과 초기화가 가능하다. 

 

---

리스트 초기화

# 1차원 리스트 초기화

#1)
arr = [0,0,0,0,0]

#2)
arr = [0] * 5 

# res = [0,0,0,0,0]

#3)
arr = [i for i in range(2,9) if i%2 == 0 ]

# res = [2,4,6,8]

 

# 2차원 리스트 초기화

#1)
brr = [[1,2,3], [1,2,3], [1,2,3]]

#2)
brr =[[1,2,3]] * 3

#res = [[1,2,3], [1,2,3], [1,2,3]]

#3)
brr = [[1,2,3] for i in range(3)]

# res = [[1,2,3], [1,2,3], [1,2,3]]

#4)
brr = [[i,j] for i in range(3) for j in in range(2)]

# res = [[0,0], [0,1], [1,0], [1,1], [2,0], [2,1]]

 

---

2차원 리스트 입력 받기

 

예시1)

n, m = map(int, input().split())

mylist = [0 for _ in range(n)]

for i in range(n):
	mylist[i] = list(map(int, input().split()))

 

예시2)

n, m = map(int, input().split())
mylist = []
for i in range(n):
	mylist.append(list(map(int, input().split()))

 

예시3)

n, m = map(int, input().split())
mylist = [list(map(int, input().split())) for _ in range(n) ]

 

---

2차원 리스트에서 원하는 데이터의 위치 찾기 

주어진 데이터에서 1이 입력된 [행][열] 찾기

 

예시1)

n, m = map(int, input().split())

new_list = []
mylist = [ 0 for _ in range(n)]

for i in range(n):
	mylist[i] = list(map(int, input().split()))
    for j in range(m):
    	if mylist[i][j] == 1:
        	new_list.append([i,j])

 

예시2)

n, m = map(int, input().split())
mylist = [list(map(int, input().split()) for _ in range(n)]

new_list = [(i,j) for i in range(n) for j in range(m) if mylist[i][j] == 1 ]

 

---

리스트 순회

n x m 리스트의 n*m 개의 모든 원소를 빠짐없이 조사하는 방법

 

1) 행 우선 순회:

리스트의 행을 우선으로 리스트의 원소를 조사하는 방법

 

arr = [[0,1,2,3], [4,5,6,7], [8,9,10,11]]

# i: 행의 좌표, n = len(arr)
# j: 열의 좌표, m = len(arr[0])

for i in range(len(arr)):
	for j in range(len(arr[i])):
    	arr[i][j]
        #필요한 연산 수행

 

2) 열 우선 순회:

리스트의 열 부터 먼저 조사하는 방법

 

# i: 행의 좌표, n = len(arr)
# j: 열의 좌표, m = len(arr[0])

for j in range(len(arr[0]):
	for j in range(len(arr)):
    	arr[i][j]
        # 필요한 연산수행

 

3) 지그재그 순회:

첫 행은 우측으로, 다음 행은 좌측으로 진행하여 Array의 원소를 조사하는 방법

# i: 행의 좌표, n = len(arr)
# j: 열의 좌표, n = len(arr[0])

for i in range(len(arr)):
	for j in range(len(arr[0])):
    	arr[i][j + (m-1-2*j)*(i%2)]
        # 필요한 연산 수행

 

4) 델타를 이용한 2차 리스트 탐색:

→ 2차 리스트의 한 좌표에서 네 방향의 인접 리스트 요소를 탐색할 때 사용하는 방법

→ 델타 값은 한 좌표에서 네 방향의 좌표와 x, y의 차이를 저장한 리스트로 구현 

→ 델타 값을 이용하여 특정 원소의 상하좌우에 위치한 원소에 접근할 수 있다.

 

* 이차원 리스트의 가장자리 원소들은 상하좌우 네 방향에 원소가 존재하지 않을 경우가 있으므로, 

Index를 체크하거나 Index의 범위를 제한 해야한다. 

 

# 델타를 이용한 2차 리스트의 탐색

# arr[0....n-1][0....n-1]

# 상하좌우
dx = [0, 0, -1, 1] 
dy = [-1, 1, 0, 0]

for x in range(len(arr)):
	for y in range(len(arr[x]):
    	for i in range(4):
        	text_X = x + dx[i]
            text_y = y + dy[i]
            print(arr[text_x][text_y])

---

전치 행렬

행과 열의 값이 반대인 행렬을 의미

 

# i: 행 좌표, len(arr)
# j: 열 좌표, len(arr[0])

arr=[[1,2,3], [4,5,6], [7,8,9]]
# 3*3

for i in range(3):
	for j in range(3):
    	if i < j:
        	arr[i][j], arr[j][i] = arr[j][i], arr[i][j]

 

* i < j 조건을 쓰는 이유:

모든 좌표에 대하여 행과 열의 값을 바꾸게 되면 본래의 모습으로 되돌아 오기 때문이다.

 

---

zip(*iterable)

동일한 개수로 이루어진 자료형들을 묶어주는 역할을 하는 함수

→ 여기서 사용한 * iterable 은 반복 가능(iterable)한 자료형 여러 개를 입력할 수 있다는 의미이다.

 

list(zip([1, 2, 3], [4, 5, 6]))
# res = [(1, 4), (2, 5), (3, 6)]

list(zip([1, 2, 3], [4, 5, 6], [7, 8, 9]))
# res = [(1, 4, 7), (2, 5, 8), (3, 6, 9)]

list(zip("abc", "def"))
# res = [('a', 'd'), ('b', 'e'), ('c', 'f')]

 

arr = [[1,2,3], [4,5,6], [7,8,9]]

print(list(zip(*arr))

# result
# [(1,4,7), (2,5,8), (3,6,9)]

 

* zip(*matrix): 전치 행렬

 

---

부분 집합

 

[ 부분 집합의 수 ]

1) 각 집합의 원소가 N개 일 때, 공 집합을 포함한 부분 집합의 수는 2^N 개 이다.

2) 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.

EX) {1,2,3,4} = 2 x 2 x 2 x 2 = 16가지

 

[ 부분집합 구하는 방법]

1) loop 를 이용하여 확인하고, 부분집합을 생성하는 방법

* bit = [] : 대상 리스트의 각 원소를 포함할지 말지를 정하는 리스트

bit = [0,0,0,0]

for i in range(2):
	bit[0] = i # 0번째 원소
    for j in range(2):
    	bit[1] = j # 1번째 원소
        for k in range(2):
        	bit[2] = k # 2번째 원소
            for l in range(2):
            	bit[3] = l # 3번째 원소
                print(bit) # 생성된 부분집합 출력

 

★ [itertools 라이브러리의 combinations 메서드] 

1) combinations(대상리스트, 부분집합의 길이)

2) combinations 객체로 반환하기 때문에 리스트 메서드로 형 변환을 시켜주어야 리스트로 활용이 가능하다. 

 

---

검색

저장 되어있는 자료 중에서 원하는 항목을 찾는 작업 

 

[순차 검색]

1) 일렬로 되어있는 자료를 순서대로 검색하는 방법이다.

2) 리스트나 연결 리스트 등 순차구조로 구현된 자료구조에서 유용하다.

3) 구현이 쉽지만, 검색 대상이 많은 경우 수행시간의 증가로 비효율적이다. 

4) 정렬된 경우와 정렬되지 않은 경우로 나뉜다.

 

[ 순차검색 - 정렬되지 않은 자료의 검색 ]

1) 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지를 비교하여 찾는다.

2) 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환한다.

3) 자료구조의 마지막에 갈 때 까지 검색 대상을 찾지 못하면 검색 실패이다.

4) 시간 복잡도는 찾고자 하는 원소의 순서에 따라 비교 횟수가 결정되며, O(N) 이다.

 

def sequential_search(a,n,key):
	i = 0
    while i < n and a[i] != key:
    	i = i+1
    if i < n: return i
    else: return -1

 

[ 순차검색 - 정렬된 자료의 검색 ]

1) 자료가 오름차순으로 정렬 된 상태에서 검색을 실시한다고 가정한다.

2) 자료를 순차적으로 검색하면서 키 값을 비교한다.

3) 원소의 키 값이 검색 대상의 키 값보다 크면 원소가 없다는 것이므로 더이상 검색하지 않고 검색을 종료한다. 

4) 찾고자 하는 원소의 순서에 따라 비교 횟수가 결정되며, 시간 복잡도는 O(N)이다.

 

def sequential_search(a,n,key):
	i = 0
    while i < n and a[i] <key:
    	i = i+1
    if i<n and a[i] == key:
        return i
    else: return -1

 

[이진검색]

1) 효율적인 검색 방법이다.

2) 자료의 가운데 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속하는 방법이다.

3) 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복수행함으로써 검색의 범위를 반으로 줄여가면서 빠르게 검색을 수행한다.

4) 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

5) 정렬된 데이터가 n개가 있는 경우의 시간 복잡도, 

순차 검색시 O(N)의 시간이 걸리지만

이진 검색시 O(logN)의 시간이 걸린다.

 

[이진검색 - 검색방법]

1) 자료의 중앙에 있는 원소를 선택한다.

2) 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.

3) 목표 값 < 중앙 원소 값: 자료의 왼쪽 반에 대해서 새로 검색을 수행

4) 목표 값 > 중앙 원소 값 : 자료의 오른 쪽 반에 대해서 새로 검색을 수행

5) 찾고자 하는 값 찾을 때까지 1)~3) 작업을 반복한다.

6) 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다. 

7) 이진 검색의 경우 자료에 삽입이나 삭제가 발생하였을 때 리스트의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다. 

 

# 반복

def binary_search(a, key):
	start = 0 
    end = len(a) - 1
    while start <= end:
    	middle = start + (end-start)//2
        if key == a[middle]:
        	return True
        elif key < a[middle]:
        	end = middle - 1
        else:
        	start = middle + 1
    return False

 

# 재귀

def binary_search(a, low, high, key):
	if low > high:
    	return False
    else:
    	middle = (low+high) // 2
        if key == a[middle]:
        	return True
        elif key < a[middle]:
        	return binary_search(a,low,middle-1,key)
        elif a[middle] < key:
        	return binary_search(a, middle+1, high, key)