사소한 아이의 소소한 스킬/알고리즘

이번엔 DFS를 알아보도록하자. DFS란 한국말론 깊이우선 탐색(Depth First Search)이다. 깊이우선탐색은 무엇인가.. 무언가 탐색을 할때 동일한 레벨의 노드를 탐색을 먼저 하는것이 아니라 아랫레벨의 노드를 우선 탐색하는 시스템이다. 역시 말로는 이해가 안가니... 이미지로...... 사진과 같은 트리가 존재할때 깊이우선의 경우에 이렇게 순회하게된다.(우측, 좌측의 순서는 없음) A -> B -> H -> M -> J -> K -> L -> I -> C -> D -> G -> E -> F 대충 느낌이 팍 오죠? 그럼 어떤식으로 구현하면 될지 생각을 해보면... stack 구조를 이용해서 노드를 추가한 후 추가한 노드를 다시 탐색하고 추가한 노드를 다시 탐색하고 하면 깊이 우선이 가능!!!! ..

이번엔 BFS를 알아보도록하자. BFS란 한국말론 너비우선 탐색(Breadth First Search)이다. 너비우선탐색은 무엇인가.. 깊이와 반대다... 무언가 탐색을 할때 추가된 노드를 우선적으로 탐색하는것이 아니라 이미 추가되어있는 노드를 우선적으로 탐색하는 것.. 역시 말로는 이해가 안가니... 이미지로...... (DFS와 동일한 노드) 사진과 같은 트리가 존재할때 깊이우선의 경우에 이렇게 순회하게된다. (우측, 좌측의 순서는 없음) A -> B -> C -> H -> D -> I -> J -> M -> E -> G -> K -> F -> L 대충 느낌이 팍 오죠? 그럼 어떤식으로 구현하면 될지 생각을 해보면... DFS의 경우 추가된 노드를 우선적으로 순회했지만.. 이번에는 이미 추가되어있는 ..

재귀함수에 대해 알아보자. 재귀함수란 자기 자신을 다시 호출한다는 의미.... 자기자신을 다시 호출하는데 파라미터를 바꿔가면서 호출한다. 여기서 무한정 자기자신을 호출할 수 있기에 종료조건은 필수로 필요하다. 그리하여 반복계산할수있도록 하는 것.. 이렇게만 말하면 헷갈리니..예제 코드를.. def factorial(n: int) -> int: # 종료조건 if n int: if x > y: return x else: return y def max_array(array: int, len: int) -> int: if len == 1: return array[0] else: return max(array[len - 1], max_array(array, len - 1)) temp_array = [33, 44,..

개발을 하다보면 정말 많은 알고리즘을 만나게된다. 아니 알고리즘을 통해서 개발을 진행한다. 그것이 유명한것이든.. 아니면 개발중인 시스템에 맞춘 자체 알고리즘이든... 그리하여 여러가지 유명?중요?기초? 알고리즘들을 다뤄볼까 한다. 대충 추려보면... 재귀 알고리즘 최대값 또는 최소값 찾기 두 정수의 최대공약수(GCD)를 빠르게 구하기 팩토리얼 피보나치 합계 정렬 알고리즘 선택 정렬 버블 정렬 퀵 정렬 삽입 정렬 쉘 정렬 힙 정렬 병합 정렬 기수 정렬 탐색 알고리즘 순차 탐색 이진 탐색 레드 블랙 트리 탐색 해쉬 알고리즘 해쉬 테이블 그래프 알고리즘 그래프 순회 깊이 우선 검색 너비 우선 검색 문자열 검색 알고리즘 패턴 문자열 검색 일단 이정도..? 이 알고리즘들을 전부다 확인하고 C#으로 구현하는것을 ..