writerq1

command + d : 같은 단어 자동 검색 및 선택

m1 맥os로 바꾼 이후 vs code가 파이썬 가상환경을 반영안하길래,

pipenv --venv

를 이용해서 경로를 확인하고

settings.json 파일에

python.pythonPath 변수에 해당 경로를넣어줬다.

해당 라인이 자꾸 지워지는 에러가 발생함.

애플 m1이라 그런건진 모르겠다.

vscode 커맨드를 이용해서 select python interpreter를 이용했는데,

가상환경안에 있는데도, 해당 인터프레터 경로가 보이지 않음..

한참 헤맸지만 스크롤을 내리니까 있었음....

커맨드로 선택하니 잘 반영됨

아직 python pillow가 m1을 지원하지 않아서,

wheel을 사용해서 인스톨을 해야했다

github.com/python-pillow/Pillow/issues/5093

의 내용을 참고했는데,

Pillow-8.0.1-cp39-cp39-macosx_11_0_arm64.whl.zip

파일을 깔고 압축 해제후

$ python3 -m pip install packaging

$ python3 -c"from packaging import tags; print('\n'.join([str(t) for t in tags.sys_tags()]))" |head -5

를 하면 tag 이름이 나오는데,

위에 해제한 파일 이름을 바꾸고

pipenv install 파일명

을 해주면 된다.

그런데 신기하게 pipenv shell 안에서의 tag 명과,

그냥 pip을 사용하기 위해서 global한 상태에서 확인한 tag명이 달랐다.

아마도,, python 버전차이인거 같은데, 정확히 뭔진 모르겠다

xcode-select --install

ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

install 후에

Next steps:

- Add Homebrew to your PATH in /Users/kyuwonpark/.zprofile:

    echo 'eval $(/opt/homebrew/bin/brew shellenv)' >> /Users/kyuwonpark/.zprofile

    eval $(/opt/homebrew/bin/brew shellenv)

위에 2명렁어를 순서대로 입력함.

brew help하면 먹힘

vi ~/.zprofile

을 통해서 zprofile에 접근할 수 있다

django 공부하면서 중요한 내용들 메모

user 모델 같은 경우는 장고에서 기본적으로 제공하기 때문에

overriding 해서 사용. 

Admin 뿐만 아니라 model 자체에서 function을 넣을 수 있다.

Python manage.py shell을 치면 쉘커맨드로 서버에 접속해볼수 있다.

Media file upload하기

setting에 media root 설정, media_url 설정

*media url에서 앞에 /를 붙이나 안붙이나가 차이가 있다.

python dir 혹은 vars

프린트해보기, 아주 실용적

django snippet (VS)

admin 의 save_model method (admin을 통해 save할때 작동)

model 의 save method (어떤 방법이든 모델이 save될때 작동)

super()를 활용해서 추가적인 기능 넣기

seeder는 foreign key 컬럼까지 생성해주진 않음

별도의 코드가 필요하다

django template의 경우

tag 이나 filter항목을 잘 찾으면 유용한 기능이 있다

queary sets are lazy

doc에서 찾아볼것. 쿼리는 바로 호출되지 않는다. all() 함수라도.

나중에 해당 variable을 호출할때 로드가 걸림.

pagiantion

dir이나 vars이용하고 doc읽어보기

django template같은 경우에는 문법이 파이썬과는 다르다.

pagination object의 함수를 불러올때도 ()를 별도로 쓰지 않는 것처럼,

템플릿을 잘 활용하려면 따로 공부가 필요할듯

tag 이나 filter같은 것들이 있음

url지정할때

namespace와 name을 잘 활용하면

장고템플릿에서 url tag 활용해서 링크를 만들기 수월하다.

A star algorithm은 길찾기 알고리즘으로 유다시티 수업 마지막 프로젝트로도 나왔다.

생각보다 재밌는 알고리즘 이었다.

그리디 알고리즘으로도 길찾기 문제는 해결할 수 있는데, 사실상 효율적이지 않다는 문제가 있다.

start node 중심에서 원형으로 모든 가능성에 대해서 길찾기를 하게 됨으로

