Tips
2차원 배열을 0으로 둘러쌓고 싶을때
arr = [[0]N] + [[0]+list(map(int,input().split()))+[0] for _ in range(N)] + [[0]N]
2차원 배열의 선언
- 1차원 List를 묶어놓은 List
- 2차원 이상의 다차원 List는 차원에 따라 Index를 선언
- 세로길이 (행의개수), 가로길이 (열의 개수)를 필요
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]배열 순회
- n X m 배열의 n*m개의 모든 원소를 빠짐없이 조사하는 방법
행 우선 순회
# i 행의 좌표
# j 열의 좌표
for i in range(n):
for j in range(n):
arr[i][j] # 필요한 연산 수행열 우선 순회
- 세로 순 으로 탐색 할 때
# i 행의 좌표
# j 열의 좌표
for j in range(m):
for i in range(n):
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차 배열 탐색
- 2차 배열의 한 좌표에서 4 방향의 인접 배열 요소를 탐색하는 방법
arr[0...N-1][0..N-1] # N x N 배열
# 왼쪽, 오른쪽, 위 , 아래
di[] <- [0,0,-1,1]
dj[] <- [-1,1,0,0]
for i : 1 -> N-1
for j : 1 -> N-1 :
for k in range(4):
nj <- i + dj[k]
nj <- j + dj[k]
if 0<=ni<N and 0<=nj<N: #유효한 인덱스 이면
test[arr[ni][nj]]# 모든 원소에 대해 ... 라는 지문이 나왔을 때
# N x M 배열
di = [0,1,0,-1]
dj = [1,0,-1,0]
for k in range(4):
ni = i + di[k]
nj = j + dj[k]
if 0 <= ni < N and 0 <= nj < M : #유효 인덱스
arr[ni][nk]
for r in range(len(num_list)):
for c in range(len(num_list[0])):
# 5 일 때, 상하좌우에 있는 원소 출력
if num_list[r][c] == 5:
row_d = [-1,1,0,0]
col_d = [0,0,-1,1]
for d in range(4):
new_r = r + row_d[d]
new_c = c + col_d[d]
print(num_list[new_r][new_c])# pythonic
for di , dj in [(0,1),(1,0),(0,-1),(-1,0)]:
ni = i + di
nj = j + dj
if 0 <= ni < N and 0 <= nj < M : #유효 인덱스
arr[ni][nk]전치 행렬
- 행과 열을 바꾸는것
검색
- 저장 되어 있는 자료 중에서 원하는 항목을 찾는 작업
- 순차검색
- 이진검색
- 해쉬
순차검색
- 일렬로 되어 있는 자료를 순서대로 검색하는 방법
- 가장 간단하고 직관적
- 배열이나 연결리스트 등 순차구조인 자료구조에서 유용
- 비효율적
-
정렬되어 있지 않은 경우
- 첫번째 원소부터 검색 대상과 키값이 같은지 원소를 비교하면 찾음
- 찾으면 그 원소의 인덱스 반환
- 검색대상을 찾지 못하면 검색 실패
- 찾고자 하는 원소의 순서에 따라 비교 회수가 결정 된다.
-
정렬되어 있는 경우
-
오름차순으로 정렬된 상태에서 검색을 실시한다고 가정.
-
순차적으로 키 값을 비교, 원소의 키값이 검색 대상의 키 값 보다
크면 찾는 원소가 없다는 것 이므로, 더 이상 검색을 하지 않고 검색을 종료
-
이진 검색 (Binary Search)
-
자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의
위치를 결정하고 검색을 진행 한느 방법
- 목적키를 찾을때까지 순환적으로 반복 수행 함으로써, 검색 범위를 반으로 줄여 빠르게 검색 가능
단 , 정렬 되어 있어야 한다.
-
검색 과정
-
중앙에 있는 원소를 고른다
-
중앙 원소의 값과 찾고자 하는 목표값을 비교
-
목표값이 중앙보다 작다면, 왼쪽 반에 대해서 새로 검색 수항
크다면, 오른쪽 반에 대해 새로 검색 수행
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 SelectionSort(a,N): for i in range(N-1): minIdx = i for j in range(i+1,N): if a[minIdx] > a[j]: minIdx = j a[i] , a[minIdx] = a[minIdx] , a[i]
부분 집합 개수 구하기
# 예시
arr = [3, 5, 6, 7]
subs = [[]] # 공집합이 포함된 리스트 선언
for 문 반복하여
[[] , [3] , [5], [3,5] ....] 순으로 더해주기
def subs(lst):
# A의 부분집합 만들기
sub = [[]] # 공집합 포함 리스트 sub 선언
for i in lst:
for j in range(len(sub)):
sub.append(sub[j]+[i]) # A의 부분집합을 만든다.
return subset() 함수를 이용하면 , 집합연산을 할 수 있다.
# 교집합
red & blue # red.intersection(blue)
# 합집합
red | blue # red.union(blue)
# 차집합
red - blue # red.difference(blue)
# 대칭 차집합
red ^ blue
개발 일기