모여서 각자 코딩/2021 하계 모각코
-
[2021 하계 모각코] 6차시모여서 각자 코딩/2021 하계 모각코 2022. 3. 15. 01:08
깊이 우선 탐색 루트 노드에서 시작해서 해당노드의 자식노드를 먼저 탐색하는 방법이다. 한방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게되면 가장 가까운 갈림길로 돌아와서 이곳으로 부터 다른 방향으로 다시 탐색을 진행한다. 즉 넓게 탐색하기 전에 깊게 탐색하는 것이다. 모든 노드를 탐색하는 경우 사용하며 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다. 단순 검색 속도는 너비 우선 탐색이 더 빠르다. 구현 방법 스택을 사용하여 방문한 노드를 담고 최근 방문한 노드를 pop하여 해당 노드의 자식노드를 스택에 담는다. 이 과정을 반복하며 깊이 우선 탐색을 진행한다. 시간 복잡도 - DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함 * 인접 리스트..
-
[2021 하계 모각코] 5차시모여서 각자 코딩/2021 하계 모각코 2022. 3. 15. 01:07
너비 우선 탐색 알고리즘 그래프 탐색 시 탐색 방법 중 하나이다. 그래프 탐색은 하나의 정점에서 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것이다. 루트노드 또는 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법으로 탐색 시에 너비를 우선으로 하는 알고리즘이다. 즉 시작 노드에서 가까운 노드를 먼저 방문하고 멀리 떨어져있는 노드를 나중에 방문하는 순회 방법이다. 너비우선탐색은 최단 경로를 찾거나 임의의 경로를 찾고자 할 때 사용한다. 노드에 대한 방문 여부를 검사해야하기 때문에 큐 자료구조를 사용하여 방문한 노드들을 저장하고 꺼낼 수 있도록 한다. 큐는 선입선출로서 방문한 노드를 삽입하고 선출 노드의 인접노드를 삽입함으로써 사용한다. 재귀적으로 동작하지 않기 때문에 반복문을 사용하여..
-
[2021 하계 모각코] 4차시모여서 각자 코딩/2021 하계 모각코 2022. 3. 15. 01:06
정렬 알고리즘 1. 선택 정렬 오름차순 정렬일 경우 제일 작은 값을 골라 차례 차례 제일 작은 인덱스부터 집어넣는다. 즉 현재 인덱스에서 최대 인덱스까지 값들 중에 최소값을 선택하여 현재 인덱스에 집어넣고 인덱스를 증가시킨 후 이과정을 반복한다. 내림차순 정렬일 경우 제일 작은 값을 고르는 것이 아닌 제일 큰 값을 고르면 된다. 2. 버블 정렬 현재 인덱스의 배열 값과 다음 인덱스의 배열 값을 비교해 오름차순, 내림차순 조건에 따라 조건에 부합하면 교화하는 식의 정렬이다. 오름차순 일경우 현재 인덱스와 다음 인덱스의 두 값을 비교해 오른쪽 값이 더 작을경우 교환한다. 이렇게 하면 처음 한번 실행했을 때 마지막 인덱스에 제일 큰값이 오게 되고 다음 턴에서는 마지막 인덱스를 제외하고 교환하..
-
[2021 하계 모각코] 3차시모여서 각자 코딩/2021 하계 모각코 2022. 3. 15. 01:04
브루트포스 알고리즘 brute: 무식한, force: 힘 무식한 힘 완전 탐색 알고리즘으로 가능한 모든 경우의 수를 탐색하면서 조건에 맞는 결과만을 선택한다. 컴퓨터에게 계산을 맡김으로써 무조건 결과를 얻는 강력한 방법이다. 브루트 포스 문제를 해결하기 위해선 어떤 구조에서도 모든 자료 탐색이 가능해야하기 때문에 구조에 따라 방식이 나뉜다. 선형 구조의 경우 모두 탐색하기 위해서 가장 간단한 방식인 순차탐색이 가능하다. 비선형 구조의 경우 모두 탐색하기 위해선 깊이 우선 탐색과 너비 우선 탐색이 있다. 순차 탐색 순차탐색으로 문제를 해결하는 방법은 다음과 같다. 1. 주어진 문제를 선형 구조로 구조화한다. 2. 구조화된 자료를 구조에 맞는 방식으로 해를 구할 때까지 탐색한다. 3. 탐색된 해를 정리하..
-
[2021 하계 모각코] 2차시모여서 각자 코딩/2021 하계 모각코 2022. 3. 15. 01:03
그리디 알고리즘 그리디 알고리즘은 최적해를 구하는 상황에서 사용하는 알고리즘으로 여러 경우 중 하나를 선택할 때 그 상황에서 가장 좋다고 생각하는 것을 선택하는 알고리즘이다. 즉 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 것이다. 따라서 탐욕 알고리즘이라고도 한다. 최적화 문제에서 동적 프로그래밍 사용 시 지나치게 많은 일을 하기 때문에 착안된 알고리즘이다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다. 각 단계의 최적해를 선택하기 때문에 전체 최적해를 보장해주지 않는다. 대표적인 예제로 거스름돈, 활동 선택 문제, 분할 가능 배낭문제가 있다. ex> 거스름돈 : 주어진 금액에 대해 최소 개수의 동전으로 거스름돈을 거슬러 준다. 알고리즘 : ..
-
[2021 하계 모각코] 1차시모여서 각자 코딩/2021 하계 모각코 2022. 3. 15. 01:00
다이나믹 프로그래밍 한번에 하나의 문제만 풀도록 하는 알고리즘이다. 큰 문제를 작은 문제로 나누어 푸는 문제로서 분할 정복과 비슷하지만 큰문제를 단순히 작은 문제로 나누어 푸는 분할정복과 다르게 다이나믹 프로그래밍은 작은 부분 문제들이 중복으로 일어난다. 이런 부분 문제들이 중복으로 일어나는 다이나믹 프로그래밍 방식은 정답을 구한 반복되는 문제들을 어딘가에 메모해놓고 이 메모한 문제를 사용하여 반복되는 문제를 해결한다. 이를 Memoization이라고 한다. 대표적인 예로 피보나치 수열이 있다. 피보나치 수열은 재귀적으로 또는 반복문으로 해결할 수 있는데 F[n] = f(n-1) + f(n-2) 의 점화식을 가진다. 구하려는 n번째 수열을 수열의 n-1, n-2값을 사용하여 구하기 때문에 반복적으..