DP 란? DP는 특정한 알고리즘이라기보다 문제해결 패러다임으로 볼 수 있다. 큰 문제를 잘게 나눠서 결과를 저장해가며 그 답을 저장해두고 재활용한다. DP는 사실… 이론적으로는 별거 없다. 결국 풀이 경험이 중요하다…! 왜 쓸까? 피보나치 수열로 배워보자 일반적인 재귀를 사용할 때, 하나의 큰 문제를 풀기 위해 작은 문제들을 여러번 반복하기 때문에 비효율적일 때가 많다. 아래는 재귀호출 버전 피보나치의 호출 과정인데, 반복되는 호출이 꽤 많다. O(2^n)으로, n이 커질수록 기하급수적으로 커진다. def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2) Top Down 방식 : 위의 항부터 큰 항부터 쪼개서 작은 문제로 나..
해시 테이블이란? 여러가지 물건들이 있는데, 이걸 일렬로 세워놓지 말고 바구니 몇개 만들어서 바구니 A, 바구니 B, …에 넣어두자는거다. key, value 쌍으로 자료를 저장하는 자료구조중 하나. key → 해시값 → index 해시 함수를 사용하여 key를 해시값으로 매핑하고, 이 해시값을 index 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하고 검색하는 자료구조. 해시 함수(hash function)란, 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)이라고 한다. 시간 복잡도 O(1) ~ O..
B-tree란? 이진트리를 확장한 자료구조로, 탐색 성능을 높이기 위해 평소에 데이터들의 높이를 균형있게 유지하는 Balanced Tree의 일종이다. 노드에는 2개 이상의 데이터(key)가 들어갈 수 있다. 하나의 노드가 가질 수 있는 자식의 최대 숫자가 2보다 크다. 모든 단말(leaf) 노드는 같은 레벨에 있어야 한다. 항상 균형을 유지한다 (균형 잡힌 트리). 최대 M개의 자식을 가질 수 있는 B 트리를 M차(M-way) B트리라고 한다. 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다. (e.g. 3차 B트리 : 1~3개의 자식 노드 가능) 노드 내에 **데이터(key)**는 floor(M/2)-1개부터 최대 M-1개까지 포함될 수 있다 특정 노드의 데이터(key)가 K개라면, 자식 노드의 ..
선형 자료구조 Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way. 스택, 큐, 데크는 모두 추상 자료형(ADT)이다. 즉, 언어에서 기본적으로 제공되는게 아니라 데이터와 연산들에 의해 정의되는 추상적인 자료구조이다. 각각을 구현하는건 프로그래머의 몫이다. 스택, 큐, 데크 모두 선형 자료 구조이며 각자 특정 방향으로 **삽입(push), 삭제(pop)**가 된다는 특징을 갖고 있다. 그리고 n개의 원소들로 이뤄진 선형 리스트이다. 그렇기 때문에 보통 is_empty() ..
배열이란? 배열은 연속적인(인접한) 메모리 공간에 저장된, 같은 타입의 데이터들의 모임이다. 가장 기초적인 자료구조. 배열의 연산들 접근 연산 : 항상 O(1) 배열의 접근 연산은 index를 이용하고 이는 random access로, 빠른 속도를 보여준다. 탐색 연산(선형 탐색이라고 가정할 때 배열의 길이에 비례한다. O(n) ) # 선형 탐색 def lenear_search(arr, n, key): for i in range(n): # found if (arr[i] == key): return i # If the key is not found return -1 삽입 연산 : 맨 끝자리에 대한 삽입은 해당 자리를 찾아서 넣기만 하면 끝이다. 즉 접근 연산과 할당 연산 두개이기 때문에 O(1) 이다. 그..
알고리즘을 평가하는 두 가지 주요 기준은 시간과 공간이다. 이 두 요소는 서로 상충하는 경우가 많다. 메모리를 아끼려면 속도를 희생하고, 속도를 높이려면 메모리를 희생하는 식. 통상 더 중요시되는 기준은 시간이다. 프로그래밍 대회를 나가거나 알고리즘을 발명할게 아니라면 대부분 코딩 테스트를 보는 입장에서, 시간 제한을 지키는 것이 문제를 해결하는 것 다음으로 중요한 태스크다.시간 복잡도란?시간 복잡도(time complexity)란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다. 알고리즘의 속도를 비교하는 가장 직관적인 방법은 실제 실행시간 측정이다. 그러나, 이는 알고리즘의 속도를 일반적으로 논하는 ..
파인만 알고리즘. 칠판에 문제를 적는다. 골똘히 생각한다. 칠판에 답안을 적는다. 구종만 선생님께서 제시하신 문제해결과정. 문제를 읽고 이해하기백준 알고리즘을 풀면서 정말 많이 느낀 점이다. 입력과 출력 예시가 부족하다고 할 수도 있겠지만, 애초에 ‘문제’를 꼼꼼히 읽었다면 문제를 오해하는 일은 일어나지 않을 것이다.변수의 값, 시간 등 제약조건을 이해하기 위해선 알고리즘 시간복잡도, 공간복잡도 분석과 언어의 값 범위에 대한 이해가 선행되어야 한다.문제에서 나오는 개념이나, 지문에서 묻는 전반적인 요구조건과 제약조건을 일단 이해하자. 문제의 재정의와 추상화…자신이 다루기 쉬운 개념을 이용해서, 문제를 자신의 언어로 풀어 쓰는 것입니다. 이 과정은 문제가 요구하는 바를 직관적으로 이해하기 위해 꼭 필요합니..
추상 자료형? 학교에서 자료구조 & 알고리즘 수업을 들으면서 추상 자료형(Abstract Data Type, ADT)이라는 개념을 알게 됐다. 언어에서 제공하는 원시 타입(primary type)들로는 해결이 어려운 문제들이 있다. 그럴 땐 기존의 원시 데이터 타입을 응용해서 새로운 자료 구조를 만들어야 하는데, 자료 구조를 만드는 방법은 상황마다, 언어마다 다양하다. 추상 자료형은 어떤 자료형을 값과 연산들의 집합으로 정의한 것이다. 구체적인 언어나 명령어가 아닌 한 단계 추상적으로 구현 방법을 설명한다. 구현에 의존하지 않는다. 즉, 추상 자료형은 how(구체적인 구현 방법)가 아닌 what(집합과 연산들의 목록)을 추상적으로 명시해놓은 것이다. 음식 레시피와 같다. 내가 어떤 환경(어떤 프라이팬을 ..
