바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

Global variable: 실행하는 파이썬 파일 전체 영역에서 사용 가능한 변수

Local variable: 특정 지역 범위에서만 영향을 주고 받을 수 있는 변수

(ex. 특정 함수 내에서 선언한 변수는 return되지 않는 한 함수 밖에서 사용될 수 없다)

#1

a = 1 #Global

def function():
	print(a) 
    # 함수 내에서 별도 변수를 선언하지 않았으므로, Global과 구분되는 Local이 없음
    # 함수 전체에 적용되는 Global 'a'가 적용됨
   
funtion()
print(a)

>> 1 \n 1

여기서 a는 Global variable이다. 

함수 내에서 별도 변수를 선언하지 않았으므로 Local variable은 없다.

함수에서 별도로 변수를 선언하지 않으면 a는 global variable이다.

#2

def function():
	a = 1
    print(a)
    
function()
print(a)

>> 1 \n error

여기서 Global variable은 없다.

함수 내에서만 변수를 선언했으므로 이것은 Local variable, 밖에서 가지고 오면 error 발생.

#3

a = 1 #Global

def function():
	a = 2 #Local
    print(a) #Local
   
function() #Local
print(a) #Global
 
 >> 2 \n 1

Python

global vs nonlocal

global

Global variable: 실행하는 파이썬 파일 전체 영역에서 사용 가능한 변수

함수 내에서 선언한 variable은 기본적으로 해당 함수에서만 사용 가능한 Local이지만, Local을 Global로 전환하는 역할.

때문에 함수 밖에서 선언된 건 global 쓸 필요 없음 (이미 Global인 상태)

#1

a = 1

def function():
	global a #함수 안에서 Local이 아닌 Global을 사용하기로 선언한다
    a = 2 #Global variable 'a'가 2가 된다
    print(a)

function() #Global
print(a) #Global

>> 2 \n 2

이때 global 선언문과 & a에 대한 식을 별도로 지정해야 한다.

#2

def function():
	global a #Local -> Global
    a = 10 #Global
    print(a) #Global

function() #Global
print(a) #Global

>> 10 \n 10

함수 밖에서 변수를 이미 선언하지 않더라도, 함수에서 처음 생성한 변수를 Global variable로 지정할 수 있다.

nonlocal

주로 함수 def 내의 또 다른 함수 def에서 사용됨

nonlocal: lower scope에서의 local variable을 upper scope에서의 local variable로 전환하는 역할

아래 예시에서, function2에서 선언한 a는 기본적으로 function2에서만 사용 가능한 local인데,

그것의 상위 함수인 function1에서 선언한 local으로 전환(연결)하겠다는 의미.

def function():
	a = 1 # function1의 Local
    def function2():
    	nonlocal a
        a = 2
        # nonlocal: function2의 Local -> function1의 Local
        #           function1의 a를 사용하겠어 (연결되겠어)
        # upper scope에서의 variable에 access
        # != Global (whole scope)
        
    function2()
    print(a)
    
>> 2

끝~

https://codingpractices.tistory.com/entry/Python-%EC%A0%84%EC%97%AD-%EB%B3%80%EC%88%98-%EC%A7%80%EC%97%AD-%EB%B3%80%EC%88%98-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%B4%9D-%EC%A0%95%EB%A6%AC-global-nonlocal

⬆️ 위 페이지에 잘 정리되어 있음 !!!

수많은 reportUnboundVariable error

이유를 탐색해보았다.

Reference

https://stackoverflow.com/questions/63388372/why-there-is-an-unbound-variable-error-warning-by-ide-in-this-simple-python-func

➡️ Because range(4) might be something empty (if you overwrite the built-in range), in which case the loop body will never run and a will not get assigned. Which is a problem when it's supposed to get returned.

➡️ Meaning of 'Unbound'

• A symbol that has not been given a value by assignment or in a function call is said to be “unbound.”
• An unbound variable is one that is not within the scope of a quantifier.

➡️ 해결: while문 선언 전 'mid'에 대한 default value를 할당해주었다.

Insertion Sort (삽입 정렬)

: human-like

1. 처음 주어지는 것: 빈 리스트 & 정렬해야 하는 카드들
2. 원리: index 순서대로 읽어가며 이미 정렬된 value들과 크기 비교하여 적절한 위치에 삽입함

