[수업기록] 알고리즘 : list(배열, 정렬, 순열-조합, 완전탐색, 그리디, 행렬)

240729~240731

1. 알고리즘이란 

문제를 단계별로 해결하는 방법

 

2. 알고리즘의 작업량을 표현할 때 시간복잡도라는 개념으로 표현한다

1) 시간 복잡도 

- 개념 : 실제 걸리는 시간을 측정 , 실행되는 명령문의 개수를 계산 

- 표기법 : 빅-오(O) 표기법 

-> 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시

O(3n+2) = O(3n)*최고차항만 남겨둠 = O(n) *계수 제거 

O(4) = O(1) # 계수 4 제거

- N 1억개일 때 0.1초 

import math
그럼 n2은?
print((10**8)**2*0.1)
print(math.log2(10**8)*0.1)

---

3. 배열

1) 개념 : 배열(array)이란 무엇인가? 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조

2) 단순히 다수의 변수 선언을 의미하는 것이 아닌, 다수의 변수로는 하기 힘든 작업을 배열을 활용해 쉽게 할 수 있다

#1차원 배열 선언의 예

Arr = list(), Arr =[]
Arr = [1,2,3]  Arr = [0] * 10 
append는 시간이 많이 걸리는 작업이다
데이터가 많을 때 안쓰는 거 추천

 

# 입력받은 정수를 1차원 배열에 저장하는 방법

N = int(input())
arr = list(map(int,input().split())) #빈칸으로 구분된 N개의 양수 Ai가 주어진다 

#1. input() # 1 2 3 4 5 
#2. split() # ['1', '2', '3', '4', '5'] 
#3. map() # 1 2 3 4 5
#4. list() [1,2,3,4,5]

---

4. 정렬 *속도와 메모리 차이, 기능은 같음*

- 정렬 종류 

1) 버블 정렬 O(n2) : 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식 

[55, 7, 78, 12, 42] #오름차순
#1. 가장 왼쪽 오른쪽 두개 비교
#2. 더 큰걸 오른쪽으로 보냄
#3. 배열 맨 끝에 가장 큰 수가 올 때까지, 배열 길이만큼 위 과정 반복 
# 주의 : 갯수에 맞춰 순회하기

# 주의 : 
# 하나일 때는 인덱스를 지정하면 됨
# 두개 이상일 땐 기준 인덱스가 필요함( 기준 인덱스 범위 : 0 -> n-2(여기서는 한 쌍이니까)

 

N = 5

arr = [55, 7, 78, 12, 42]

for i in range(N-1, 0, -1):# 각 구간의 끝 인덱스 i
    for j in range(i):# 각 구간에서 두개씩 비교할 때 왼쪽 원소의 인덱스 j
        if arr[j] > arr[j+1]:# 왼쪽 원소가 더 크면 교환
            arr[j], arr[j+1] = arr[j+1], arr[j]

print(*arr) #언패킹

 

 

2) 카운팅 정렬 : 

- 인덱스별 횟수 파악 -> 시간복잡도가 조금 더 낮음

- 집합에 각 항목이 몇개씩 있는지 세는 작업을 하여 순서를 정함. 선형 시간에 정렬하는 효율적인 알고리즘

- 제한사항 : 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능

- 시간복잡도 : O(n+k) : n은 리스트 길이, k는 정수의 최댓값

arr = [0,4,1,3,1,2,4,1] #카운팅 정렬 과정

#단계 1. 각 항목들의 (0~4) 발생 회수를 세고 정수 항목들로 직접 인덱스 되는 new 배열, 카운트 배열 cnt에 저장
counts = [0] * 5(정수 0~4까지, 총 5개) #new 배열(카운트 배열) 선언 
#counts = [0] * (k+1)
#counts = [0,0,0,0,0]

for num in arr: #ex. 숫자 4 -> 인덱스 4로 
	counts[num] += 1
    
print(counts)
# [1,3,1,1,2]

#단계 2. 각 항목의 앞에 위치하는 항목의 개수 반영 위해 counts 원소 조정(누적합 반영한 새 배열 생성)
for i : 1 -> N-1
	counts[i] = counts[i-1] + counts[i] #현재 내 자리에서 바로 이전 자리와 내 자리 더해서 값 업데이트
#counts = [1,4,5,6,8] 


#단계 3. 0으로 크기를 정해둔 new 배열을(변수 temp) 만들고, counts[arr[i]]의 값을 1 줄여준다
# 줄여주는 이유는 컴퓨터 인덱스 0부터 시작해서!
temp = [0] * N #정렬 결과 저장
for i in range(len(temp)-1, -1, -1):
    counts[arr[i]] -= 1 #[-1,3,4,5,7]
    temp[counts[arr[i]]] = arr[i]
    
print(temp) 


