Python_수업 (1)

2024.04.02 (화)

 

• 다익스트라 → 벨만 포드 알고리즘

 

• 이런이런 상황이거든? 자료구조!
• 그걸 토대로 풀어내는게 알고리즘!

 

• 리팩토링?
  소프트웨어 공학에서 '결과의 변경 없이 코드의 구조를 재조정함'을 뜻한다. 주로 가독성을 높이고 유지보수를 편하게 한다.
  버그를 없애거나 새로운 기능을 추가하는 행위는 아니다.

 

• 알고리즘 공부 방법론
  • 실전형 : 일단 문제를 풀면서 내용을 공부 틀려도 답지보고 풀고 비슷한 유형을 더 풀어본다.
  • 탐구형 : 우선 이론을 공부. 이후 이론에 맞는 문제를 풀되, 안 풀리는 문제를 끝까지 고민해보며 최대한 생각을 많이 해본다.
  • 실전형으로 하자!!!!!!!!!!
  • BOJ 실버 ~ 골드, 프로그래머스 LV 2~3
  • 대략 200 ~ 300 Q 정도면 1회독
  • 결국 중요한 것은 얼마나 꾸준히 오래 하느냐!

자료구조론

이러 이러한 상황이다!

조회, 수정, 삭제

a = [7, 2, 3, 5]
b = [3, True, 'hi', [1, 2], {'name': 'alex'}]

a[3] #5츨력

a[0] = 6 #[6, 2, 3, 5] 출력

a.append(9) #6, 2, 3, 5, 9] 출력

a.pop() #a = [6, 2, 3, 5] 출력

a.pop(0) #a = [2, 3, 5] 출력

• 스택 → DFS 때 유용
  • 후입선출 (ex. 뒤로가기 버튼)
• 큐(Queue)
  • 선입선출 (ex. 식당의 대기줄)
  • 우선순위 큐 (logN!????) (나중에 할 것이다…)
• 인접 행렬
• 그래프

 

• 리스트 안의 리스트? → 2차원 배열!!!!

 

 

<문제>

문제를 읽을 때 제한사항을 읽고 시작하자!!

예를 들면 시간복잡도 때문에!!

1. 신고 결과 받기
2. 전력망을 둘로 나누기
3. N-Quene 문제 → 순열 2차 백트래킹

중첩 자료구조를 잘 써야한다.

ex. 딕셔너리, 튜플, 리스트..

 

알고리즘 공부 순서

필수 주제 → 빈출 주제 → 부가 주제

 

메서드

sort()

• 옵션 주는 건 알아두자!

sort() 는 lexicographic sort!!

ex. 올림픽 메달

문자열 sort! -> 아스키 코드로 비교
words = ['alex', 'car', 'pineapple', 'apex', 'gold', 'dog', 'cat']
words.sort()
words = ['alex', 'apex', 'car', 'cat', 'dog', 'gold', 'pineapple']

a = ['1', '5', '3', '11', '23', '7']
a.sort()
a = ['1', '11', '23', '3', '5', '7']

a = [[1, 5], [1, 4], [5, 7], [2, 8], [9, 1]]
a.sort()
a = [[1, 4], [1, 5], [2, 8], [5, 7], [9, 1]]

a.sort(key=lambda x: x[1])  #x의 1번째를 기준으로 정렬!!
a = [[9, 1], [1, 4], [1, 5], [5, 7], [2, 8]]