방향성을 가지고 길찾기를 할 수 있도록, 알고리즘에 약간의 수정을 해야 한다.

function = g + h

g = cost of the path

h = estimated distance to the goal

위의 function의 값이 최소화가 되는 방향으로 알고리즘을 짜는 문제다. 

아래는 내가 프로젝트로 냈었던 문제다. 피타고라스정리를 이용해서 거리를 계산해가고 있으며

그리디 알고리즘에 h 요소를 집어넣어 문제를 해결할 수 있었다.

def shortest_path(M,start,goal):
    explored = []
    frontiers = {}

    for neighbour in M.roads[start]:
        route = [start, neighbour]
        distance_from_start = math.sqrt((M.intersections[start][0] - M.intersections[neighbour][0])**2 + (M.intersections[start][1] - M.intersections[neighbour][1])**2)
        distance_to_goal = math.sqrt((M.intersections[goal][0] - M.intersections[neighbour][0])**2 + (M.intersections[goal][1] - M.intersections[neighbour][1])**2)
        total_distance = distance_from_start + distance_to_goal
        frontiers[neighbour] = Intersection(route, distance_from_start, distance_to_goal, total_distance)

    explored.append(start)

    while frontiers:
        smallest_frontier = sorted(frontiers.items(), key=lambda x: x[1].total_distance)[0]
        smallest_fron_key = smallest_frontier[0]
        explored.append(smallest_fron_key)
        if smallest_fron_key == goal:
            print("shortest path called")
            return smallest_frontier[1].route

        for neighbour in M.roads[smallest_fron_key]:
            if neighbour not in explored:
                route = smallest_frontier[1].route.append(neighbour)
                distance_from_start = smallest_frontier[1].distance_from_start + math.sqrt(
                    (M.intersections[smallest_fron_key][0] - M.intersections[neighbour][0])**2 + (M.intersections[smallest_fron_key][1] - M.intersections[neighbour][1])**2
                    )
                distance_to_goal = math.sqrt((M.intersections[goal][0] - M.intersections[neighbour][0])**2 + (M.intersections[goal][1] - M.intersections[neighbour][1])**2)
                total_distance = distance_from_start + distance_to_goal
                if frontiers.get(neighbour) != None and total_distance > frontiers[neighbour].total_distance:
                    continue
                frontiers[neighbour] = Intersection(route, distance_from_start, distance_to_goal, total_distance)

    if not frontiers:
        return -1

knapsack Problem

item 마다 weight 과 value가 있고, 정해진 weight limitation 하에 최적의 value를 구하는 문제.

모든 경우의 수를 다 따지려면 2의 n제곱 만큼의 time complexity가 필요하다.

dynamic programming은 문제를 나누어서 접근하는 방법으로 divide and conquere과도 비슷하다.

보통의 경우 lookup table을 두는데,

subproblem에 대한 solution들을 저장해 둔다.

추가 되는 경우의 수마다 최적값을 업데이트 해나가는데,,

내 생각에 이는 greedy 알고리즘과도 비슷하게 느껴졌다.

문제의 핵심은 problem을 subproblem으로 break down 할 수 있느냐는 부분.

def knapsack_max_value(knapsack_max_weight, items):
    
    # Initialize a lookup table to store the maximum value ($) 
    lookup_table = [0] * (knapsack_max_weight + 1)


    # Iterate down the given list
    for item in items:
        
        # The "capcacity" represents amount of remaining capacity (kg) of knapsack at a given moment. 
        for capacity in reversed(range(knapsack_max_weight + 1)):
            
            if item.weight <= capacity:
                lookup_table[capacity] = max(lookup_table[capacity], lookup_table[capacity - item.weight] + item.value)

    return lookup_table[-1]

What is graph

node(or vertex)사이의 관계를 나타낼 수 있는 자료구조.

tree도 graph의 한 종류라고 할 수 있다.

node 사이에는 연결선 (edge)가 존재한다.

graph는 root이 따로 없고, circle형태도 가능하다.

edge역시 data값을 지닐 수 있다. (보통 strength of connection, 예를 들어 거리)

**A star 알고리즘에서처럼 길찾기 알고리즘을 구현할 때 유용한 자료구조.