#문법 TIP : for문에서 값을 직접 가져올땐 i, j,k,p,q(인덱스) 안쓰는 게 좋음

---

5. 완전 탐색 

 

-  모든 경우의 수 나열하며 확인 기법 

- 부르프토스, generate-and-test 기법이라고도 불림

- 일반적으로 경우의 수가 작을 때 유용

 

* 순열 : 서로 다른 것들 중 몇개를 뽑아 한줄로 나열

nPr

nPr =(n)  * (n-1) * (n-2) * .. * (n-r+1)

n! = n * (n-1) * (n-2) * .. * 2 * 1

 

> 예제.

{1,2,3}을 포함하는 모든 순열을 생성하는 함수

- 동일한 숫자가 포함되지 않았을 때, 각 자리수 별로 loop 활용

for i1 in range(1,4):
	for i2 in range(1,4):
    	if i2 != i1:
        	for i3 in range(1,4):
            	if i3 != i1 and i3 != 12:
                	print(i1,i2,i3)

 

# %%
# 1) 순열 및 조합의 경우의 수 얻기
import math

# 1-1) 순열(permutation)
# 순서를 고려하여 나열 (ex.줄 세우기)
# ex. [1,2,3] != [2,3,1]
print(math.perm(5,3)) #5_P_3 #5개 중 3개 줄세우기

# 1-2) 조합(combination)
# 순서를 고려하지 않고 나열 (ex. 조 만들기)
# ex. [1,2,3] == [2,1,3] != [1,2,4]
print(math.comb(5,3)) #5_C_3, 다섯개 중 3개 선택

---

6. 탐욕 알고리즘(그리디)

- 최적해를 구하는 데 사용되는 근시안적 방법

- 여러 경우 중 하나를 결정해야 할때마다 그 순간이 최적이라고 생각되는 걸 선택해 나가는 방식으로 최종적 해답에 도달

> 예제 : 거스름돈 줄이기 (지페와 동전 개수를 최소한으로 줄이는 방법)

> 예제 baby gin(트럼프 카드)

#ex. 444345
data = list(map(int, input().split()))

 

i = 0

tri = run = 0#tri, run 0으로 초기화
while i <10:
	if c[i] >= 3: #triple  조사후 데이터삭제
    	c[i] -= 3
        tri += 1
        continue
	if c[i]

---

7. 배열 : 2차원 배열

1) 개념 - 1차원 list를 묶어놓은 list

2) 특징 - 2차원 리스트의 선언 : 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함

N = int(input())
arr = [list(map(int, input())) for _ in range(N)]
#3
#123
#456
#789


arr =[] #아직 빈 배열이 만들어진 것이 아님
arr1 = [0] * 3 
arr2 = [[0] * 3 for _ in range(2)] #2행 #3열
print(arr1) # [0,0,0]
print(arr1) # 0 0 0
for i in range(2):
	print(*arr2[i]) #한 행 다 언패킹
# 0 0 0
# 0 0 0


for i in range(2):
	for j in range(3):
	print(arr2[i][j], end =' ')
	print()

 

3)  2차원 배열의 접근 

- 배열 순회 : n*m 배열의 n*m개의 모든 원소를 빠짐없이 접근

arr = [[1,2,3],[4,5,6]]
print(len(arr)) #행 개수
print(len(arr[0])) #행 번호 -> 원소의 개수 파악



arr = [[0] * 3] * 2
#위는 안됨!
print(arr)
# [[0, 0, 0],
# [0, 0, 0]]
print()

arr[0][0] = 1 #왜냐면
print(arr)
# [[1, 0, 0],
# [1, 0, 0]]
#복사는 아님

(1) matrix = [[set()]*10 for _ in range(10)] #얕은 복사 (이렇게 하면 안됨)
(2) matrix = [[set() for _ in range(10)] for _ in range(10)] #깊은 복사

(1) : 얕은 복사가 되서 특정 인덱스의 set요소에 값을 추가한다면 해당하는 행의 모든 set()들이 다 동시에 값이 바뀜
그래서 (2)와 같이 모두 다른 set()이 메모리에 할당 되도록 해야함

#열 우선 순회
for j in range(M): #열
	for i in range(N): #행
    	array[i][j]
    
# 행, 열 우선 순회 같이
for i in range(N):
	for j in range(M): #행
    array[i][j] #행우선 -> -> 
    array[j][i] #열우선 ↓  ↓

#지그재그 순회 🤔 : 홀수 행은 열의 마지막 인덱스에서 첫 인덱스로 접근 
for i in range(n):
	for j in range(m):
    		arr[i][j + (m-1-2*j) * (i%2)]
            #m-1 -> 인덱스 찾기(끝값)
            # i%2 -> 홀수행이면 1, 짝수행(0 포함, 0은 짝수!)은 0 되어서 j만 남음(그대로 행 출력)