• 새로운 빈 리스트를 하나 생성하는 것 대신(메모리 많이 잡아 먹음)
• ⇒ in-place기법 (주어진 표를 변형 + 원본이 훼손됨)

def insertion_sort(list):
	for i in range(i, len(list)):
    	key = list[i]
        j = i-1
        while j >=0 and key < list[j]:
        	list[j+1] = list[j]
        	j -= 1
        list[j+1] = key

1. sorted된 아이템들 중에 현재 Key와의 비교가 이루어질 위치 탐색: O(N) -> binary search 통해 O(logN)
2. shift : O(N)
3. 각 key에 대한 location 최종 삽입: O(1) (이미 1, 2단계로 location이 최종 선택된 상태)
4. 1~3의 단계를 N(=len(list)) 만큼 반복

=> Overall complexity: O(N^2)

관련 문제: 백준 11399 (ATM)

https://www.acmicpc.net/problem/11399

문제 개요

N명, i번 사람이 돈을 인출하는데 P_i분 소요

줄을 서는 순서에 따라 돈을 인출하는 데 각 사람이 인출하는 데 필요한 시간의 합이 달라짐

Input

줄을 서 있는 사람 수 N (ex. 5)

각 사람이 돈을 인출하는 데 걸리는 시간 P (ex. 3 1 4 3 2)

Output

각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값 (ex. 32)

문제 풀이

Pseudo Code

: for문으로 key를 하나씩 지정

각 key의 위치를 while문 통해 탐색

그렇게 필요한 위치를 하나씩 탐색.

비록 시간 복잡도는 n^2

(3, 1, 4, 3, 2)

1 2 3 4 5 => (3, 1, 4, 3, 2) => 39분 (작은 값을 마냥 앞에 배치한다고 개선되지 않음)

2 5 1 4 3 => (1, 2, 3, 3, 4) => 32분

결론: value의 오름차순 소팅! (삽입정렬로 해결)

import sys

for t in range(2):
    if t == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = list(map(int, sys.stdin.readline().split()))

for i in range(1, n):
    key = inputs[i]
    j = i-1
    while j>=0 and key < inputs[j]:
        inputs[j+1] = inputs[j] //swap
        inputs[j] = key //swap
        j -=1 //최종 목적지까지 계속 탐색

answer = [0]
for x in inputs:
    answer.append(x+answer[-1])

print(sum(answer))

https://www.acmicpc.net/problem/11660

👀👉 구간 합 기본 개념 및 전략

Input

표의 크기 N(NxN), 합을 구해야 하는 횟수 M(아주 큼)

둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다

다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어짐

ex. 
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

output

(x1, y1)부터 (x2, y2)까지 합, 총 M개 (각 줄에 하나의 값, M줄)

ex. 

27

6

64

문제 풀이

1. 단순한 구간 합으로 ,,,, 단순 비효율적으로 => 시간 초과

#시간초과

import sys

[N, M] = list(map(int, sys.stdin.readline().split()))
inputs = []
outputs = []
for i in range(N+M):
    if i < N:
        inputs.append(list(map(int, sys.stdin.readline().split())))
    else:
        outputs.append(list(map(int, sys.stdin.readline().split())))

sum_lst = [[0 for _ in range(N)] for _ in range(N)]  # [[0]*N]*N
max_y = max([x[3] for x in outputs])
sums = 0

for y in range(max_y):
    for x in range(N):
        sums += inputs[y][x]
        sum_lst[y][x] = sums

for [a, b, c, d] in outputs:
    if a==c and b==d:
        print(inputs[c-1][d-1])
        continue
    elif a==1 and b==1:
        print(sum_lst[c-1][d-1])
        continue
    elif a>=2 and b==1:
        print(sum_lst[c-1][d-1] - sum_lst[a-2][-1])
        continue
    else:
        f_sum = 0
        for t in range(a-1, c):
            f_sum += sum_lst[t][d-1] - sum_lst[t][b-2]
        print(f_sum)

2. 합 배열과 구간 합의 변용 (중복처리 중요)

문제에 따른 조작적 정의

- 합 배열 :

