알고리즘 기초 입문을 위해 공부한 DO IT! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬편을 통해 새로 알게 된 내용을 정리

1. Mutable(list vs tuple)

: 배열은 Mutablity(변경 가능 유무)에 따라 list(mutable)와 tuple(immutable)로 나뉜다.

- tuple : 원소 하나일 때, 원소 뒤에 반드시 쉼표!
tuple1 = 1,
tuple2 = (1,)

: (Mutable) 리스트, 딕셔너리, 집합
: (Immutable) 수, 문자열, 튜플

2. Slice

2-1. 기초

: s[i:j:k] = s[i]부터 j개 k씩 건너뛰며 나열

2-2. s[i:j:k] 규칙

• i > len(s), i = len(s)
• i == None, i = 0
• j > len(s) or j == None, j = len(s)

[example]

s= [1,2,3,4,5,6,7]
s[3:] => [4,5,6,7]
s[-3:] => [5,6,7]
s[::2] => [1,3,5,7]
s[::-1] => [7,6,5,4,3,2,1]

3. 파이썬의 중요 원칙

3-1. 원칙

변수에 어떤 값을 대입하면 변수가 값을 복사하는 것이 아니라 단순 참조하는 것이다.

3-2. 등가성(==) vs 동일성(is)

• 등가성 : 좌변과 우변의 값이 같은 지 확인
• 동일성 : 좌변과 우변의 값과 각 객체의 식별번호까지 같은지 확인

4. 함수

4-1. enumerate()

: 배열의 인덱스, 값을 튜플로 짝지어 내보낸다.
: 두번째 매개변수 1을 넣어서 index 시작값을 1로 조정가능(default = 0)

arr = ['s', 'e', 'h']
for i, name in enumerate(arr, 1):
	print(f'arr[{i}] = {name}')
>> 
arr[1] = s
arr[2] = e
arr[3] = h

4-2. 역순 정렬

• arr[::-1]
• arr.reverse()
• xrr = list(reversed(arr)) : 배열 리턴해준다

5. 기수와 서수

5-1. 정의

• 기수 : 수를 나타내는 기초 (ex. 10진수 (0~9)에서 10이 기수)
• 서수 : 사물의 순서 (ex. 첫째, 둘째, 셋째 )

5-2. 10진수 값 받아 n진법으로 바꾸기

def card_conv(x: int, r:int) -> str:  
  dchar = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  result = ""
  while x > 0:    
    result += dchar[t%r]
    x//=r
  return result[::-1]

5-3. 입력(n진수를 10진수로)

n = int(input(),16)
print(n)
=> (n이 A일 때) 10 

5-4. 출력(n진수로)

- print('%x'%a) : 16진수로 출력, X로 하면 대문자 출력
- print(format(a,'x')
- print(format(a,'8x') : 앞에 8칸 띄우기
- print(format(a,'#8x') : 0X11 

6. callByValue vs callByReference

• call by value : 함수의 매개변수에 인수 값을 직접 복사하여 함수 내부에서 호출
• call by reference : 함수의 매개변수에 인수의 참조를 복사하여 함수 내부에서 호출
• call by object reference : [파이썬 특징] 인수가 참조하는 객체를 매개변수도 함께 참조하여 함수 내부에서 호출
  - 참조하는 객체가 immutable이면, 함수 내부에서 매개변수의 값의 변화에 인수가 영향을 받지 않는다.
  - 참조하는 객체가 mutable이면, 함수 내부에서 매개변수의 값의 변화를 인수가 영향을 받는다.

7. 소수 계산

7-1. 소수 정의

: 1과 자신 이외의 정수로 나누어 떨어지지 않는 정수

2부터 n-1까지 어떤 정수로도 나누어 떨어지지 않는다.

7-2. n까지 소수 구하기

[알고리즘 1]

n = int(input())
for i in range(2,n):
  for j in range(2,i):
    if i%j == 0 : break;
  else :
    print(i)
    
    
[알고리즘 2] : 2부터 n-1까지 어떤 소수로도 나누어 떨어지지 않는다. 

n = int(input())
sosu = [None] *500 
sosu[0] = 2
ptr = 1

for i in range(3,n,2):
  for j in range(1,ptr):
    if i%sosu[j] == 0 : 
      break;
  else :
    sosu[ptr] = i
    ptr +=1
print(sosu)


[알고리즘 3] : n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.

n = int(input())
sosu = [None] *500 
sosu[0] = 2
sosu[1] = 3
ptr = 2


for i in range(5,n,2):
  j = 1
  while sosu[j]*sosu[j] <= i:
    if i%sosu[j] == 0 : break;
    j +=1;      
  else :
    sosu[ptr] = i
    ptr +=1

print(sosu)

8. 깊은 복사 vs 얕은 복사

8-1. 얕은 복사

: 객체 복사 시, 객체의 참조값만 복사하는 방식

x= [[1,2,3],[4,5,6]]
y = x.copy()
x[1][0] = 7
print(x) => [[1,2,3],[7,5,6]]
print(y) => [[1,2,3],[7,5,6]]

8-2. 깊은 복사

: 객체 복사 시, 객체의 참조값 뿐 아니라 참조하는 객체 자체를 복사

import copy
x= [[1,2,3],[4,5,6]]
y = x.copy.deepcopy()
x[1][0] = 7
print(x) => [[1,2,3],[7,5,6]]
print(y) => [[1,2,3],[4,5,6]]