CS/자료 구조 및 알고리즘17 [알고리즘 이론] 7. 백트래킹 백트래킹 제약조건 만족 문제에서 해를 찾기 위한 전략 해를 찾기 위해 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 백트랙(이 후보군은 다시 체크하지 않을 것을 표시) 하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서, 각 루트에 대해 조건이 부합하는지 체크하고, 만약 해당 트리에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지를 쳐버리는 탐색. 알고리즘 문제 추천 N과 M(1 ~ 4) (실버 3) https://www.acmicpc.net/problem/15649 https://www.acmicpc.net/problem/15650 .. 2023. 5. 9. [알고리즘 이론] 6. 완전탐색 완전탐색 모든 경우의 수를 시도하여 정답을 찾는 방법이다. 무식하게 푼다는 의미로 Brute Force 라고도 한다. 상대적으로 간단하지만 경우의 수가 많아지면 시간이 길어지는 단점이 있다. 1. 단순 Brute-Force 특별한 기법 없이 for문과 if문으로 모든 경우의 수를 체크하여 답을 구함 이 방법으로 풀 수 있는 문제는 많지 않음 2. 비트마스크 각 원소를 두 가지 상태로 분류할 수 있을 때 사용 모든 경우의 수에서 각각의 원소가 포함되거나 포함되지 않는 경우 포함되면 1, 포함되지 않으면 0으로 구분한다 -> 2진수 EX) 원소 n개인 집합의 부분집합 구하기 자세한 건 아래 게시글 https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC.. 2023. 5. 9. [알고리즘 이론] 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. 이전 1 2 3 4 5 다음
