2차원 배열의 선언
- 1차원 List를 묶어 놓은 List
- 2차원 이상의 다차원 List는 차원에 따라 Index를 선언
- 세로길이 (행의 개수 : row) , 가로길이(열의 개수)를 필요
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(m):
arr[i][j] # 필요한 연산 수행열 우선 순회
- 세로 순으로 탐색 할 때
# i행의 좌표
# j행의 좌표
for j in range(m):
for i in range(n):
arr[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]부분집합 개수 구하기
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 sub
검색
- 저장 되어 있는 자료 중에서 원하는 항목을 찾는 작업
- 순차검색
- 이진검색
- 해쉬
순차검색
- 일렬로 되어 있는 자료를 순서대로 검색하는 방법
- 가장 간단하고 직관적
- 배열이나 연결리스트 등 순차구조인 자료구조에서 유용
- 비효율적
-
정렬되어 있지 않은 경우
- 첫번째 원소부터 검색 대상과 키값이 같은지 원소를 비교하면 찾음
- 찾으면 그 원소의 인덱스 반환
- 검색대상을 찾지 못하면 검색 실패
- 찾고자 하는 원소의 순서에 따라 비교 회수가 결정 된다.
-
정렬되어 있는 경우
-
오름차순으로 정렬된 상태에서 검색을 실시한다고 가정.
-
순차적으로 키 값을 비교, 원소의 키값이 검색 대상의 키 값 보다
크면 찾는 원소가 없다는 것 이므로, 더 이상 검색을 하지 않고 검색을 종료
-
이진 검색 (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]
문자열
-
string은 인덱스로 접근 가능하지만,
수정은 불가능 하다.
-
dir 메소드 사용시 문자열 뒤집기 가능
-
is => 참조하는것이 같은지 확인
-
리스트를 문자열로 -> "".join
고지식한 알고리즘 (Brute Force)
- 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작
- 최악의 경우 시간 복잡도는 O(MN) 이 된다.
KMP 알고리즘
-
불일치가 발생한 텍스트 스트링의 앞부분에 어떤 문자가 있는지 미리 알고 있으므로 , 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행
-
패턴을 전처리하여 배열 next[M] 을 구해서 잘못된 시작을 최소화함
- next[M] : 불일치가 발생했을 경우 이동할 다음 위치
- 시간 복잡도 : O(M+N)
-
매칭이 실패했을 때 돌아갈 곳을 계산한다.
-
접두사와 접미사를 기반으로 만드는 전처리 테이블
def makeTable(P):#P는 패턴 lp=len(P) Table=[0]*lp #패턴의 길이와 같은크기의 테이블 생성 i=0 #i를 사용하여 테이블 값을 갱신한다 for j in range(1,lp): while i>0 and P[i]!=P[j]: #i와 j가 다르면 i는 i-1의 테이블값 인덱스로 돌아간다 i=Table[i-1] #왜?->현재의 i에서 j와 다르니 i가 +1되었던것을 되돌아가서 #i-1에서의 테이블값 인덱스에서 다시 j와 비교해준다 #테이블에는 최대 공통 부분들이 있어서 돌아갈지점을 계속 갱신해주다가 #0까지 가면 0이 된다.0을 저장하고 다음 j로 넘어간다 if P[i]==P[j]: #만약 같으면 i값을 1더해주고 table값에 넣는다. i+=1 #i,j둘다 1씩 증가한다 Table[j]=i return Table -
KMP 코드 예시
def KMP(P,T): ans=[] lt=len(T) lp=len(P) table=makeTable(P) i=0 for j in range(lt): while i>0 and P[i]!=T[j]: i=table[i-1] if P[i]==T[j]: if i==lp-1: ans.append(j-lp+2) i=table[i] else: i+=1 return ans text=input().rstrip() pattern=input().rstrip() ans=KMP(pattern,text) print(len(ans)) print(*ans)접두사와 접미사를 만드는 테이블과 KMP 테이블이 거의 일치 하는것을 확인 가능
-
백준1786
T=input() P=input() def getPi(pattern): pi = [0] * len(pattern) j=0 for i in range(1, len(pi)): # i끝, j앞 while j > 0 and pattern[i] != pattern[j]: j = pi[j - 1] #순간이동 if pattern[i] == pattern[j]: j += 1 pi[i] = j return pi def kmp(word, pattern): pi = getPi(pattern) print(pi) results = [] j=0 for i in range(len(word)): #i word, j pattern while j > 0 and word[i] != pattern[j]: j = pi[j - 1] if word[i] == pattern[j]: if j==len(pattern)-1: results.append(i-len(pattern)+1) j=pi[j] else: j+=1 return results results = kmp(T, P) print(len(results)) for r in results: print(r+1)
보이어 - 무어 알고리즘
-
오른쪽에서 왼쪽으로 비교
-
대부분 상용 소프트 웨어에서 채택
-
패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우 이동거리는 패턴의 길이 만큼
-
KMP 와 차이점 => 오른쪽 끝부터 확인
개발 일기