알고리즘
-
깊이 우선 탐색 (DFS, Depth First Search)알고리즘 2023. 10. 2. 20:23
- 그래프를 탐색할 때 쓰는 알고리즘 중 하나 - 어떤 노트부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않는다. - 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색한다. cf) 분기 : 2개 이상의 정점으로 쪼개지는 부분 cf) BFS는 level 별로 탐색한다. DFS 수도코드 DFS(u, adj) u.visited = 1 for v ∈ adj[u] if(v.visited ==0) DFS(v, adj) DFS 코드 구현 #include using namespace std; const int n=6; vector adj[n]; int visited[n]; void dfs(int u){ visited[u]=1; cout
-
맵과 방향백터알고리즘 2023. 10. 1. 21:44
Q. 문제에서 맵(Map)으로 그래프를 표현한 경우 - 맵(지도) 기반으로 문제를 풀어야 한다! (인접행렬 X, 인접리스트X) 1. 맵을 보고 "갈 수 있는 지점" 과 "갈 수 없는 지점"을 인식한다. - 갈 수 있는 지점 : 연결된 정점 - 갈 수 없는 지점 : 연결되지 않은 정점 1 1 1 1 1 1 1 0 0 2. 4가지 방향 탐색 (y, x 기반으로 하기) 시계방향으로 탐색 (상 → 우 → 하 → 좌) 3. 재귀적으로 한칸씩 이동 (인접리스트, 행렬과 마찬가지로) Q. 3 * 3 맵을 입력받는다. 이 맵은 1과 0으로 이루어져있고 {0, 0}은 무조건 1이다. {0, 0}부터 4방향을 기준으로 한칸씩 탐색해나가며 방문한 정점은 다시 방문하지 않으며 방문하는 좌표를 출력한다. (0은 갈 수 없는 지..
-
인접행렬과 인접리스트 탐색알고리즘 2023. 10. 1. 20:33
그래프를 표현하는 방법 2가지 (컴퓨터에게 정점-간선으로 연결된 그래프가 있다고 알려주는 것) - 인접행렬 : 2차원 배열을 기반으로 그래프 표현 - 인접리스트 : 연결리스트를 기반으로 그래프 표현 더보기 1. 0번부터 방문 안한 노드를 찾고 해당 노드부터 방문한다. 2. 연결된 노드를 이어서 방문한다. 3. 방문한 노드는 다시 방문하지 않는다. 인접행렬을 기반으로 탐색하기 - 2차원 배열 이용 //인접행렬 #include using namespace std; const int V=10; bool a[V][V], visited[V]; //0으로 초기화 void go(int from){ visited[from] =1; cout
-
Birthday Problem알고리즘 2023. 3. 6. 01:28
구두 설명으로 알고리즘을 단어로 설명하십시오. 코딩을 하기 전에 정확성을 보여주십시오. 귀납적 증명을 사용하십시오. 효율성을 보여주십시오. 점근적 표기법을 사용하고 그 이유를 설명하십시오. 설명을 위한 의사 코드를 구성합니다. 문제를 해결하기 위해 코드를 개발합니다. 결과를 보여주세요. 알고리즘 효율성 & 점근적 분석 - 시간 복잡도 : 알고리즘의 수행시간 ▶ 최선의 경우 분석 (빅-오메가) ▶ 최악의 경우 분석 (빅-오) ▶ 평균의 경우 분석 (빅-세타) 최악의 경우 > 평균의 경우 > 최선의 경우 순으로 최악의 경우 분석을 사용하여 비교를 많이함. - 공간 복잡도: 알고리즘이 수행되는 동안 사용하는 메모리 공간 귀납적 증명 - 가설 : 100명의 사람이 있다면 생일이 같은 한쌍이 적어도 1쌍 존재한다..