개발새발 로그

그리디 - 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘 - 최적해를 보장해주지 않는다. 그리디 알고리즘의 특징 - 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다. - 크루스칼 알고리즘과 다익스트라 알고리즘 등에 사용된다. - 직관적인 문제에 사용된다. 동전 반환 문제 - 거스름돈은 번거롭기 때문에 최대한 적은 갯수의 동전을 사용해서 거슬러 주고 싶다. -> 큰 단위의 동전부터 거스름돈을 만들면 된다. 코딩테스트 그리디 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들..

너비 우선 탐색(BFS) -그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 BFS의 특징 - Queue를 이용하여 구현할 수 있다. - 시작 지점에서 가까운 정점부터 탐색한다. - V가 정점의 수, E가 간선의 수 일 때 BFS의 시간복잡도는 O(V+E)이다. 깊이 우선 탐색(DFS) - 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘 DFS의 특징 - Stack을 이용하여 구현할 수 있다. - 시작 정점에서 깊은 것부터 찾는다. - V가 정점의 수, E가 간선의 수 일 때 DFS의 시간복잡도는 O(V+E)이다. 코딩테스트 DFS 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코..

선형 탐색 - 순서대로 하나씩 찾는 알고리즘 - O(n) 시간 복잡도가 걸린다. 이진 탐색 - 정렬되어 있는 요소들을 반씩 제외하며 찾는 알고리즘 - O(log n)만큼 시간복잡도가 걸린다. 이진 탐색의 특징 - 반드시 정렬이 되어있어야 사용할 수 있다. - 배열 혹은 이진트리를 이용하여 구현할 수 있다. - O(log n) 시간복잡도인 만큼 상당히 빠르다. 배열을 이용한 구현 방법 이진 탐색 트리를 이용한 구현 방법 - 배열을 이용한 방법은 중간에 요소를 추가하거나 삭제하는 경우에는 선형시간이 걸린다는 단점이 여전히 존재한다. - 이 단점을 해결하기 위해 이진 탐색 트리를 이용한다. 이진 탐색 트리 - 이진 탐색을 위한 이진트리로 왼쪽 서브트리는 루트보다 작은 값이 모여있고, 오른쪽 서브트리는 루트보다..

정렬 요소들을 일정한 순서대로 열거하는 알고리즘 정렬의 특징 - 정렬 기준은 사용자가 정할 수 있다. - 크게 비교식과 분산식 정렬로 나눌 수 있다. - 대부분의 언어가 빌트인으로 제공해준다. - 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재한다. 비교식 정렬 버블 정렬 - 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 - O(n^2) 시간복잡도를 가진다. 버블정렬 이 과정을 반복한다.(가장 큰 수가 뒤로간다.) function solution(arr){ let answer=arr; for(let i=0; i

구글이나 네이버 검색에서 자동완성을 하려면 어떻게 해야할까? 이런 경우에 사용하기에 적합한 자료 구조로 트라이(Trie) 가 있다. 트라이 - 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 구조 트라이의 특징 - 검색어 자동완성, 사전 찾기 등에 응용될 수 있다. - 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다. - L이 문자열의 길이일 때, 삽입은 O(L)만큼 걸린다. - 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 더 많은 저장공간을 사용한다. Trie 생성하기 Trie 구조 - 루트는 비어있다. - 각 간선은 추가될 문자를 키로 가진다. - 각 정점은 이전 정점의 값 + 간선의 키를 값으로가진다. - 해시테이블과 연결리스트를 이용하여 구현할 수 있다. 자..

우선순위 큐 - FIFO인 큐와 달리 우선순위가 높은 요소가 먼저 나가는 큐 - 이때 우선순위 큐는 자료구조가 아닌 개념이다. 우선순위 큐를 구현하는 방법은 다양하게 존재한다. 그 중 힙은 우선순위 큐를 구현하기에 가장 적합한 방법이다. 힙 - 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 정렬되는 특징이 있다. 우선순위 큐와 힙은 다른 것이다! -만약 배열을 매번 우선순위에 따라 정렬하면 그것도 우선순위 큐가 될 수 있다. 단지 힙보다 효율이 떨어질 뿐이다. 힙의 특징 - 우선순위가 높은 요소가 먼저나가는 특징을 가진다. - 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있다. - 아쉽게도 자바스크립트에서는 직접 구현해서 사용..

비선형 자료구조인 트리에 대해서 알아보자 트리 - 방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 구조를 가지고 있다. 트리의 특징 - 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다. - 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다. - 루트에서 특정 정점으로 가는 경로는 유일하다. -> 하나의 부모 정점을 가지기 때문에 생긴 특징 이진 트리 - 이진트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다. 이진트리 완전 이진트리 : 마지막 레벨을 제외하고 모두 채워져 있는 이진 트리 포화 이진 트리 : 완전히 채워져 있는 이진 트리 편향 트리 : 한 방향으로만 정점이 이어진 이진 트리 이진트리의 특징 - 정점이 N개인 이진트리는 최악의 경우 높이가 N이 될 ..

DOM - HTML 문서를 파싱하여 브라우저가 이해할 수 있는 자료구조 - HTML 문서의 계층적 구조와 정보를 표현 - 프로퍼티와 메서드를 제공하는 트리 자료구조 - 노드 객체들로 구성된 트리 자료구조를 DOM 노드 HTML 요소 : HTML 문서를 구성하는 개별적인 요소 노드 객체 : HTML 요소가 렌더링 엔진에 의해 파싱되어 DOM을 구성하는 요소로 변환된 것 HTML요소 노드 어트리뷰트 어트리뷰트 노드 텍스트 콘텐츠 텍스트 노드 트리 자료구조 HTML 요소간의 중첩관계에 의해 계층적인 부자관계 형성으로 이를 반영한 모든 노드 객체들은 트리 자료구조로 구성된다. 트리 자료구조는 부모노드와 자식노드로 구성되어 노드간의 계층적 구조를 표현하는 비선형 자료구조 루트노드 : 최상위 노드 리프노드 : 자식..