[W02] 알고리즘

06.백트래킹

# 1.def comb(n,k) -> 전체의 작업을 관리하는 바깥 함수
# 2.backtrack(start,current_combination) -> 조합을 실제로 만드는 작업함수. cur[]뒤에 start이상의 숫자 고르기
	-> current_combination배열의 길이가 k와 같다면 result에 복붙 
	-> 다르다면 current_combination[]에 반복문이 현재 차례에 선택한 숫자추가
# for문 돌때마다 재귀호출
# 하나의 재귀 탐색을 마치고 돌아올 때마다 pop() 실행

– current_combination 배열의 길이가 k와 같다면 result에 복붙하는 이유
: 이후 배열이 append와 pop을 계속하면서 배열의 값이 섞일 수 있기 때문(같은 리스트 객체가 계속 변경됨)
→ current_combination은 재귀 과정 전체에서 같은 리스트 객체를 사용하고, append()와 pop()으로 내용만 계속 변경함. -> 조합이 완성되었을때 해당값을 보존하기 위해서.

---

09.정수론

# 1. gcd(a,b) 
-> b==0이면 a 리턴
-> 아니면 gcd(b,a%b)로 재귀

# gcd_iterative(a,b) -> b == 0 될 때까지 
temp=b
a=a%b
b=temp

한 후에 최대공약수 a를 return

#lcm(a,b) -> a*b = lcm(a,b) * gcd(a,b)

#extended_gcd(a,b) : ax+by=gcd(a,b)를 만족하는 x,y 구하기

