시험 시간은 40분이고 시험 사이에 10분 간의 준비 시간이 있습니다. 알고리즘만 대충 기출이 기억이 납니다 첫번째 시험에는 mergesort의 코드를 써야하는 것이 나왔고 두번째 시험에는 여러 알고리즘의 시간 복잡도를 쓰는 것이 나왔습니다 세번째 시험에는 BST관련해서 inorder search, preorder search, postorder search가 나왔습니다 간단한 문제였지만 세번째 시험은 공지된 교과서에는 없던 문제여서 당황했습니다 다행히 예전에 공부한 것을 바탕으로 쳤습니다 합격 하겠쪼 ??? ㅎㅎㅎㅎㅎ ㅠㅠㅠ 붙었습니다 ~ 다들 알고리즘 보세요 역대급 개꿀 냠냠 과목입니다

위상 정렬은 2022년도 1학기 서울대학교 석사 시험에 나왔던 문제이다. 노드 i와 j 사이에 간선 (i, j)가 존재한다면 노드 i는 노드j보다 먼저 수행되어야한다. 모든 간선에 대해서 이 성질만 만족시킨다면 노드 간의 어떤 순서라도 좋다. 이런 성질을 만족하는 정렬을 위상 정렬, topological sort이라고 한다. 간선 (i, j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야한다 만약 그래프에 사이클이 있다면 이 성질은 결코 만족될 수 없으므로 위상 정렬은 할 수 없다. 동작 방식은 아래와 같다. 알고리즘 1. topologicalSort(G, v){ for i

1. dfs와 bfs의 시간 복잡도 dfs와 bfs 모두 인접리스트, 인접 행렬로 구현할 수 있다. N이 그래프의 노드의 수, E가 그래프의 간선의 수라고 하자. dfs와 bfs 모두 인접리스트로 그래프를 구현했을 때 O(N+E)의 시간 복잡도를 가지며 인접행렬로 구현했을 때 O(N^2)의 시간 복잡도를 갖는다. 2. bfs 소스코드 C++ BFS(G, s){ for each v ( s visited[v] = NO; } visited[s] = YES; enqueue(Q, s) while (Q!=0){ u

평균 선형 시간 선택 알고리즘 n개의 원소로된 집합에서 최소 원소를 찾기 위해서는 O(n)의 사긴이 필요로한다. 그런데 n개의 원소 중 i번째 작은 원소를 찾기 위해서는 O(n^2) 의 시간이 든다. 정렬을 사용하면 O(nlogn)의 시간으로 단축할 수 있으므로 시간은 O(n)과 O(nlogn) 사이의 시간이 들 것이다. 알고리즘을 사용하면 O(n)의 시간에 확인할 수 있다고 한다. 퀵정렬 알고리즘을 개선하면 평균적으로 선형시간에 i번째 작은 원소를 찾을 수 있게 한다. 알고리즘을 살펴보자. 소스코드 select(A, p, r, i) { if (p=r) then return A[p]; q

앞서 설명한 정렬 알고리즘들의 공통점은 원소끼리 비교하는 것으로만 정렬을 한다는 것이다. 이런 정렬을 '비교정렬'이라고 한다. 이러한 비교정렬은 최악의 경우 수행 시간이 절대 O(nlogn)을 밑돌 수 없다. 정렬하고자 하는 원소들이 특수한 성질을 만족하면 이 하한보다 더 빠른 정렬 알고리즘을 적용할 수 있다. 기수정렬 기수 정렬은 입력이 모두 k자릿수 이하의 자연수인 특수한 경우에 사용할 수 있는 방법으로 O(n)시간이 소요되는 정렬 알고리즘이다. 기수정렬은 우선 가장 낮은 자릿수만 가지고 모든 수를 정렬한다. 그런 다음 가장 낮은 자릿수는 잊어버린다. 그리고 앞과 같은 방법으로 더 이상 자릿수가 남지 않을 때까지 반복한다. 이렇게 하면 마지막에는 정렬된 배열을 갖게된다. 계수정렬 계수 정렬은 정렬하고..