mo1lusca의 블로그

0. 주제 선정 동기동아리 시간에 배운 BFS와 DFS 같은 탐색 알고리즘을 활용해 뭘 만들 수 있을까 고민했다.미로찾기 시뮬레이터를 만들어 여러 알고리즘으로 미로를 해결해보면,탐색 알고리즘이 어떻게 실행되는지도 이해하기 좋을 것 같아서 해당 주제로 프로젝트를 진행하기로 했다.1. 개념 소개i . 미로 생성미로를 탐색하기 위해서는 일단 미로가 필요하다.사용자가 미로를 입력하는 방식은, 크고 복잡한 미로를 만들기에 부적합하기에 미로생성을 위한 알고리즘을 짜야 했다.미로생성에는 Prim, Kruskal 등 다양한 알고리즘을 사용할 수 있지만, 구현이 마냥 쉽진 않기도 하고 주객전도같은 느낌이 들어간단한 알고리즘을 통해 만들었다.ii. 미로 탐색위에서 만든 미로를 탐색한다.동아리 시간에 배운 DFS와 BFS,..

동아리 시간에 배운 트리 자료구조에 대해 작성하려 한다.트리의 구조와 명칭을 정리한 그림이다. 루트(Root): 부모가 없는 최상위 노드이다부모(Parent): 노드 A에서 노드 B로 가는 링크가 있을 때 A를 B의 부모라고 한다. 자식(Child): 노드 A에서 노드 B로 가는 링크가 있을 때 B를 A의 자식이라고 한다. 형제(Siblings): 같은 부모를 갖는 노드들이다.리프(Leaf): 자식이 없는 노드이다. 이진트리(Binary Tree): 자식을 두개까지만 가질 수 있는 트리이다.솔직히 트리는 탐색같이 다른 알고리즘 할때도 많이 접했어서개념자체는 크게 어렵지 않은 것 같다.

동아리 시간에 배운 탐색 알고리즘에 대해 작성하려 한다.이진 탐색은 탐색하려는 범위를 둘로 나누어서 탐색하는 방법이다.업다운게임이라고 생각하면 편하다. 어느 정렬된 배열이 있다고 했을 때, 일반적으로 어느 값을 찾기 위해for문과 같은 반복문을 사용하는 방법을 선택할 수 있다.이 경우에는 찾으려는 값이 나올때 까지 하나씩 탐색하기 때문에,시간복잡도가 O(n)이다.n이 몇억만 되어도 시간이 꽤 걸리기 때문에 백준에서 이런 탐색법은 쓰기 어렵다. 배열이 정렬되어 있다는 전제 하에, 이진 탐색 알고리즘을 사용하면시간복잡도를 O(log_2*n)으로 줄일 수 있다.약 43억개의 원소를 가진 배열도 32번 남짓의 연산으로 커버 가능하다. 비록 탐색하려는 배열이 정렬되어있어야 한다는 점이 약간 걸리지만굉장히 효율적인..