2차원 배열의 선언
arr = [[1,2,3,4],[5,6,7,8]]
(2행, 4열)
N = int(input())
arr = [list(map(int,input().split())) for i in range(N)]
배열 순회
n X m 배열의 n*m 개의 모든 원소를 빠짐없이 조사하는 방법
행 우선 순회
# i 행의 좌표
# j 열의 화표
for i in range(n):
for j in range(m):
Array[i][j]
# i 행의 좌표
# j 열의 화표
for j in range(n):
for i in range(m):
Array[i][j]
# i 행의 좌표
# j 열의 화표
for i in range(n):
for j in range(m):
Array[i][j - (m-1-2*j)*(i%2)]
델타를 이용한 2차 배열 탐색
# 상하좌우 방향
N = 3
di = [0,1,0,-1]
dj = [1,0,-1,0]
for i in range(N):
for j in range(N):
for k in range(4):
ni,nj = i + di[k], j + dj[k]
if 0 <= ni < N and 0 <= nj < N:
print(i,j,ni,nj)
# 상하좌우 방향 2개씩
전치 행렬
# i 행
# j 열
arr = [[1,2,3],[4,5,6],[7,8,9]]
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]
비트 연산자
&
: 비트 단위로 AND 연산을 한다
|
: 비트 단위로 OR 연산을 한다
<<
: 피연산자의 비트 열을 왼쪽으로 이동시킨다.
>>
: 피연산자의 비트 열을 오른쪽으로 이동시킨다.
<< 연산자
& 연산자
부분집합 생성
arr = [3,6,7,1,5,4]
n= len(arr)
for i in range(1<<n) : # 1<<n : 부분 집합의 개수
for j in range(n): # 원소의 수만큼 비트를 비교함
if i & (1<<j): # i의 j번 비트가 1인 경우
print(arr[j], end = ", ") # j번 원소 출력
print()
print()
저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
목적하는 탐색키를 가진 항목을 찾는 것
검색의 종류
정렬되어 있지 않은 경우
def sequentialsearch(a, n, key):
i <- 0
while i < n and a[i]!=key:
i <- i+1
if i < n : return i
else : return -1
정렬되어 있는 경우
def sequentualsearch2(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
자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다
검색 과정
구현
def binarySearch(a, N, key):
start = 0
end = N-1
while start <= end :
middle = (start + end) // 2
if a[middle] == key : # 검색 성공
return True
elif: a[middle] > key:
end = middle -1
else:
start = middle -1
return False # 검색 실패
# 재귀 함수 이용
# 이진 검색은 반복구조가 더 빠르긴 함
def binarysearch2(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 binarysearch2(a, low, middle -1, key)
elif a[middle] < key:
return binarysearch2(a, middle+1, high, key)
인덱스라는 용어는 database에서 유래 했으며, 테이블에 대한 동작 속도를 높여주는 자료 구조를 일 컫는다. Database 분야가 아닌 곳에서는 Look up table 등의 용어를 사용하기도 한다
인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보다 작다. 왜냐하면 보통 인덱스는 키- 필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문
배열을 사용한 인덱스
대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없다.
이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 배열 인덱스를 사용할 수 있다
원본 데이터에 데이터가 삽입될 경우 상대적으로 크기가 작은 인덱스 배열을 정렬하기 때문에 속도가 빠르다.
def selectionsort(a, n):
for i in range(n-2):
min_index = a.index(min(a[i:]))
if min_index != i:
a[i], a[min_index] = a[min_index], a[i]
n_list = [0,2,5,1,9,6,4,7,8,3]
selectionsort(n_list, 10)
print(n_list) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
def selectionsortk(a, k):
for i in range(k): # k번만 선택정렬
min_index = a.index(min(a[i:]))
if min_index != i:
a[i], a[min_index] = a[min_index], a[i]
return a[k-1]
n_list = [0,2,5,1,9,6,4,7,8,3]
print(selectionsortk(n_list, 4)) # 3
print(n_list) # [0, 1, 2, 3, 9, 6, 4, 7, 8, 5]
n_list = [0,2,5,1,9,6,4,7,8,3]
print(selectionsortk(n_list, 6)) # 5
print(n_list) # [0, 1, 2, 3, 4, 5, 9, 7, 8, 6]