# 델타를 이용한 2차 배열 탐색 😜단골주제😜
# - 2차원 배열 한 좌표에서 4방향의 인접 배열 요소 탐색법
# - 인덱스(i,j)인 칸의 상하좌우 칸(ni,nj)
# - i = 행 , j= 열

# - TIP : 평소 상하좌우 방향 순서 정해두기

# right, down, left, up
di =  [0,1,0,-1]
dj = [1,0,-1,0]


for i in range(N):
    for j in range(M):
        #현재 좌표에서 인접한 요소에 대한 처리
        for di, dj in dirs:
            ni, nj = i + di, j + dj 
            if 0<=ni<N and 0<=nj<M: #인덱스 범위 내인지 검사 필요 #유효한 인덱스면

                print(f"{(ni, nj)}", end=',')

#n*n  2차 배열, 각 요소에 그 요소와 이웃한 요소와의 차의 절댓값 합 구하기
N = int(input())

arr = [list(map(int, input().split())) for _ in range(N)]
print(arr)

di = [0,1,0,-1]
dj = [1,0,-1,0]

total = 0
for i in range(N):
    for j in range(N): #N*N 배열 모든 원소에 대해
        s = 0 #문제에서 원소와 인접원소의 차의 절대값의 합 저장
        # i,j 원소의 4방향 원소에 대해
        for k in range(4):
            ni = i + di[k]
            nj = j + dj[k]
            if 0 <= ni < N and 0 <= nj < N: ##실존하는 인접원소(범위 내)인지 검사
                s += abs(arr[i][j] - arr[ni][nj])
        total += s

print(total)

전치 행렬 
#- 정사각 행렬에서 대각선을 기준으로 행과 열이 바뀐 행렬의미
N, M = len(num_matrix), len(num_matrix[0])

tr_m = deepcopy(num_matrix)
for i in range(N) :
    for j in range(M) :
        if i < j :
            tr_m[i][j], tr_m[j][i] = tr_m[j][i], tr_m[i][j]
print(tr_m)
print('-'*50)

#zip함수 활용 전치 행렬 만들기
tr_m = list(zip(*num_matrix))
print(tr_m)
#[(10, 30, 80), 
# (20, 50, 45), 
# (30, 60, 59)]

대각선 순회, 또는 윗삼각, 아랫삼각 순회

#- ex. 대각선을 기준으로 오른쪽 위가 바뀌게
if i < j:
	arr[i][j], arr[j][i] = arr[j][i], arr[i][j]
    
# 즉, i,j 크기에 따라 접근하는 원소 비교
#- i == j => for i in range(0,n-1): arr[i][i] 대각선(감소형)
#- i > j => 대각선 기준으로 왼쪽 아래
#- 2-i == j => for i in range(0,n-1): arr[i][n-1-i] 대각선(증가형)

 

+ 부분집합 원리

부분집합 생성 방법
#예제 : 집합(배열)이 주어졌을 때 부분집합 중에서 모든 원소 합이 0이 되는 경우 있는지 찾기

# - 부분 집합의 수 :
# -- 집합 원소 n가 있을 때, 공집합을 포함한 부분집합의 수는 2**n 개이다.
# -- 왜? 각 원소를 부분집합에 포함 and 포함시키지 않는 경우 둘이니까
# -- 생성 방법은 행마다 bit = [], bit 배열 활용
# -- 즉, arr[i] 원소가 부분집합에 포함되어있으면 bit[i] ==0 <-> 1

# 비트연산자 : 정보를 이진수로 바뀐 상태에서 연산하는 기호
# bin(), 10진수 숫자를 이진수(binary) 문자열로 바꾸는 함수
# & : 비트 단위로 and 연산
# i & (1<<j) : i의 j번째 비트가 1인지 아닌지 검사

# | : 비트 단위로 or 연산

# <<  : 피연산자의 비트 열 왼쪽 이동
# 1 << n : 2**n 즉, 원소가 n개일 경우의 모든 부분집합의 수 의미

# >> : 비트 열 오른쪽 이동

arr = [3,6,7,1,5,4]
n = len(arr) #n  원소 개수
for i in range(1<<n): # 1<<n 부분 집합 개수
    for j in range(n): #원소의 수만큼 비트 비교
        if i & (1<<j): #i의 j번 비트가 1인 경우 
            print(arr[j],end=",") #j번 원소 출력
    print()
print()

 

왜 비트연산을 하나? 비트연산이 연산 중 가장 빠르다

1 << 0  #1
1을 왼쯕으로 0번 밀면 
1 -> 2^0 #십진수화 

1 << 1 #2
1을 왼쯕으로 한번 밀면 
10 -> 2^1

1 << 2:
100 -> 2^2