zo_zni's Blog

재귀 (Recursion) 재귀란 자신을 정의할 때, 자기 자신을 다시 호출하는 것입니다. 정의는 매우 단순하지만, 추후 그래프 탐색, 트리 , dp 등 주요 자료구조와 알고리즘과 연결되기 때문에 매우 중요한 개념입니다. 재귀에 대한 대표적인 예시는 factorial과 fibonacci가 있습니다. 자기 자신을 재참조한다는 것이 어떤 의미인지 코드를 통해 확인해 보도록 합시다. 재귀의 example 팩토리얼(factorial) def factorial(n): if n == 1: return 1 return n * factorial(n - 1) 함수 factorial 의 반환에 factorial 를 재참조하는 것을 확인할 수 있습니다. 피보나치(fibonacci) def fibo(n): if n == 1 ..

DTA(Direct-address Table) Direct-address Table(직접 주소화 테이블)이란, key값이 $k$인 데이터를 index $k$ 위치에 저장하는 방식입니다. key: 출석번호, value: 이름 (3, 노정호) (5, 배준석) (6, 정재헌) (7, 남영욱) 직접 주소화 방법을 통해 key-value 쌍의 데이터를 저장하고자 하면 많은 문제가 발생합니다. 문제점 1) 불필요한 공간 낭비 key: 학번, value: 이름 (2022390, 노정호) (2022392, 배준석) (2022393, 정재헌) (2022401, 남영욱) 문제점 2) Key값으로 문자열이 올 수 없다. key: ID, value: 이름 (nossi8128, 노정호) (js9876, 배준석) (zebra00..

큐(Queue) 💡 Queue queue는 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조입니다. queue의 rear(뒤)에 데이터를 추가하는 것을 enqueue라고 합니다. 또한 queue의 front(앞)에서 데이터를 꺼내는 것을 dequeue라고 합니다. FIFO (First In First Out) List 기반 queue 구현 python에서 queue를 가장 간단히 구현하는 방법은 단순하게 list를 이용하는 것입니다. list의 append 메서드를 사용하면 맨 뒤에 데이터가 추가 되고, pop을 하게 되면, 맨 앞의 데이터가 나오기 때문입니다. 여기서 주목해야 할 점은 list로 queue를 구현하면 dequeu..

리스트 (List) 리스트는 순서를 가지고 원소들을 저장하는 자료구조로, mutable, iterable, sequence 객체입니다. Array List와 Linked List 2가지 방식으로 구현이 가능한데, python에서 사용하는 리스트는 Array List로 구현되었습니다. 동적 배열 dynamic array 배열(array)은 정적 배열(static array)과 동적 배열(dynamic array)로 구분됩니다. 선언 이후에 크기를 변경할 수 없는 정적배열과 다르게 동적배열은 크기를 늘릴 수 있습니다. 파이썬의 리스트는 내부적으로 동적배열(dynamic array)로 구현되어 있습니다. List 사용법 - 기본 선언할 때에 배열의 크기를 정하지 않아도 되는 장점 덕분에 코딩테스트에서 동적 배..

💡 "다이나믹 프로그래밍(Dynamic Programming)"은 큰 문제를 작은 문제들로 나누어 해결한 후, 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법을 의미합니다. 다이나믹 프로그래밍을 사용하는 알고리즘의 주요 특징은 다음과 같습니다: 중복 계산 감소: 이미 계산한 결과를 저장하고, 필요할 때마다 재활용하여 중복된 계산을 피합니다. 점화식: 주어진 문제의 해를 작은 문제의 해를 통해 표현하는 식을 정의합니다. 이를 점화식이라고 부릅니다. 최적 부분 구조: 큰 문제의 최적해가 작은 문제들의 최적해를 통해 구할 수 있어야 합니다. 모든 해결책을 다 탐색해보는 ‘완전 탐색’은 기본적으로 높은 시간 복잡도를 가집니다. 이를 ‘체계적’이고 ‘효율적으로 탐색하기 위해서는 몇 가지 조건이 있어야 합니다...

💡 "분할정복"은 문제를 해결하기 위해 문제를 작은 부분 문제로 분할하고, 각 부분 문제를 독립적으로 해결한 후, 그 결과를 조합하여 전체 문제의 해를 얻는 방법입니다. 분할정복의 주요 특성은 다음과 같습니다. 분할(Divide): 주어진 문제를 더 작은 부분 문제로 분할합니다. 이때, 부분 문제들은 원래 문제와 동일한 유형이지만 크기가 작아야 합니다. 정복(Conquer): 각 부분 문제를 재귀적으로 해결합니다. 부분 문제가 충분히 작으면, 재귀를 멈추고 직접적으로 해결합니다. 통합(Combine): 부분 문제들의 해를 조합하여 전체 문제의 해를 얻습니다. 분할 정복은 주로 재귀적인 방식으로 구현되며, 문제를 더 작은 부분 문제로 나누어 해결하고 이를 결합하여 최종 해를 얻습니다. 분할정복의 과정을 의..

💡 "탐욕법"은 문제를 해결하기 위해 현 상태에서 가장 이득이 되는 선택을 하는 알고리즘 패러다임 입니다. 탐욕법의 주요 특징은 다음과 같습니다. 탐욕적 선택 속: 현재 단계에서의 선택이 이후에 영향을 미치더라도 현재 단계에서 최적인 선택을 합니다. 최적 부분 구조: 각 단계에서의 선택이 전체 문제에 대한 최적해의 부분해이어야 합니다. 하지만 항상 최적해를 보장하지는 않음: 탐욕적으로 선택하는 것이 항상 최적해를 보장하지는 않을 수 있습니다. 탐욕법의 3번 특징때문에 코딩테스트에서 이를 사용할때는 탐욕법의 해가 과연 코딩테스트 문제에서 원하는 해답일지 고민해봐야합니다. 위의 구조에서 가장 큰 수를 구하라 하였을 때 실제로 구해야하는 큰 수는 27이지만 탐욕법으로 접근하게 되면 20이 가장 큰 수로 구해지..

💡 "백트래킹"은 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 백트래킹은 일반적으로 완전탐색과의 유사성을 가지고 있습니다. 둘 다 모든 해를 찾아 나가려고 하는것은 같지만 백트래킹의 경우 해를 구해나가는 과정 중 더 진행해도 해가 될 것 같지 않다면 중단시키고 되돌아가는것이 특징입니다. 문제의 모든 가능성은 하나의 트리 형태로 표현할 수 있으며 부모 노드에서 자식 노드로 이동하는 것을 모든 가능성중 특정 가능성으로 결정하는 것으로 보아 이 트리를 의사 결정 트리라고 부릅니다. 즉 백트래킹은 의사 결정 트리를 순회하며 답을 찾는 방법으로 이해할 수 있습니다. 이 중단시키고 되돌아가는 것을 백트래킹에서는 가지치기 라고 부릅니다. 이 가지치기를 얼마나 잘 하느냐에 따..

💡 "완전탐색"은 문제의 해를 찾기 위하여 가능한 모든 해를 찾아내어 그 중 주어진 조건을 만족하는 최적해를 찾는 패러다임 입니다. 완전탐색은 알고리즘 패러다임중 하나로 가능한 모든 해를 찾아내어 그 중 조건을 만족하는 최적해를 찾아내는 방법입니다. 완전탐색은 모든 가능성을 확인하기때문에 가장 정확하고 최적의 해를 구할 수 있지만, 시간복잡도가 매우 높아질 수 있습니다. 모든 문제에 대해 완전탐색을 적용시키면 항상 답은 구해지겠지만 코딩테스트가 제한하는 시간안에 문제를 해결하지 못할 가능성이 큽니다. 그렇기에 완전탐색을 사용해야 할 시점은 다음과 같습니다. 주어진 입력의 범위가 작아 가능한 모든 해를 찾는 시간이 적게 들 때즉, 시간복잡도를 계산하고 될거같다 싶으면 일일이 다 하면 됩니다. 반복문이 몇개..

💡 "알고리즘 패러다임"은 문제를 해결하는 데 사용되는 기본적인 철학이나 방법론을 말합니다. 코딩 테스트에서는 주어지는 문제들을 한정된 시간 안에 정해진 형태의 입력을 가지고 답을 구해야 합니다. 그러기 위해서 저희는 각 문제별 풀이 과정을 발견해야하는데, 이런 풀이 과정들은 저희가 배웠던 자료구조와 알고리즘을 기반으로 만들어집니다. https://en.wikipedia.org/wiki/Algorithmic_paradigm 알고리즘 패러다임에는 여러가지 종류가 있지만, 코딩 테스트에서 자주 사용되는 종류만 추려서 앞으로 교재에서 다룰 주요한 알고리즘 패러다임을 다음과 같이 정리했습니다. 알고리즘 패러다임 완전탐색 백트래킹 탐욕법 분할정복 동적 계획법 📍 알고리즘이란 어떠한 문제를 해결하기 위해 정해진 일..