Lucy의 개발 일지

수 많은 알고리즘 중 당연히 알고 있어야 하는 기본 알고리즘 중 하나가 DFS와 BFS이다. 오늘은 이 두 가지 알고리즘에 대해 정리를 해보려고 한다. 깊이우선"탐색" 과 너비우선"탐색"과 같이 이 알고리즘은 무언가를 탐색하는 것이다. 그렇다면 무엇을 탐색하는 것일까? 바로 그래프를 탐색하는 알고리즘이다. 그렇다면 그래프란 무엇일까? 그래프 (graph) 그래프는 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 예를 들어, 지하철 노선도는 많은 역들이 어떻게 연결되어 있는지를 알려주며, 소셜 네트워크 서비스의 인맥 지도는 사람들의 복잡한 친구 관계를 표현한다. 그래프는 선형 자료구조들이나 트리보다 더 일반화 된 자료구조를 제공하고 많은 분야에서 널리 사용되고 있다. 정점과 간선 그래프..

정보처리기사 공부를 하는 도중, 여러 가지 정렬 알고리즘에 대해 정리를 할 필요가 있어 이 글을 쓰게 되었다. 정렬 알고리즘은 컴퓨터 분야에서 중요시되는 문제 가운데 하나로 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제이다. 정렬 알고리즘 중 주요 알고리즘인 5가지에 대해 정리를 해보려고 한다. 1. 삽입 정렬 (Insertion Sort) 2. 선택 정렬 (Selection Sort) 3. 버블 정렬 (Bubble Sort) 4. 퀵 정렬 (Quick Sort) 5. 힙 정렬 (Heap Sort) 삽입 정렬(Insertion Sort) 삽입 정렬은 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬한다. N번째 키를 앞의 N-1개의 키와 ..

❓분할 정복 알고리즘 (Divide and Conquer) 란? 분할 정복(Divide and Conquer) 알고리즘은 여러 알고리즘의 기본이 되는 해결방법으로, 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬과 이진탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다. 🔑설계 분할 정복은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화 할 수 있다. 분할 (Divide) : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 정복 (Conquer) : 가장 적은 단위의 하위 문제를 해결하여 정복한다. 조합 (Combine) : 하위 문제에 대한 결과를 ..

❓이진 탐색 (또는 이분 탐색, Binary Search) 란? 정렬되어 있는 (이진 탐색의 주요 조건) 배열에서 데이터를 찾으려 시도할 때, 순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라 탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법이다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다. 👉동작 방식 이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾는다. 중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있다. 이진 탐색의 동작 방식은 다음과 같다. 1. 배열의 중간 값을 가져온다. 2. 중간 값과 검색 값을 비교한다. 1. 중간 ..

❓동적 계획법 (또는 다이나믹 프로그래밍 , DP)란? 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 👉DP를 쓰는 이유 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 피보나치 수열은 아래와 같다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141 ... 피보나치 수를 구하고 싶을 때 재귀로..

💡그리디(탐욕) 알고리즘 (Greedy Algorithm)이란? - Greedy는 '탐욕스러운, 욕심많은' 이란 뜻이다. - 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방식이다. - 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. - 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. - 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. - 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서..

DFS와 백트래킹 깊이 우선 탐색(DFS) DFS는 가능한 모든 경로(후보)를 탐색한다. 장점 : 무한히 깊은 곳을 찾아야할때 효과적이다. 단점 : 모든 곳을 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할수도 있다. =>따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다. DFS의 비효율적인 경로를 차단하고 목표지점에 갈 수 있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘 이다! 백트래킹(Backtracking) 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아 간다. 코딩에서는 반복문의 횟수를 줄일 수 있어 효율적이다. 불필요한 부분을 쳐내고 최대한 올바른..