CS48 [알고리즘 이론] 5. 트리순회 트리순회 트리순회는 이진트리에 속하는 모든 노드를 한 번씩 방문하여 모드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다. 루트 : V, 왼쪽 서브 트리(트리 중 왼쪽 전체(루트 제외)) : L, 오른쪽 서브 트리(트리 중 오른쪽 전체(루트 제외)) : R 이진트리에서 각각의 서브 트리 역시 이진트리이다. 전체 트리 순회의 알고리즘을 서브 트리에도 똑같이 적용해 순회한다. -> 순환(재귀) 적용 1. 전위순회 (Preordfer Traversal) : VLR 루트(V) -> 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) 순서대로 방문하는 것이다. 2. 중위순회 (Inorder Traversal) : LVR 왼쪽 서브트리(L) -> 루트(V) -> 오른쪽 서브트리(R) 순서대로 방문하는 것이다... 2023. 5. 5. [알고리즘 이론] 4. DFS, BFS DFS (Depth-First Search) 루트 노드(다른 임의의 노드도 가능)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색한다. 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. -> 재귀 or 스택 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부르 반드시 검사해야 한다. 이를 검사하지 않으면 무한루프에 빠질 수 있다. EX) visit[node] = true; 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더이상 갈 수 업게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하.. 2023. 5. 5. [알고리즘 이론] 3. 그래프이론 그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 그래프를 구현하는 방식은 두 가지가 있다. 알고리즘 문제에서 서로 다른 개체가 연결되어 있다.고 하면, 가장 먼저 그래프 알고리즘을 떠올리기. 1. 연결 리스트를 이용한 인접 리스트 방식 간선의 개수(O(E)) 만큼 메모리가 필요로 하지만 인접 행렬에 비해서 O(V)의 시간복잡도를 가진다. -> E(Edge) : 그래프 안에 있는 모든 간선들의 집합 , V(Vertax) : 그래프 내에 있는 모든 노드들의 집합 2. 2차원 배열을 이용하는 인접 행렬 방식 메모리 공간을 많이(O(V^2)) 필요로 하는 대신 노드간 간선의 비용을 구하는 시간이 O(1)의 시간복잡도를 가진다. 트리란 그래프의 일종으로 노드(정보의 단위)와 노드 사이에 하.. 2023. 5. 5. [알고리즘 이론] 2. 구현 구현 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 자바나 C에서 int 자료형은 –2,147,483,648 ~ 2,147,483,647 (약 21억) 이어서 이보다 범위가 큰 long 자료형을 사용하는 것이 좋다. 예시 알고리즘은 간단하지만 코드가 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 알고리즘 문제 추천 피보나치 수 5 (브론즈 2) https://www.acmicpc.net/problem/10870 최대공약수와 최소공배수 (브론즈 1) https://www.acmicpc.net/problem/2609 소수 (브론즈 2) https://www.acmicpc.net/prob.. 2023. 5. 3. 이전 1 2 3 4 5 6 7 ··· 12 다음
