책 읽다가 코딩하다 죽을래

📚 DP(동적계획법)란? 큰 문제를 작은 문제로 나누어 푸는 것인데 이때 하나의 문제는 한 번만 풀어야 합니다. 동적 계획법에 대해 설명하기 딱 좋은 예시가 있는데 그것은 피보나치수열입니다. 📚 피보나치 수열이란? 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. ❓ 그러면 피보나치수열의 몇 번째 항을 바로 알 수 있는 코드를 짜려면 어떻게 해야 할까요? 피보나치의 규칙을 살펴보면 된다. 첫 번째와 두 번째는 무조건 1이고 다음 항부터는 Fibo(n) = Fibo(n - 1) + Fibo(n - 2) 이 반복된다. 우리는 이것을 재귀 함수로 쉽게 구현할..

📚 BFS (Breadth-First Search) 란? 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서 넓이 우선 검색을 적용한다. DFS는 인접한 한 노드를 끝까지 탐색했다면 BFS는 인접한 모든 정점을 방문합니다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모드 노드들을 저장하고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 됩니다. 처음에 넣은 노드이므로 큐를 이용해서 BFS를 구현할 수 있다. 📋 BFS 전체 과정 BFS의 알고리즘 방식을 설명하면 다음과 같다. 1. 루트 노드를 큐에 넣는다 2. 현재 큐의 노드를 빼서 visited에 추가한다. 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않..

📚 DFS란(Depth First Search)? DFS는 자료의 검색 트리나 그래프를 탐색하는 방법 중 하나이다. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS는 이름에 나와있는 그대로 끝까지 탐색하는 거에 초점을 맞춥니다. 그래서 그래프의 최대 깊이만큼의 공간을 요구하며, 이는 공간을 적게 쓰는 것입니다. 그러나 최단 경로를 탐색하기는 쉽지 않다. 모든 경로를 탐색하는 것이 아니기 때문입니다. 📋 DFS 전체 과정 DFS의 알고리즘 방식을 설명하면 다음과 같다. 1. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다. 2. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다. 3. 만약 끝에 도달했다면 리턴한..

📚 병합 정렬이란? 병합 정렬은 정렬할 배열을 더 이상 쪼개질 수 없는 상태까지 나눈 다음 합치면서 정렬을 하는 방법이다. 📋 병합 정렬 전체 과정 병합 정렬은 2가지 과정을 거친다. 정렬할 배열을 나누고(merge sort) -> 합친다(merge) 📋 merge sort 병합 정렬은 더 이상 쪼개질 수 없는 상태 즉, 쪼개진 배열의 길이가 1이 될 때까지 나눈다. 왜냐하면 배열의 길이가 1이면 그 속에 무슨 숫자가 들어있는 정렬이 모두 완료된 상태이기 때문입니다. 시간복잡도를 계산해가면서 배우는 게 낫기 때문에 시간복잡도 관점에서 과정을 설명해드리겠습니다. 다음과 같은 배열을 정렬해봅시다. 처음 배열의 개수는 N 개라고 합시다. 그다음은 N인 배열을 반으로 나눕니다. 그러면 길이가 N/2개인 배열 2..

1. 버블 정렬 더보기 버블 정렬은 보시다시피 두 개씩 비교해서 정렬한다는 모양이 마치 거품과도 같다해서 버블 정렬이라고 부릅니다. 맨 왼쪽에서부터 두 가지 수를 비교해서 오른쪽 수가 적으면 서로 자리를 바꾸고 오른쪽 수가 크면 자리를 바꾸지 않는 것입니다. 저 빨간색 네모가 왼쪽에서 맨 오른쪽까지 도착하게 되면 한 번 순회했다고 부르는데 한 번 순회할 때마다 맨 오른쪽에 하나씩 정렬이 됩니다. 왜냐하면 제일 큰 수는 저 빨간색 네모에서 계속 자리를 바꿔 결국에는 맨 뒤로 향하기 때문입니다. 그래서 한 번 순회하면 ~~, 8 두 번 순회하면 ~~7, 8 여섯 번 순회하면 1, 2, 3, 6, 7, 8 이런 식으로 정렬이 됩니다. 이러한 동작을 코드로 구현하면 다음과 같습니다. input = [3, 6, ..

재귀 함수는 함수 안에 자기를 다시 호출하는 함수이다. 알고리즘 문제 중 어떤 패턴이 반복적으로 나오거나, 같은 문제를 여러 번 풀어야 하는 상황이 생길 때 쓰이는 방법이다. 재귀 함수를 만드는 방법은 간단하다. def infinity: print("재귀함수가 뭐냐면은...") infinity() 함수 안에 다시 자신의 함수를 호출하면 된다. 근데 위의 예시는 계속 자신의 함수를 무한정 호출하게 되므로 스택오버플로우 오류가 일어난다. def function(k): if k

이런 배열이 있고 나는 'mango'라는 단어가 이 배열에 있는지 탐색한다고 가정하자 배열에 어느 특정 값을 찾으려면 당연히 처음부터 끝까지 하나씩 하나씩 찾아봐야 한다. 마치 배열 요소 닫힌 박스라고 생각하고 거기서 망고가 들어있는 박스를 찾으려면 하나하나씩 일일이 다 열어봐야 한다. 우린 이렇게 처음부터 순차적으로 데이터를 찾아보는 것을 순차 탐색이라 부른다. 여기서 운이 좋게도 한 번에 그 박스를 찾으면 행복하겠지만 맨 마지막에 그 박스를 찾으면 나는 운이 더럽게도 없다며 생각할 것이다. 여기서 순차 탐색의 시간복잡도를 알 수 있다. 찾고자 하는 데이터가 배열의 맨 앞에 있다면 시간 복잡도는 O(1)이지만 맨 뒤에 있었다면 시간복잡도는 O(N)이 걸릴 것이다. 즉 배열의 크기가 클수록 더 많은 시간..

1. 시간복잡도 더보기 시간 복잡도는 입력값에 따라 문제를 해결하는데 걸리는 시간과의 상관관계를 말합니다. 똑같은 알고리즘에 입력값이 몇 배로 늘어남에 따라 문제를 해결하는 데 걸리는 시간은 몇 배만큼 늘어나는지 보는 것이다. 우리는 똑같은 입력값이라도 당연히 더 빠른 시간 안에 입력을 처리하는 알고리즘을 선호한다. 즉 걸리는 시간이 줄어들수록 시간 복잡도는 작아지며, 시간 복잡도가 작은 알고리즘이 좋은 알고리즘이다. 시간 복잡도에 대해서 설명하기 위해 똑같은 목적을 가진 두 개의 알고리즘을 살펴보겠다. 두 개의 알고리즘의 목표는 배열 안에 숫자 중 가장 큰 최댓값을 찾는 로직이다. array = [1,3,6,5,4,2] def findMaxValue(array): max_num = array[0] fo..