• 단순히 1번 원소부터 특정 원소까지 다 더한 합이 아니라, 처음부터 직사각형 형태의 합으로 구함
• 점화식의 초항처럼, x=0, y=0일 때의 가장자리 원소를 별도로 구해줌 (base)
• 가장자리 원소(x,y)까지 직사각형 형태의 합 = (x-1까지 직사각형) + (y-1까지 직사각형) - ((x-1, y-1)까지 직사각형)

- 구간 합: 직사각형 형태로 도출될 수 있도록 구함

• (x2,y2)에서 합 배열의 원소 - (x1-1, y2)에서 합 배열의 원소 - (x2, y1-1)에서 합 배열의 원소 + (x1-1, y1-1)에서 합 배열의 원소

import sys

[N, M] = list(map(int, sys.stdin.readline().split()))
inputs = []
outputs = []
for i in range(N+M):
    if i < N:
        inputs.append(list(map(int, sys.stdin.readline().split())))
    else:
        outputs.append(list(map(int, sys.stdin.readline().split())))

sum_lst = [[0 for _ in range(N)] for _ in range(N)]  # [[0]*N]*N
max_y = max([x[3] for x in outputs])

#default setting
sum_lst[0][0] = inputs[0][0]
for x in range(1,N):
    sum_lst[0][x] = sum_lst[0][x-1] + inputs[0][x]
    
for y in range(1,max_y):
    sum_lst[y][0] = sum_lst[y-1][0] + inputs[y][0]


for y in range(1, max_y):
    for x in range(1, N):
        sum_lst[y][x] = sum_lst[y-1][x] + sum_lst[y][x-1] - sum_lst[y-1][x-1] + inputs[y][x]

    
for [x1, y1, x2, y2] in outputs:
    if x1 == x2 and y1==y2:
        print(inputs[x1-1][y1-1])
    elif x1>=2 and y1 >=2:
        print(sum_lst[x2-1][y2-1] - sum_lst[x1-2][y2-1] - sum_lst[x2-1][y1-2] + sum_lst[x1-2][y1-2])
    elif x1==1 and y1>=2:
        print(sum_lst[x2-1][y2-1] - sum_lst[x2-1][y1-2])
    elif x1>=2 and y1==1:
        print(sum_lst[x2-1][y2-1] - sum_lst[x1-2][y2-1])
    else:
        print(sum_lst[x2-1][y2-1])

구간 합 개념

: 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 (가능한 케이스 개수가 극단적으로 많을 경우 특히!)

*핵심: 합 배열 S의 정의

S[i] = A[0] + A[1] + A[2] + .... A[i-1] + A[i]

=> 기존 배열의 일정 범위의 합을 구하는 시간 복잡도: O(N)

=> A[i]~A[j]까지 배열 합: 최악은 i가 0이고 j가 N이므로.

<=> 합 배열을 미리 구해 놓으면 : O(1)로 감소

구현 공식: S[i] = S[i-1](재귀느낌) + A[i](특정 원소)

=> 이것을 기본으로, 문제에 따라 다양한 변용!

구간 합 구현

구현 공식: S[j] - S[i-1]

=> 이것을 기본으로, 문제에 따라 다양한 변용!

https://youtu.be/O514yiWg8YE

https://www.acmicpc.net/problem/17298

1. 문제 개요

1.1 Input

N (ex. 9)

크기가 N인 수열 A (ex. 10 1 2 3 11 4 5 6 12)

1.2 Output

A의 각 원소에 대한 오큰수 배열(*오큰수 NGE(I): 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수)

(ex.  [11,2,3,11,12,5,6,12,-1])

2. 문제 풀이

2.0 귀찮은 백준 입력 세팅: 여러 줄을 입력으로 받는다 (for문 활용 + sys.stdin.readline())

import sys

for y in range(2):
    if y == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = deque(map(int, sys.stdin.readline().split()))

2.1 진짜 단순하게 하나씩: O(n^2)

from collections import deque

answer = deque()
for t in range(n):
    now = inputs.popleft()
    for i in inputs:
        if i > now:
            answer.append(i)
            break
        else:
            continue
    if len(answer) < t+1:
        answer.append(-1)

print(*answer)

Tip: 리스트 내 원소만 출력하고 싶으면, print(*리스트)

2.2 reverse

탐색 문제 풀이 시 input과 output의 관계(경향)을 잘 살피고

• reverse 탐색 / 양방 탐색 등의 방법도 고려해야 함
• 발상의 전환! 반대 방향으로 탐색하면 더 효율적이지 않을까? => 본 문제에서는 여전히 O(n^2)

