[재귀] 재귀란? (반복문 vs 재귀 누가더 성능이좋은가!)
·
과거의 이력/기본개념 (손필기)
. 재귀(Recursion) 란? : 재귀함수란 자기 자신을 계속 호출하는 함수를 뜻한다. - 자기 자신을 호출할 수 있기 때문에 반복 연산에 자주 사용된다. - 모든 재귀함수는 무한재귀가 발생하는것을 방지하기 위해 탈출 조건인 기본단계와 재귀단계로 나누어져 있다. - 함수가 호출될 때 스택 메모리(stack memory)를 사용하게 되는데, 함수의 스택 call이 반복적으로 이루어지므로 메모리를 많이 차지하며 반복문에 비해 성능이 좋지 않다. - 메모리가 부족한 상황까지 반복된다면 stack overflow가 발생하며 프로그램이 비정상 종료 된다. 재귀 vs 반복문 여기까지의 결론 재귀는 반복문보다 느리고 성능이 좋지 않다. 그럼 대체 재귀를 왜 사용하는걸까?... 재귀함수를 사용하는 이유 1. 재귀적..
[정렬] 선택정렬 자바스크립트로 로직 구현!
·
과거의 이력/기본개념 (손필기)
선택정렬을 javascript로 구현해봤다. 1. 선택정렬 로직 (js) function selectSort(arr) { for(let i=0; i 1, 2, 3, 4, 5
[알고리즘] 배열과 연결리스트의 차이? (Array vs Linked List)
·
과거의 이력/기본개념 (손필기)
배열과 연결리스트 자료구조 알아보기! 연결 리스트(Linked List) 란? 링크드 리스트 라고도 한다. 메모리를 동적으로 사용가능하다. 데이터 재구성이 용이하다. 대용량 데이터 처리에 적합한 자료구조이다. 노드(Node)로 구성되어 있으며 노드 두개의 셀이 있는데 첫번째 셀에는 실 데이터가 있으며 두번째 셀에는 다음 노드의 시작 메모리 주소를 뜻하는 링크가 들어있다. (자료의 주소값으로 연결된 구조) 마지막 노드의 두번째 셀에는 Null값을 가진다. (마지막 노드이기 때문에 다음 노드의 링크가 없기떄문!) 노드가 서로 이웃하지 않기 때문에 각 노드의 위치를 바로 검색할 수 없다.(첫 노드부터 순차탐색 해야함) 배열이란? 배열은 크기가 고정적이다. 연속적인 메모리공간이 필요하기 때문에 최대 데이터 개수..
[빅오표기법] 빅오표기법이란? (Big O notation)
·
과거의 이력/기본개념 (손필기)
. 개발자로써 알고리즘을 짜야하고, 누군가가 만들어놓은 알고리즘을 자주 사용한다. 과연 그 알고리즘은 빠른 알고리즘일까? 이것을 평가하기위한 지표가 빅오표기법(Big O notation) 이다. 1. 빅오표기법이란? 상단에서 언급했듯 빅오표기법은 알고리즘이 얼마나 빠른지를 나타내는 표기법이다. 실제로 대문자 O를 사용하기에 빅.오. 표기법이라고 한다.(정말로..!) 빅오표기법은 '초' 와같은 시간단위로 속도를 세는것이 아니라 연산 횟수를 비교하기 위한것이다. 따라서 연산양이 많아질때 알고리즘에 걸리는 시간이 어떤식으로 증가하는지 알 수 있다. 2. 예시 100개의 원소를 가진 리스트를 단순탐색과 이진탐색을 각각 수행한다고 해보자. 이진탐색은 7밀리초가 걸리고 단순탐색은 100밀리초가 걸린다. 해당 결과로..
[알고리즘] 이진탐색(binary search) 기본개념 + js코드
·
과거의 이력/기본개념 (손필기)
240,000 개의 값이 있을때 단순탐색은 최대 240,000번 추측해야하지만, 이진탐색은 최대 18번의 추측으로 정답을 찾아낼 수 있다. 크기가 커질수록 단순탐색과는 비교도 안될정도의 빠른속도로 정답을 찾아낼 수 있다. 단, 이진탐색은 원소들이 정렬되어 있어야만 사용할 수 있다. javascript로 구현한 이진탐색 function binarySearch (target, dataArray) { let low = 0; let high = dataArray.length - 1; while (low target) { // 추측값이 정답보다 클 경우 high = mid - 1; } else { // 추측값이 정답보다 작을 경우 low = mid + 1; } } return undefined; } 단순탐색과 이..