728x90 반응형 알고리즘5 [알고리즘/Python] 재귀함수와 팩토리얼 재귀적으로 문제를 푼다는것 = 같은 형태의 더 작은 문제를 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 것. 재귀함수의 예시로 팩토리얼을 한번 보자. 팩토리얼 n의 팩토리얼은 n!이라고 표시한다. 이는 1부터 n까지의 정수를 곱하는 단순한 연산을 말한다. 재귀로 풀땐 항상 경우를 나눠줘야하는데 기본적인 base case와 조건이 다른 recursive case가 있다. 0!=1이라고했으니 n =0인 경우는 무조건 n!=1이 된다. 이렇게 바로 답이 나오는 경우를 base case라고 한다. 하지만 n != 0 인경우, n >0인 경우엔 재귀적으로 문제를 풀어야한다. 즉, 같은 형태의 더 작은 문제를 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 것이다. 위에 그림처럼 5!은 1x2x3x4x5 =.. 2023. 2. 23. [알고리즘/Python] BFS(너비우선탐색) BFS (너비우선탐색) Breath-First Search, 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘이다. 너비 우선 탐색이라고도 한다. 데이터가 N개 있을때 O(N)시간 복잡도를 가진다. 일반적인 경우 실제 수행시간은 DFS보다 좋은편이다. [DFS vs BFS] 동작 방식 동작 원리 구현 인접한 노드가 여러개라면? DFS 멀리 있는(깊게 있는)노드 부터 탐색 스택 재귀 함수 이용 한개씩 넣음 BFS 가까운 노드부터 탐색 큐 큐 자료구조 이용 한번에 다 넣음 BFS 동작과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다, 3. 2번과정을 더이상 수행할 수 없을 때까지 반.. 2023. 1. 18. [알고리즘/Python] 깊이우선탐색 (DFS) 그래프 탐색 알고리즘 : 시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 찾는 알고리즘 깊이우선탐색 (Depth-First Search, DFS) 그래프의 깊이를 우선으로 탐색하기 위해 스택의 개념을 활용한다. 너비우선탐색 (Breadth-First Search, BFS) 그래프의 너비를 우선으로 탐색하기 위해 큐의 개념을 활용한다. 깊이우선탐색(Depth-First Search, DFS) 시작 정점으로부터 갈 수 있는 하위 정점까지 가장 깊게 탐색하고, 더 이상 갈 곳이 없다면 마지막 갈림길로 돌아와서 다른 정점을 탐색하며 결국 모든 정점을 방문하는 순회 방법 깊이우선탐색(DFS)의 특징 모든 정점을 방문할 때 유리하다. 따라서 경우의 수, 순열과 조합 문제에서 많이 사용 한다. 너비우선탐색(B.. 2023. 1. 18. [알고리즘/Python] 에라토스테네스의 체 에라토스테네스의 체 -> 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘. -> N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 소수란? 1과 자신 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 말한다. > 동작 과정 2부터 N까지의 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.) 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다. > 장단점 에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다. 그래서 다수의 소수를 찾아야 하는 문제에서 자주 사용된다. 하지만 알고리즘을 수행할 때 N의 .. 2023. 1. 18. 내가 보려고 올리는 코딩 테스트 4단계 공부법(feat.원티드) 1단계: 자료구조 및 알고리즘 개념 공부하기 코딩 테스트에 제대로 대비하기 위해서는 연습 문제를 풀기에 앞서 이론을 탄탄히 다지는 단계가 필요합니다. 이론을 공부하지 않고 닥치는 대로 연습 문제만 푸는 것은 부실한 토지에 건물을 올리는 것과 같습니다. 건물을 높게 쌓을수록 토지의 부실함이 드러나 모든 게 무너지겠죠. 반면에 이론이라는 토지를 탄탄히 다져놓으면 그 위에 어떤 높은 건물을 쌓아도 든든히 버텨줄 것입니다. 코딩 테스트에서는 보통 단시간 안에 풀 수 있는 알고리즘 문제가 출제되는데요, 이런 유형의 문제를 풀기 위해서는 기본 자료구조 및 자주 사용되는 알고리즘 개념을 알아두어야 합니다. 수많은 자료구조와 알고리즘 개념 중 반드시 공부해야 하는 주제 몇 가지를 선정해 보았습니다. 자료구조 배열 (A.. 2023. 1. 4. 이전 1 다음 728x90 반응형
