전체 글65 [알고리즘 이론] 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. [알고리즘 이론] 3. 그래프이론 그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 그래프를 구현하는 방식은 두 가지가 있다. 알고리즘 문제에서 서로 다른 개체가 연결되어 있다.고 하면, 가장 먼저 그래프 알고리즘을 떠올리기. 1. 연결 리스트를 이용한 인접 리스트 방식 간선의 개수(O(E)) 만큼 메모리가 필요로 하지만 인접 행렬에 비해서 O(V)의 시간복잡도를 가진다. -> E(Edge) : 그래프 안에 있는 모든 간선들의 집합 , V(Vertax) : 그래프 내에 있는 모든 노드들의 집합 2. 2차원 배열을 이용하는 인접 행렬 방식 메모리 공간을 많이(O(V^2)) 필요로 하는 대신 노드간 간선의 비용을 구하는 시간이 O(1)의 시간복잡도를 가진다. 트리란 그래프의 일종으로 노드(정보의 단위)와 노드 사이에 하.. 2023. 5. 5. 이전 1 2 3 4 5 6 7 8 ··· 17 다음
