문제 www.acmicpc.net/problem/2644 풀이 BFS로 풀이했다. 거리(촌수)를 구해야 할 두 노드가 정해져 있기 때문에 시작 노드만 큐에 넣고 탐색을 했다. 코드 import sys, collections def bfs(start, end): q = collections.deque([]) q.append([start,0]) visited[start] = 1 while q: cur, cnt = q.popleft() if cur == end: print(cnt) return for adj in g[cur]: if not visited[adj]: visited[adj] = 1 q.append([adj,cnt+1]) print(-1) n = int(sys.stdin.readline().stri..
1. PM2란? PM2는 Node.js 애플리케이션을 관리해주는 패키지이다(Process Manager). 공식사이트: pm2.keymetrics.io/ 2. PM2 설치하기 npm install pm2 -g -g옵션은 패키지를 전역적으로 설치하겠다는 명령이다(global). 3. PM2 실행하기 pm2 start [--name ] pm2 start [--watch] /* e.g. pm2 start main.js --name "server" pm2 start main.js --watch */ pm2로 프로그램을 실행시킨다. --name옵션을 통해 해당 프로세스에 앱 이름을 지정하여 관리할 수 있다. 지정하지 않는다면 기본적인 파일명이 지정된다(main.js -> main). --watch옵션을 통해 소스..
동적 계획법 푸는 방법 (DP 풀이) 알고리즘 중 하나인 동적 계획법, 사실 알고리즘 자체보다는 순발력을 요하는 경우가 잦아 많은 연습이 필요한 알고리즘이다. 이러한 동적 계획법에 대해 소개하고 어떻게 풀이해야 하는지에 대한 글이 있어 소개하고자 한다. 결론은 많은 연습과 직관이지만, 풀이 단계를 체계적으로 나누고 실제로 적용해봄에 의의가 있다고 생각된다. (원문: www.geeksforgeeks.org/solve-dynamic-programming-problem/) 동적 계획법(DP, Dynamic Programming)은 다항식 시간의 특정 유형의 문제를 해결하는 기술이다. 동적 계획법은 지수 시간의 브루트 포스 방식보다 빠르며 정확하다. 동적 계획법을 풀기 위해선 선행 학습되어야 할 내용들이 있다...
문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 유사한 문제들은 많이 풀어보았다. 1, 2, 3을 만들 수 있는 경우의 수를 dp테이블에 베이스로 저장해둔다. 점화식은 다음과 같다. dp[n] = dp[n-1] + dp[n-2] + dp[n-3] (3
문제 www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 이전에 풀었던 오르막 수 문제의 쉬운 버전 문제다. dp[n][0] = 0으로 끝나는 n자리 이친수의 개수 dp[n][1] = 1로 끝나는 n자리 이친수의 개수 문제에 주어진 조건을 살펴보자. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 1번 조건에 의해 dp[1][0] = 0, dp[1][1] = 1이 성립..
