index.js는 index.html파일이 열리고 나서 실행되는 파일로, React 코드들 중에서 가장 먼저 실행되는 친구라고 보면 된다. (참고 : index.html은 웹브라우저에서 가장 먼저 실행되는 파일이라 생각하면 됨)
import ReactDOM from 'react-dom';
ReactDOM.render(
<h1>안녕 리액트!</h1>,
document.getElementById('root')
);
코드를 보면 react-dom이란 패키지로부터 디폴트로 export하는 객체를 ReactDOM이란 이름으로 import해서 그 객체의 render라는 메소드를 실행하고 있음을 볼 수 있다. render란 '화면을 그린다'라는 뜻인데, React에선 이 render메소드로 HTML태그를 만들어준다. 독특한 점은 render메소드의 첫 번째 파라미터로 문자열이 아니라 HTML태그를 그대로 작성했단 점인데, 사실 이것은 React에서 지원하는 JSX라는 문법이다. 여기선 일단 이것이 React에서 지원하는 특별한 문법이라고 생각하고 넘어가자.
이어서 코드를 보면, getElementByID를 동해 root라는 아이디를 가진 요소를 파라미터로 넘기는 것을 볼 수 있다. 실제로 render메소드가 실행되면 첫 번째 파라미터를 통해서 HTML요소를 만들고, 이를 두 번째 파라미터에 집어넣는 방식으로 동작한다. index.html의 body태그를 보면 root라는 아이디값을 갖는 div태그를 볼 수 있는데, 바로 여기에 JSX를 통해 만들어진 HTML요소들이 들어가는 것이다.
정리하자면,
1. 우선 React가 실행되면 브라우저가 index.html을 연다
2. index.js를 실행
3. index.js의 render함수가 실행되면서 첫 번째 파라미터(JSX로 작성된 것)을 HTML요소로 바꿔서 두 번째 파라미터에 넣음
보통 react의 render메소드는 index.js에서 한 번만 실행되므로 굳이 사용법을 외울 필욘 없다.
그래프같은 걸 탐색할 때, 너비를 우선으로 탐색을 진행하는 것을 너비우선탐색, 영어로는 Breadth First Search라고 하며 줄여서 BFS라고도 부른다. 어떠한 시작점이 있을 때, 그로부터 가까운 것들부터 탐색해나가는 방법으로 맹목적인 탐색을 할 때 사용가능한 방법이다. 이 녀석은 '최단 경로'를 찾아주기 때문에 최단길이를 보장해야 할 때 많이 쓰인다.
2) 1을 큐에서 빼고, 1을 방문한 지점이라 처리해준 다음 1과 연결된 2, 3, 4를 큐에 넣는다.
3) 먼저 들어온 2를 큐에서 빼며 방문한 지점이라 처리해주고, 연결된 요소 중 방문처리가 안된 5를 큐에 넣어준다.
4) 가장 앞에 있는 3을 큐에서 빼며 방문한 지점이라 처리해주고, 연결된 요소 중 방문처리가 안된 6, 7을 큐에 넣어준다.
...반복
그럼 이걸 파이썬으로 구현해보자.
우선 그래프는 다음과 같이 딕셔너리 형태로 표현해봤다.
graph = {
1 : [2, 3, 4],
2 : [1, 3],
3 : [1, 2, 4, 5],
4 : [1, 3],
5 : [3, 6],
6 : [5]
} # 키에 연결된 value에 있는 리스트가 그 key에 연결된 애들임
그리고 BFS를 도와줄 큐는 다음과 같이 해보자.
queue = [] # 큐를 리스트 형태로 구현
queue.append(something) # 큐에 요소를 넣는 동작 : append ->큐의 뒤쪽에 추가
queue.pop(0) # 큐에 요소를 빼는 동작 : pop(0) ->큐의 앞쪽에 있는 걸 뺌
그럼 BFS를 다음과 같이 만들 수 있다.
def BFS(graph, start_node):
visited = [] # 방문한 요소들이 이 리스트에 저장됨
queue = [start_node] # 큐
while queue: # 큐에 뭔가 있는 동안 이하 내용을 반복한다
node = queue.pop(0) # 큐의 제일 앞에 있는 놈을 빼와서
if node not in visited: # 만약 이 놈이 방문한 적이 없다면
visited.append(node) # 방문처리
print(node) # 그 녀석 출력
queue.extend(graph[node]) # 그 녀석과 연결된 요소들(graph[node])를 queue에 추가
어떤 리스트(A라고 가정)의 append메소드의 파라미터로 리스트를 넘기면 리스트 자체가 A리스트의 마지막 요소로 추가되지만, extend메소드의 파라미터로 리스트를 넘기면 그 리스트 자체가 A리스트에 합쳐진다.
ex) A = [1, 2, 3]이고 B = [4, 5]일때,
A.append(B)를 하면 A = [1, 2, 3, [4, 5]]
A.extend(B)를 하면 A = [1, 2, 3, 4, 5]
근데 이 방법에는 문제점이 있다.
그것을 확인하기 위해 다음과 같이 코드 중간중간에 print를 써서 현재 queue와 visited에 있는 값들을 하나하나 확인해보고, 걸리는 시간까지 알아보자.
import time
def BFS(graph, start_node):
start = time.time()
visited = []
queue = [start_node]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
print(node)
print(f'방문 처리 후 visited : {visited}')
queue.extend(graph[node])
print(f'큐에 연결된 요소 추가 후 queue : {queue}')
print("-"*10)
print(time.time()-start)
1 방문 처리 후 visited : [1] 큐에 연결된 요소 추가 후 queue : [2, 3, 4] ---------- 2 방문 처리 후 visited : [1, 2] 큐에 연결된 요소 추가 후 queue : [3, 4, 1, 3] ---------- 3 방문 처리 후 visited : [1, 2, 3] 큐에 연결된 요소 추가 후 queue : [4, 1, 3, 1, 2, 4, 5] ---------- 4 방문 처리 후 visited : [1, 2, 3, 4] 큐에 연결된 요소 추가 후 queue : [1, 3, 1, 2, 4, 5, 1, 3] ---------- ---------- ---------- ---------- ---------- ---------- 5 방문 처리 후 visited : [1, 2, 3, 4, 5] 큐에 연결된 요소 추가 후 queue : [1, 3, 3, 6] ---------- ---------- ---------- ---------- 6 방문 처리 후 visited : [1, 2, 3, 4, 5, 6] 큐에 연결된 요소 추가 후 queue : [5] ---------- ----------
0.007978439331054688
대략 0.007초가 걸렸다.
이 코드의 문제점은 그럼 뭘까?
어떤 요소를 방문처리해주고(visited.append(node))
그 요소와 연결된 요소들(graph[node])를 큐에 추가해줄 때, 방문한 적 없는 요소들만 추가해야 한다.
근데 위 코드는 일단 연결된 요소들 전부 큐에 추가해주고, 나중에 큐에서 꺼낼 때 꺼낸 값이 방문한 적이 있는지 없는지를 판단하기 때문에 쓸데없이 시간을 낭비하는 꼴이 된다.
그래서 다음과 같이 바꿔줄 수 있다.
def BFS(graph, start_node):
visited = []
queue = [start_node]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
print(node)
for nd in graph[node]: # 연결된 요소들에 대해 하나하나 따진다
if nd not in visited: # 방문한 적 없는 요소여야
queue.append(nd) # 큐에 추가
그러나 이 방법도 문제점이 있다. 큐에 원소들을 추가해주는 작업을 하는 부분을 보면 graph[node]에 해당하는 리스트의 원소들을 루프문으로 돌기 때문에, 시간낭비가 역시 생길 수 있다!
: 수학으로 치면 '집합'의 개념에 해당하는 자료형. set이란 키워드를 이용해 만들 수 있고, set()의 괄호 안에 리스트나 문자열을 넣어주어 만들 수 있다(ex : a = set([1, 2, 3], b = set("hello") → 참고로 집합 자료형은 중복을 허용하지 않고 때문에 b의 경우는 i가 2개가 아니라 1개만 있는 형태가 된다. 암튼 이를 통해 교집합/차집합/합집합을 구하는 듯한 연산을 할 수 있는데, 이를 통해 visited에 방문한 적 없는 친구들을 넣어주는 것이 가능!
예를 들어, a = set(1, 2, 3)이고 b = set(3, 4, 5)라 해보자. a와 b의 합집합 a|b = 1, 2, 3, 4, 5가 된다! 또한, 차집합 a - b = 1, 2가 된다. 이를 통해 graph[node]의 리스트 중에서 방문한 적 없는 요소들, 즉 visited리스트에 없는 요소들만 더하려면 queue에다가 set(graph[node]) - set(visited)를 더해주면 됨!
그래서 다음과 같이 해준다.
def BFS(graph, start_node):
visited = []
queue = [start_node]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
print(node)
queue += (set(graph[node]) - set(visited))
그러나 아직까지도 문제가 있다..ㅋㅋㅋㅋㅋㅋ
큐에서 제일 첫 번째 녀석을 빼주는 queue.pop(0)이 문젠데, 이 녀석의 시간복잡도가 O(n)이라는 것.
이는 collection 라이브러리에 있는 deque를 사용해 해결가능하다.
그리고 visited가 리스트로 되어있는데,
if in 또는 if not in방법은 리스트에서 하면 이 역시 시간복잡도가 O(n)이다.
따라서 visited를 딕셔너리 또는 집합(set)으로 해주는 게 더 빠르다!
그래서, 다음과 같이 해주자.
from collections import deque
def BFS(graph, start_node):
visited = {}
queue = deque([start_node])
while queue:
node = queue.popleft()
if node not in visited:
visited[node] = True
print(node)
queue += (set(graph[node]) - set(visited))
다 됐으면, pip freeze > requirements.txt를 하여 라이브러리 리스트를 만들어주고 이를 manage.py와 동일한 위치에 둔다! 그후 manage.py가 있는 곳에 runtime.txt를 만들고, 그 안에 python-x.x.x를 작성한다. 파이썬 버전을 적는 것인데, 이는 터미널에 python -version을 입력하는 것으로 확인가능하다.
이제 모든 준비가 끝났는데, 내 경우에는 가상환경과 관련된 폴더가 프로젝트 디렉토리와 같은 곳에 있었는데, 이 때 프로젝트 디렉토리 안으로 가상환경 폴더를 이동시켜야만 에러가 발생하지 않았다. 내 가상환경 이름이 venv고 프로젝트 디렉토리가 project1이었다면, project1디렉토리 안에 venv가 위치해야만 했다. 즉 manage.py와 venv가 같은 곳에 있어야 했음!
여까지 다 됐다면, 이제 깃허브에 새 레포지토리를 만들고, manage.py가 있는 위치에서 다음 작업들을 해준다.
git init
git add .
git commit -m "커밋메시지"
git remote add origin <레포지토리 url>
git push origin master
그리고 터미널에서 heroku login을 입력하면 헤로쿠 사이트가 뜨는데 로그인해준다. 그 후 터미널에 heroku create <서버이름>을 입력해서 배포서버를 만들어준다. 서버이름은 내 맘대로 정하는 것임. 이미 만든 서버가 존재한다면, heroku git:remote -a <서버이름>을 입력해주면 된다.
그 후 git push heroku master를 해준다. 푸쉬가 다 잘 됐다면, 터미널에
heroku run python manage.py migrate
heroku run python manage.py createsuperuser
heroku run python manage.py collectstatic
을 해준 다음, heroku open을 하면 된다. 끝!!
참고로 터미널에서 heroku run bash를 한 뒤, cd명령어 등을 이용해 작업할 수도 있다.
