로코의 개발일지 로코의 개발일지

알고리즘/탐색

• 완전 탐색(Brute Force - with. 백준 일곱난쟁이)

  알고리즘/탐색 2023. 2. 19. 18:07

  알고리즘 문제를 해결하기 위해 가장 쉬운 방법 중 하나로 완전 탐색을 떠올릴 수 있다. 이 알고리즘은 간단하게 모든 경우의 수를 탐색하는 방법으로 구현하기 쉬운만큼 시간은 최대로 사용하게 된다. 완전 탐색으로 풀 수 있는 문제 중 백준의 일곱 난쟁이 문제의 코드를 예시로 들어보겠다. https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제를 간략하게 설명하자면 아홉 난쟁이의 키가 주어졌을 때 일곱 난쟁이의 키의 합이 100이 되는 경우를 찾아 각 난쟁이의 ..

  Read More
• 합집합 찾기(Union-Find)

  알고리즘/탐색 2021. 12. 25. 01:16

  서로소 집합 알고리즘 : 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별. (1) 자기 자신을 부모로 가진다. (2) A,B가 연결되어 있을 때 더 작은 값을 부모로 합친다 (Union) (3) A,B,C가 연결되어 있을 때 재귀함수를 이용해서 가장 작은 값인 A로 부모를 지정한다.(Union-Find) Find 알고리즘 : 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘. Union-Find는 최소 비용 신장 트리를 만들기 위한 알고리즘인 Kruskal 알고리즘에 주로 사용됨. //부모 노드를 찾는 함수 int getParent(int parent[], int x){ if(parent[x] == x) retu..

  Read More
• 이분 탐색(binary search)

  알고리즘/탐색 2021. 12. 25. 01:05

  이분 탐색 : 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 찾으려는 데이터와 중간 위치에 있는 데이터를 반복적으로 비교하여 원하는 결과를 도출해냄. 배열 내 데이터들이 정렬되어 있어야 사용할 수 있는 알고리즘이며, 입력 데이터가 많거나, 탐색 범위가 넓은 편. 시간복잡도: O(logN) 확인할 때마다 원소의 개수가 절반씩 줄어듦으로써 시간 복잡도는 logN에 비례하는 시간임. #include using namespace std; int binary_search(int arr[], int length, int target) { // 반복적 int start = 0; int end = length-1; int mid; while(start target) { end = mid-1; } else { ..

  Read More
• 깊이 우선 탐색(DFS)

  알고리즘/탐색 2021. 12. 25. 00:51

  깊이 우선 탐색(Depth First Search) : 탐색을 하는 데 있어 깊은 것을 우선적으로 하여 탐색하는 알고리즘. 스택이 사용되지만, 컴퓨터는 구조적으로 시스템 스택 프레임의 원리를 사용하기때문에 스택을 사용하지 않아도 재귀적으로 구현이 가능함. 시작 노드를 스택에 삽입하고, 방문 처리한다. 스택의 최상단 노드를 확인한다. 최상단 노드에서 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고, 방문처리 한다. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 뺀다. 2, 3의 과정은 스택이 비어질때까지 반복된다. #include #include using namespace std; int n = 7; int checked[7]; vector arr[8]; void dfs(int x) ..

  Read More
• 너비 우선 탐색(BFS)

  알고리즘/탐색 2021. 12. 25. 00:47

  너비 우선 탐색(Breadth First Search): 특정 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 알고리즘. 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용함. (ex. 미로찾기) 선입선출의 특성을 가진 큐를 이용하는데 큐는 너비 우선 탐색을 가능하도록 해준다. 시작 노드를 큐에 삽입하면서 방문처리. 큐에서 하나의 노드를 꺼낸다. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입. 2, 3번 과정을 반복하면 시작 노드에서 거리가 가까운 순서대로 출력이 될 것임. #include #include #include using namespace std; int n = 7; int checked[7]; vector arr[8]; void b..

  Read More