오늘 할일 DFS 심화 intro : 외판원 순회 문제 DFS(재귀)를 통한 순열 직접 구현 백트래킹(가지치기) 준비물 : DFS(재귀) 코드 복습! 그래프 이론 DFS(깊이 우선 탐색 → 스택, 재귀 / 경로) / BFS(너비 우선 탐색 → 큐 / 최단거리) : 세팅 → 방문 → 탐색 DFS 심화 intro : 외판원 순회 문제 N 개의 도시를 순회하는 가장 빠른 경로 → N 개의 도시 줄 세우기! → DFS(깊이 우선 탐색) 가능한 모든 경로(경우의 수) 확인하기! → 가능한 모든 DFS 반복하기! DFS(재귀)를 통한 순열 직접 구현 순열과 조합 (itertools) permutation(순열) : N개 중에 N개를 뽑아 줄을 세운다. 재귀순열 # 기본적인 틀 def perm(depth): # 종료..
오늘 할 일 DFS/BFS 심화 → 이차원 리스트 형태 복습! 스택과 큐, deque 자료구조 deque 사용시 popleft() 사용 그래프 자료구조의 의미, 용어 점과 선으로 이루어진다. 정점, 간선, 가중치 유향(일방향) 그래프, 무향(양방향) 그래프 그래프 구조화 : 인접 행렬과 인접 리스트 빈 판 만들기 간선 정보 입력 그래프 탐색 : BFS(너비우선탐색)와 DFS(깊이우선탐색) DFS/BFS 심화 스택 또는 재귀 함수를 활용한 DFS 구현 이차원리스트 형태의 그래프(델타탐색) 이차원리스트에서 DFS/BFS 실습문제: 미로, 미로의 거리 DFS 특 가장 최근에 탐색한 정점을 우선적으로 방문한다. → 스택 또는 재귀를 통한 구현 스택을 통한 구현 세팅 흐음… 재귀를 통한 구현 세팅 재귀가 모두 종..
오늘 할 일 그래프 이론 구현 ex. 사칙연산 빠르게 구하기 기타(자료구조론) 그래프 이론 그래프 이론 관련 용어 숙지하기 정점(노드, Vertex)과 간선(Edge), 가중치 유향(일방향) 그래프와 무향(양방향) 그래프 ex. SNS 친구 관계 ㅋㅋㅋ 희소 그래프와 밀집 그래프, 완전 그래프 → 시간 복잡도 때문에 사용 but 중요하진 않지만 완전 그래프는 약간 중요함 ㅋㅋㅋ ex. 외판원 문제 → 완전 그래프 스택과 큐 복습! 큐 선입선출 나가는 건 처음 들어간 것 들어올땐 마지막으로 시간 복잡도상 리스트 구현 힘들다. (pop(0) → O(N) / append() → O(1)) → deque deque 자료의 선입과 선출이 중간에 이뤄지지 않고 양 끝에서 이뤄진다. from collections i..
2024.04.12 (금) 오늘 할 일 2차원 리스트와 델타 탐색 2차원 리스트와 델타 탐색 1. 모듈러 연산 나머지로 깎아 버린다. ex. 0 1 2 3 0 1 2 3 … 2. 몫 연산 2차원 리스트 순회할 때 사용 matrix = [[3, 7, 9], [4, 2, 6], [8, 1, 5]] for i in range(9): print(matrix[i // 3][i % 3]) #쓸 일 많이 없다 그냥 이중 for 문 돌리자 3. 델타 탐색 기법 상하좌우 움직이는 구현 “delta” (작은 값) → 알고리즘에서는 이차원 리스트의 한 칸 new_r -> nr new_c -> nc nr = r + dr nc = c + dc [상] -> dr : -1 /. dc : +0 [우] -> dr : +0 /. dc ..
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: # 다른 경우라면 그 즉시 안된다고..
2024.04.09 (화) 정렬 목표 : 안정 정렬이 무엇인지! 버블 정렬 (안정 정렬) # 버블 정렬 코드 arr = [2, 4, 1, 3] # 정렬하고자 하는 리스트의 길이가 4니까? for i in range(len(arr)-1, 0, -1): # 총 3회 시행, for j in range(i): # 각 시행 횟수 안에서, 3 2 1 번씩 비교 할것 if arr[j] > arr[j+1]: # 내가 오른쪽 녀석보다 크다면? arr[j], arr[j+1] = arr[j+1], arr[j] # 자리를 바꾼다! print(arr) ''' " > " 때문에 안정 정렬이 된다!! ''' 2. 카운팅 정렬 (안정 정렬) 어렵… 안정 정렬 보장법 기교 S 배열 (누적합 배열) step 1. 개수를 센다. step..
2024.04.05 (금) 오늘 배울 것 함수, 스코프 재귀함수 log N 시간 복잡도 이분 탐색기 함수, 스코프 이름 공간 a = 3 def func(): a = 4 print(a) func() print(a) #4 #3 ''' !!!!순서 중요!!!! Local : ex. a = 4 의 a Enclosed (함수 안의 함수) Global : ex. a = 3 의 a / func Built-in : print, sum... ''' a = 3 def func(): global a a = 4 print(a) func() print(a) #4 #4 스코프 → 함수 기준 a = [1, 2, 3] print(id(a)) def func(lst): print(id(lst)) lst.append(4) print(l..
Python_수업 (2)
2024.04.04 (목) 슬라이싱 하나씩 보는 것을 순차검색 shallow copy (얕은 복사) 기능 이차원 리스트 복사하는 것 주의!! 제일 밖에 껍데기만 갈아끼우고 안쪽 리스트는 계속 연동 #해결 방법 #첫 번째 방법 a = [[1, 2], [3, 4]] b = [] for i in a: b.append(i[:]) print(b) #두 번째 방법 -> 자주 사용한다. a = [[1, 2], [3, 4]] b = [i[:] for i in a] print(b) #세 번째 방법 -> 삼차원 이상이면 deepcopy 사용이 좋다. import copy a = [[1, 2], [3, 4]] b = [i[:] for i in a] c = copy.deepcopy(a) print(b) 슬라이싱 삽입 → 따로..