Directions and cycles

edge는 direction을 지닐 수 있고 아닐 수도 있다. (한방향만으로만 연결된 node)

cycle은 infinite loop의 가능성을 준다.

Connectivity

모든 노드가 edge로 연결되어 있어야 하는 것이 아니기 때문에,

연결이 끊긴 node가 있을 수 있다. disconnected graph.

연결이 끊긴 node끼리 그래프를 만들수도 있다.

최소한으로 몇개의 edge를 끊으면 disconnected graph가 되는지 개수를 세어서,

connectivity의 strength를 체크해볼 수 있다.

Graph representation

Object oriented language 를 사용하는 경우라면 node(vertex)나 edge를 object 형식으로 만들수 있다.

list 형식으로도 관리할 수 있는데

예를 들면 edge list, [[1,3],[2,4],[3,6] .... ]

노드의 아이디넘버를 통해 엣지를 리스트화 하는 방법.

adjacency list

[[1], [0,2,3], [1,3] ...]

리스트의 인덱스가 node 역할을 해서 인접한 노드를 list로 정리하는 방법.

adjacency matrix

3d 형태로 list안에 list를 넣는 방식.

Searching의 경우 tree와 비슷하게 stack와 queue를 활용할 수 있다.

DFS

def dfs_search(root_node, search_value):
    visited = set()                         # Sets are faster for lookups
    stack = [root_node]                     # Start with a given root node
    
    while len(stack) > 0:                   # Repeat until the stack is empty
            
        current_node = stack.pop()          # Pop out a node added recently 
        visited.add(current_node)           # Mark it as visited

        if current_node.value == search_value:
            return current_node

        # Check all the neighbours
        for child in current_node.children:

            # If a node hasn't been visited before, and not available in the stack already.
            if (child not in visited) and (child not in stack):         
                stack.append(child)

BFS

def bfs_search(root_node, search_value):
    visited = set()                           # Sets are faster while lookup. Lists are faster to iterate.
    queue = [root_node]
    
    while len(queue) > 0:
        current_node = queue.pop(0)
        visited.add(current_node)

        if current_node.value == search_value:
            return current_node

        for child in current_node.children:
            if child not in visited:          # Lookup
                queue.append(child)

매 step 마다 최적의 해를 구하면 최종적인 방식도 최적이 되는 재밌는 알고리즘.

매 스텝마다 최적의 해를 구한다는 의미로 greedy라는 표현을 쓴 것 같은데, 곰곰히 들여다볼수록 재미있는 부분이 많다.

코드를 확인해 보면, 결국 매step의 선택이 가장 최선의 선택임을 알 수 있다.

import sys

'''Find the shortest path from the source node to every other node in the given graph'''
def dijkstra(graph, source):
    
    result = {}
    result[source] = 0                 
    
    for node in graph.nodes:
        if (node != source):
            result[node] = sys.maxsize
            
    unvisited = set(graph.nodes)  
    
    path = {}

    '''THE GREEDY APPROACH'''
    # As long as unvisited is non-empty
    while unvisited: 
        min_node = None    
        
        # 1. Find the unvisited node having smallest known distance from the source node.
        for node in unvisited:
            if node in result:
                
                if min_node is None:       
                    min_node = node
                elif result[node] < result[min_node]:
                    min_node = node

        if min_node is None:
            break
            
        # known distance of min_node
        current_distance = result[min_node]
        
        # 2. For the current node, find all the unvisited neighbours. 
        # For this, you have calculate the distance of each unvisited neighbour.
        for neighbour in graph.neighbours[min_node]:
            if neighbour in unvisited:
                distance = current_distance + graph.distances[(min_node, neighbour)]
            
                # 3. If the calculated distance of the unvisited neighbour is less than the already known distance in result dictionary, update the shortest distance in the result dictionary.
                if ((neighbour not in result) or (distance < result[neighbour])):
                    result[neighbour] = distance

                    # 4. If there is an update in the result dictionary, you need to update the path dictionary as well for the same key.
                    path[neighbour] = min_node
        
        # 5. Remove the current node from the unvisited set.
        unvisited.remove(min_node)

    return result