2.3 O(n^2) => O(n)으로 효율화 필요함! 

• for 문을 한 번만 쓰는 방법,, + 이미 오큰수 구한 원소는 고려 대상에서 제외하는 거,,
• 리스트 내 원소 i는 순차적으로 한 번씩 탐색 (유일한 for문)
• answer = [-1] * n
• stack!! => 오큰수를 찾지 못한 원소의 index를 stack에 저장해두고, 완료된 것은 지움으로써, 당장 필요한 원소만을 추리는 기능
  • stack = [0] 으로 시작 (base case에 대한 사전 처리)
  • while 현재 탐색 중인 i가 stack의 top보다 크면, i는 top의 오큰수가 됨! (이하이면 pass)
  • stack에서 top을 pop (이미 오큰수 구하였으므로 제거) & top의 Index 위치에 해당하는 answer의 value에 오큰수를 저장
  • while 문 끝나면 i가 stack에 append

for y in range(2):
    if y == 0:
        n = int(input())
    else:
        inputs = list(map(int, input().split()))

answer = [-1] * n
stack = [(0)]

for i in range(1, n):
    if inputs[stack[-1]] >= inputs[i]:
        pass
    else:
        while stack and (inputs[stack[-1]] < inputs[i]):
            answer[stack[-1]] = inputs[i]
            stack.pop()
    stack.append((i))
print(*answer)

Tip: stack 저장 대상에 index만 있을 수 있음!

Tip: 반복문에서 pass VS continue

Tip: while stack and 조건: 해당 조건문이 stack이 False인 상태에서 에러 발생!

스택 Stack

1. 마지막에 넣은 것이 - 먼저 나온다
2. stack의 top: 삽입과 삭제가 일어나는 위치
3. s.append(data): top 위치에 새로운 데이터 삽입
4. s.pop(): top 위치의 현재 데이터를 삭제하고 확인
5. s[-1]: top 위치의 현재 데이터를 단순 확인

• DFS: 깊이 우선 탐색
• 백트래킹 종류
• 재귀 알골과 일맥상통

큐 Queue

1. 먼저 들어온 것이 - 먼저 나간다
2. 파이썬에서 deque를 이용하여 큐를 구현 (import collections)
3. stack의 top과 달리, rear(가장 끝)와 front(가장 앞)가 있음
4. s.append(data): rear에 새로운 데이터 삽입
5. s.popleft(): front 부분의 데이터를 삭제하고 확인
6. s[0]: 큐의 맨 앞(front) 데이터 확인

• BFS: 너비 우선 탐색
• 우선순위 큐: 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나옴. ⇒ front에 항상 최댓값 또는 최솟값
  • 힙(heap)을 이용해 구현.

https://youtu.be/JwOFYxirPPU

https://data-analysis-science.tistory.com/61

https://lsjsj92.tistory.com/543

1. 자카드 유사도(Jaccard similarity)

정의: 교집합 / 합집합

- '유무'만 따짐: set

- '유'인 것들 사이의 rating value를 비교하지 않음

2. 코사인 유사도(Cosine similarity)

- '유'인 것들 사이의 rating value를 비교함: points

정의:

import numpy as np
from numpy import dot
from numpy.linalg import norm

def cos_sim(A, B):
  return dot(A, B)/(norm(A)*norm(B))

doc1 = np.array([0,1,1,1])
doc2 = np.array([1,0,1,1])
doc3 = np.array([2,0,2,2])

print('문서 1과 문서2의 유사도 :',cos_sim(doc1, doc2))
print('문서 1과 문서3의 유사도 :',cos_sim(doc1, doc3))
print('문서 2와 문서3의 유사도 :',cos_sim(doc2, doc3))

- 결측치를 'negative'한 값으로 취급함

- recommendation system에 바로 적용하는 데 한계가 있음

3. 피어슨 상관계수 (Pearson correlation coefficient)

- 정의: 각 값을 '평균과의 차이', 즉 '편차'로 변환한 후, 코사인 유사도를 계산함

- 없는 정보(결측치)를 예측하는 경우(ex. recommendation)에 유용함

Reference:

https://wikidocs.net/24603

http://taewan.kim/post/norm/

https://blog.naver.com/cindyvelyn/222136360080