Python_수업 (5)

2024.04.11 (목)

오늘 할 일

String 알고리즘

• 투포인터
• 같은 단위 내에서 시간복잡도 감소 (3N → 2N)

---

투포인터

• 시간 복잡도를 줄인다.
• 양쪽 데이터를 봐야할 때

word = input('단어를 입력하세요: ')

left = 0 # 시작 인덱스
right = len(word)-1 # 마지막 인덱스

is_palindrome = True
while left < right:  # 왼쪽과 오른쪽이 유지될때까지 돌아라!
    if word[left] == word[right]:  # 같은 경우라면 아직은 회문 조건을 만족함
        left += 1  # 왼쪽 포인터를 한칸 오른쪽으로 증가시키고
        right -= 1  # 오른쪽 포인터를 한 칸 왼쪽으로 감소
        continue
    else:  # 다른 경우라면 그 즉시 안된다고 표시하고 break
        is_palindrome = False
        break

print(is_palindrome)

- kmp 알고리즘 (문자열 검색 알고리즘)

- brute force

 

그리디(greedy, 탐욕 기법)

[문제] 백준_회의실 배정 (활동 선택, activity selection)

• 종료 시간이 이른 순서대로 정렬
• 걸리는 애들 싹 다 없애
• • 프로그래머스_단속카메라

 

2차원 리스트

• 나쁜 방식 → ID 값이 다 같아진다. a = [ [0] * 3 ] * 3
• 좋은 방식 b = [ [0] * 3 for _ in range(3) ]
• 행 우선 순회

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

trails = []  # 순회 궤적 담아줄 리스트

for r in range(3):
    for c in range(3):  # r 이 하나 고정된 상태에서 각각
        trails.append(matrix[r][c])

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

• 열 우선 순회

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

trails = []

for r in range(3):
    for c in range(3):
        trails.append(matrix[c][r])  # 여기가 바뀝니다.

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

• 전치 (Transpose) → 역방향 그래프가 된다!

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

for r in range(3):
    for c in range(3):
        if r > c: # r < c로 해도 됩니다.
            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]

for i in range(3):
    print(matrix[i])

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

if r > c: # r < c로 해도 됩니다. → 이 부분이 없으면 다시 원래대로 돌아가게 된다.

zip

→ 세로로 찝(zip)은 것을 튜플로!

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

c = [7, 8, 9]
list(zip(a, b, c))  #[(1, 4, 7), (2, 5, 8), (3, 6, 9)] -> 일종의 전치!

# zip을 활용한 전치하기 => 원소가 튜플이 됩니다.
zipped_matrix = list(zip(*matrix))
print(zipped_matrix) # [(3, 4, 8), (7, 2, 1), (9, 6, 5)]

# 전치 완료 후, 원소를 리스트로 활용하고 싶을 때
transposed_matrix = list(map(list, zip(*matrix)))
print(transposed_matrix)
# [[3, 4, 8], [7, 2, 1], [9, 6, 5]]

→ 활용도 무궁무진하다!!!! 복합자료 쉽게 만들 수도 있다.

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

d = dict(zip(range(0,3), [1, 2, 3]))    # {0: 1, 1: 2, 2: 3}

e = dict(zip(range(3), [0] * 3))    # {0: 0, 1: 0, 2: 0}

 

 

 

• 나중에 회전은 외워두면 좋다!