-> b==0이면 return (a,1,0)
-> 아니면 extended_gcd(b,a%b)로 재귀
-> 재귀에서 돌아오면서 계수 계산
x=y1
y=x1-(a//b)*y1

return(g,x,y)

#소수판별
from math import sqrt
case1: n<2 -> false
case2: n==2 ->2는 유일한 짝수 소수이므로 True
case3: n%2==0 -> false -> 2 제외 짝수
case4: n%3==0 -> 그 외 홀수
4-1. 3부터 sqrt(n)까지 홀수로 나눠본다.
4-2. 하나라도 나누어떨어짐 → 소수 아님 (F)
4-3. 끝까지 안 나누어떨어짐 → 소수 (T)

– 확장 유클리드 함수 : ax+by=gcd(a,b)를 만족하는 x,y & gcd 구하기
① 목표
ax + by = g

② 재귀 결과
bx1 + (a%b)y1 = g

③ 나머지 공식
a%b = a - (a//b)b ->a%b에 대입

– 소수 판별에서 제곱근 사용 이유
: 약수는 항상 쌍으로 존재함
ex) √36 = 6을 넘어가면 앞에서 확인했던 약수 쌍이 순서만 바뀌어서 다시 등장

1 × 36
2 × 18
3 × 12
4 × 9
6 × 6    ← √36
9 × 4
12 × 3
18 × 2
36 × 1

→ 어떤 수 n이 합성 수라면, 약수 쌍 중 적어도 하나는 반드시 √n 이하에 존재
=> √n 까지만 검사함을 통해 시간 감소 가능

---

07.시간복잡도

# 1.find_duplicates_brute_force (이중반복문)
첫번째 for문 [i]: i 번째요소 ~ n-1번째 요소까지
두번째 for문 [j]: i+1번째요소 ~ n번째요소까지
[i]==[j] 
-> duplicates에 있는지 확인
-> 없으면 duplicates[]에 추가

duplicates 리턴

# 2. find_duplicates_sorting (정렬)
nums.sort()로 정렬
for문 [i]: i 번째요소 ~ n-1번째 요소까지
[i]==[i+1] 
-> duplicates에 있는지 확인
-> 없으면 duplicates[]에 추가

# 3.find_duplicates_hash (해시)
빈 집합 생성
seen = set() <- 본적 있는 수 저장
duplicates = set() <- 중복 저장

nums 순회하면서 
seen에 있음 -> duplicates에 추가
없음 -> seen에 추가

– 해시 집합(Hash Set): 중복을 허용하지 않고 순서가 없는 고유한 값들을 빠르게 저장하고 검색하기 위한 자료구조
– find_duplicates_hash에서
seen: 지금까지 등장한 숫자(중복인지를 판별)
duplicates: 그 수의 중복으로 확인된 숫자(판별 결과를 저장)

로 나눠서 저장함.
– 중복 원소를 리스트로 반환하도록 요구하므로
return list(duplicates)를 통해 set → list로 형변환

---

08.버블정렬

# 1.bubble_sort(arr)
- 외부반복문 : n-1번 반복
- 내부반복문 : n-i-1번 반복 (이미 정렬된 뒷부분 제외)
   - arr[j]>arr[j+1] -> 교환
   
# 2.bubble_sort_optimized(arr)
- 외부반복문: n번 반복
   - 한 패스 시작마다 swapped=False
- 내부반복문: n-i-1번 반복
   - 교환이 한번이라도 발생 -> swapped=True
- 교환이 없었으면 이미 정렬된 것 => 조기종료
- 필요한 모든 패스 수행을 통해 정렬 끝남 => 정상종료

– 버블 정렬 : arr[i]와 뒤의 원소들을 비교하는 게 아닌, 인접한 두 요소 arr[j], arr[j+1]를 비교
– i == 패스 횟수
– j == 인접 원소 비교 위치
– 내부 반복문의 범위
: 앞에서는 항상 0부터, 이미 뒤의 큰 값들이 확정되었기 때문에 다시 비교할 필요없이 i만큼 범위 감소.

• arr[j+1]까지 접근해야하므로 j가 마지막 인덱스 전까지만 가야하므로 -1
  – swapped : 이번 패스에서 교환이 한 번이라도 있었는가?

---

11.분할 정복

# base case: left와 right의 위치가 같을 때
# 현재 탐색 범위 left ~ right의 중간 인덱스 mid를 구함
# l_max는 left~mid 범위로 find_max_divide_conquer 재귀 호출
# r_max는 mid+1~right 범위로 find_max_divide_conquer 재귀 호출
# 각 재귀가 자기 범위의 최댓값을 반환
→ l_max와 r_max 비교
→ 현재 범위의 최댓값을 부모에게 반환

– left == right
→ 현재 탐색 범위의 시작과 끝 위치가 같음
→ 원소가 딱 1개 남음
→ 더 쪼갤 수 없으므로 base case
→ 그 원소 arr[left]가 이 범위의 최댓값

현재 범위: left ~ right

        mid
         ↓
[left .... mid] [mid+1 .... right]
      ↓                 ↓
    l_max             r_max
      └────── 비교 ─────┘
              ↓
          더 큰 값 반환

---

14.연결리스트

1.Node 생성
	- self.data = data -> 전달받은 값 저장
    - self.next = None -> 아직 다음 노드가 없으므로 None
    
2.head (연결리스트 시작점) 생성
	-> 처음에는 노드가 하나도 없으니까 None
    
3.append(data)
- 비어있다면
	-> head가 new_node를 가리키게 하고 return
- 비어있지 X
	-> 마지막 node를 찾음
    - 탐색용 변수 current 생성
      : current = self.head
      -> current.next가 존재하는 동안 current를 다음 Node로 이동
    -> 위 반복문이 끝난 현재상태 : current.next == None
	-> 마지막 노드의 current.next에 new_node 연결(current가 마지막 이니까)

4. print_list()
- 결과 담을 빈 values [] 준비
- current = self.head에서 시작
- current == None이 될 때까지 순회
	① current.data를 values에 추가
    ② current를 current.next로 이동
- values 반환

Node 한 칸
┌────────────┐
│data │ next│
└────────────┘
- self.data = data
→ Node가 자기 값을 저장
- self.next = None
→ 생성 직후에는 연결된 다음 Node가 없음

LinkedList
    │
   head
    ↓
   None       ← 처음에는 비어 있음
   
- self.head = None
→ LinkedList는 첫 번째 Node가 어디인지 기억
→ 처음에는 Node가 하나도 없으므로 None

new_node = Node 자체
new_node.data = Node 안의 값
new_node.next = 다음 Node

current = 현재 Node 자체
current.data = 현재 Node의 값
current.next = 다음 Node

head = 첫 Node를 가리킴

• append
  → 마지막 Node에서 멈춰야 함
  → current.next가 None이면 끝

• print_list
  → 마지막 Node의 값까지 읽어야 함
  → current 자체가 None이 될 때까지