2차원 배열의 선언
: Python에서는 데이터 초기화를 통해 변수선언과 초기화가 가능
arr = [i for i in range(2, 9) if i % 2 == 0]
# [2, 4, 6, 8 ]
brr = [[1,2,3]] * 3
# [[1, 2, 3],[1, 2, 3],[1, 2, 3]]
crr = [[i, j] for i in range(3) for j in range(2)]
# [[0, 0],[0, 1],[1, 0],[1, 1],[2, 0],[2, 1]]
델타를 이용한 2차 배열 탐색
: 특정 원소의 상하좌우에 접근
-> 존재하지 않을 경우가 있으므로 index 체크
# 상하좌우
dy = [0, 0, -1, 1]
dx = [-1, 1, 0, 0]
전치행렬
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]
연습문제 1
Q. 5x5 2차 배열에 무작위로 25개의 숫자로 초기화 한 후, 25개의 각 요소에 대해서 그 요소와 이웃한 요소와의 차의 절대값을 구하시오.
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
ans = [[0]*4 for _ in range(4)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
for y in range(4):
for x in range(4):
for d in range(4):
if 0 <= x+dx[d] < 4 and 0 <= y+dy[d] < 4:
if arr[y][x] > arr[y+dy[d]][x+dx[d]]:
ans[y][x] += arr[y][x] - arr[y+dy[d]][x+dx[d]]
else:
ans[y][x] += arr[y + dy[d]][x + dx[d]] - arr[y][x]
print(ans)
부분집합
비트연산자
1. & : 비트 단위로 AND 연산을 한다.
2. | : 비트 단위로 OR 연산을 한다.
3. << : 피연산자의 비트 열을 왼쪽으로 이동시킨다.
4. >> : 피연산자의 비트 열을 오른쪽으로 이동시킨다.
arr = [3, 6, 7, 1, 5, 4]
n = len(arr)
# 2^n 개의 부분집합
for i in range(1<<n):
# 원소의 갯수만큼 비교
for j in range(n):
if i & (1<<j):
print(arr[j], end=" ")
print()
print()
연습문제 2
Q. 10개의 정수를 입력 받아 부분집합의 합이 0이 되는 것이 존재하는지를 계산하는 함수를 작성하라.
arr = list(map(int, input().split()))
n = len(arr)
result = False
# 공집합인 경우에는 부분집합의 합이 0 이므로 1부터 시작
for i in range(1, 1<<n):
sumV = 0
for j in range(n):
if i & (1<<j):
sumV += arr[j]
if sumV == 0:
result = True
break
print(result)
순차검색
1. 정렬되어 있지 않은 경우
-> 단순히 값을 하나씩 비교하며 인덱스 증가, 값을 찾지 못하고 배열에 끝에 닿으면 -1을 리턴한다.
arr = [3, 6, 7, 1, 5, -1, -3, -4]
key = 5
def sequentialSearch(a, n, key):
i = 0
while i < n and a[i] != key:
i += 1
if i < n:
return i
else:
return -1
print(sequentialSearch(arr, 8, key))-> 시간복잡도 : O(n)
2. 정렬되어 있는 경우
-> 찾고자 하는 값보다 작은 동안 인덱스를 늘려가며 검사, 멈춰선 인덱스가 key와 완전히 같지 않으면 -1을 리턴
arr = [2, 4, 7, 9, 11, 19, 23]
key = 10
def sequentialSearch(a, n, key):
i = 0
while i < n and a[i] < key:
i += 1
if a[i] == key:
return i
else:
return -1
print(sequentialSearch(arr, 8, key))-> 정렬이 되어 있으므로, 검색 실패를 반환하는 경우 평균 비교 횟수가 반으로 줄어든다.
-> 시간복잡도 O(n)
댓글