https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 풀이 생각보다 오래걸린 문제이다. 단순히 DFS와 BFS만 구현할 것이 아니라, 방문할 수 있..

BFS 너비우선 탐색 너비 우선 탐색(Breadth-first search, BFS)은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 정점들과 같은 레벨에 있는 노드들(형제 노드)을 먼저 탐색하는 방식 시간복잡도: O(V + E) 구현을 하기 위해서는 두가지 큐가 필요하다 방문한 노드를 순서대로 기입한 큐 (A) 방문이 필요한 노드들의 정보가 가지고 있는 큐 (B) 첫 노드를 B에 넣고 시작한다. B에서 꺼낸 노드가 A에 없으면 B에서 꺼낸 후에 방문을 하고 A에 넣는다. 그리고 해당 노드와 연결된 노드를 B에 넣는다. 만약 B에 있는 노드가 이미 방문한 노드이..

개발환경 pycharm Professional https://www.jetbrains.com/ko-kr/pycharm/download/#section=windows 다운로드 PyCharm: JetBrains가 만든 전문 개발자용 Python IDE www.jetbrains.com 브라우저의 역할 서버에게 URL로 요청하고 서버한테 결과물을 결과물을 받아서 그려주는 것이 브라우저의 역할이다. HTML을 받아오는 경우 데이터만 받아오는 경우 HTML HTML은 문서 형태를 기반으로 한 뼈대이다. 여러 태그들로 이루어져 있다. 크게 head와 body로 이루어져 있다. head : 페이지의 속성정보 body : 페이지의 내용. body 안에 들어가는 대표적인 요소들 div : 구역을 나누는 역할. 줄 바꿈이 ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다. fibonacci(0)은 0을 출력하고, 0을 리턴한다. fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을..

async/await 패턴은 es8에서 도입되었는데 es6에서 표준화된 Promise 패턴으로도 불편함이 있었고 이 불편함을 해소하기 위해서 async/await 패턴이 도입되었다. 따라서 반드시 Promise 패턴을 알고 있어야 한다. async/await에서 사용되는 몇가지 규칙이 있다. await 는 반드시 async와 같이 사용되어야 한다. await 뒤에는 반드시 Promise 객체가 와야 한다. await는 Promise 객체의 비동기 작업이 끝날때까지 동기방식처럼 blocking 되어서 기다렸다가 작업이 끝나면 그 결과를 리턴한다. async를 앞에 붙인 함수는 resolved 된 Promise를 리턴하므로 만일 결과를 받아서 사용할려면 .then()으로 결과를 받아서 처리할 수 있다. as..

setTimeout 만약 아래 코드를 실행하면 결과가 어떻게 될까? A-B-C 순으로 출력이 될까 아니면 A-C-B순으로 출력이 될까? console.log("A"); setTimeout(function () { console.log("B"); }, 0); console.log("C"); 만약 자바스크립트가 멀티쓰레드라면 실행할 때마다 A-B-C로 출력되거나 A-C-B로 다르게 출력이 될 것이다. 메인쓰레드 외에 setTimeout이라는 부분을 별도의 쓰레드가 담당하게 되어서 두개의 쓰레드가 경합하면 메인쓰레드가 C를 출력할지 B를 출력할지 CPU가 다르게 할당할 것이기 때문이다. 그러나, 자바스크립트는 싱글쓰레드 언어이다. 따라서 setTimeout 부분을 별도의 쓰레드로 할당하지 않고 나중에 실행하기..