과외 - 알고리즘/과제
-
문자열(String)과외 - 알고리즘/과제 2018. 9. 6. 18:42
NaiveMatchingContents두 개의 문자열이 입력으로 들어 온다. 두 번째로 들어오는 문자열이 패턴이고 첫 번째로 입력받은 문자열에서 해당 패턴을 찾는 것이 이번 문제이다. 패턴을 찾는 방법에는 여러 방법이 있지만, 그 중에서 가장 구현하기 쉬운 방법으로 이번 문제를 해결해보자. 알고리즘은 다음과 같다. naiveMatching(A, P){ //n is length of A, m is length of P. //P is pattern string. for i = 1 to n-m+1 if(P[1..m] = A[i..i+m-1]) ---- (1) then A[i] 자리에서 매칭이 발견되었음을 알린다.} 다른 알고리즘과 위 알고리즘을 구별하기 위해서 (1)에서 비교 횟수를 카운팅한다. * 비교회수에..
-
그래프(Graph)과외 - 알고리즘/과제 2018. 9. 6. 18:41
BFSContents이번 문제에서 그래프는 다음과 같이 구성된다. 1부터 n까지의 노드로 구성된다. 각 노드는 이어져있을 수도 있고 그렇지 않을 수도 있다. 간선의 방향은 없다.BFS로 방문 할 때 숫자 순으로 방문한다. 예를 들어서 1번 노드에 2번 노드와 3번 노드가 동시에 이어져 있을 경우, 1번 노드에서는 2번 노드를 먼저 방문한다. 그래프 G와 출발점 s가 주어졌을 때, s에서 출발하는 BFS를 하면서 방문하는 노드를 출력하라. Input입력의 첫줄은 n이 들어온다. 그 다음 줄에는 간선의 수 m이 들어온다. 다음 m 줄에는 간선(x, y)이 들어온다.마지막 줄에는 출발 노드 s가 들어 온다. Outputs에서 출발하여 BFS를 하면서 방문하는 노드를 출력한다. 각 노드는 빈칸으로 구별한다. S..
-
동적프로그래밍(DP)과외 - 알고리즘/과제 2018. 9. 6. 18:40
MatrixPathContents 소년 스티브 잡스는 주말 동안 밤새 열혈코딩을 하느라고 월요일 아침에 늦잠을 자고 말았다. 오전에 수업이 있는 스티브잡스는 빌게이츠와의 경쟁에서 이기기 위해서는 수업에 지각을 하면 안된다. 스티븐 잡스는 머리를 굴리기 위해 지도를 펼쳤다. 지도는 왼쪽 가장 위쪽의 좌표가 (1, 1)이고 오른쪽 가장 아래쪽의 좌표가 (4, 4)이다. 각 셀의 숫자는 택시가 움직이는데 드는 시간이다. 즉, (1, 1)에서 택시가 이동하는데 드는 시간은 6이다. 잡스는 (1, 1)의 위치에 있고, 학교는 (4, 4)에 있다. 즉, (1, 1)에서 (4, 4)로 이동해야 한다. 그런데 잡스가 사는 동네의 택시는 사람들의 안전을 위해서 다음과 같은 방식으로 움직인다. ㆍ오른쪽이나 아래쪽으로만 이..
-
해쉬(Hash)과외 - 알고리즘/과제 2018. 9. 6. 18:38
HASHContentsN개의 숫자들을 개방주소 방식을 사용하는 다음의 해시 함수 h_i(x)를 이용하여 크기 M인 해시테이블에 저장한다. h_i(x) = (x + i) % M 해시테이블의 크기 M은 2*N보다 크거나 같은 소수 (prime number) 중 가장 작은 숫자로 한다. 예를들어, N = 5인 경우 M = 11이 된다. 이때, 숫자 N개를 해시테이블에 저장할 때 충돌이 일어나는 총 횟수를 출력한다. Input입력의 첫줄에는 해시테이블에 넣을 숫자의 개수 N이 들어온다. 다음 줄에 N개의 숫자가 입력된다. Output해시 테이블에 숫자를 입력할 때 발생하는 전체 충돌 횟수를 출력한다. Sample Input10 1 2 3 4 5 5 6 7 8 9 Sample Output5