개인공부/패스트캠퍼스 알고리즘18 [Algorithm] 탐욕 알고리즘 # 탐욕 알고리즘(greedy algorithm) -현재 상황에서 당장 가장 좋아 보이는 상황만을 선택하는 알고리즘이다. - 그리드알고리즘, 탐욕법이라고 불리기도 한다. -최적의 해를 구하기 위한 근사적인 방법으로 사용될 때가 많다. # 탐욕 알고리즘의 접근 방법 1. 방법 고안하기: 현재 상황에서 어떤 것을 선택할지 알고리즘을 고안한다. 2. 정당성 확인하기: 자신이 고안한 알고리즘이 항상 최적의 해를 보장하는지 확인한다.(증명 단계) # 거스름돈문제 -거스름돈 문제는 전형적인 탐욕 알고리즘의 예시다. -카운터에 500원, 100원, 50원, 10운짜리 동전이 무수히 많이 존재한다. -손님에게 6480원을 거슬러 주어야할때, 동전 개수의 최솟값은? # 거스름돈 문제의 해법 -가장 큰 화폐 단위부터 거슬.. 2023. 9. 3. [알고리즘] 2-5. 트리와 우선순위 큐 # 트리(Tree) - 트리는 가계도와 같이 계층적인 구조를 표현할 때 사용할수 있는 자료구조다. - 나무의 형태를 뒤집은 것과 같이 생겼다. - 루트 노드(root node): 부모가 없는 최상위 노드 - 단말 노드(leaf node): 자식이 없는 노드 - 트리에서는 부모와 자식 관계가 성립한다. - 형제 관계: 17을 값으로 가지는 노드와 48을 가지는 노드 사이의 관계 - 깊이(depth): 루트 노드에서의 길이(length) - 여기서 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수를 의미한다. - 트리의 높이(height)는 루트 노드에서 가장 깊은 노드까지의 길이를 의미한다. # 이진 트리(Binary Tree) - 최대 2개의 자식을 가질 수 있는 트리를 말한다. # 우선순위 .. 2023. 8. 17. [알고리즘] 2-4. 큐(queue) # 큐(Queue) - 먼저 삽입된 데이터가 먼저 추출되는 자료구조다. # 연결리스트로 큐 구현하기 - 큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있다. - 연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가진다. - 머리(head): 남아있는 원소 중 가장 먼저 들어온 데이터를 가리키는 포인터 - 꼬리(tail): 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터 - 삽입할 때는 꼬리위치에 데이터를 넣는다. - 삭제할 때는 머리위치에서 데이터를 꺼낸다. # 큐 동작 속도: 배열 VS 연결리스트 - 다수의 데이터를 삽입 및 삭제할 때에 대하여, 수행 시간을 측정할 수 있다. - 단순히 배열 자료형을 이용할 때보다 연결 리스트를 사.. 2023. 8. 15. [알고리즘] 2-3. 스택(Stack) # 스택(Stack) - 먼저 들어온 데이터가 나중에 나가는 자료구조 - 흔히 박스가 쌓인 형태, - 프링클스 과자 통 !!! - 박스를 쌓은 뒤에 꺼낼 때는 가장 마지막에 올렸던 박스부터 꺼내야 한다. - 새로운 원소를 삽입할 때는 마지막 위치에 삽입한다. - 새로운 원소를 삭제할 때는 마지막 위치가 삭제된다. # 스택 자료구조의 중요성 - 스택은 굉장히 기본적인 자료구조이다. - 다양한 알고리즘/ 코딩 테스트 문제에서 자주 등장한다. # 스택 자료구조의 시간 복잡도 - 스택은 여러 가지 연산을 제공한다. # 자바스크립트에서 스택을 구현하는 방법 - 배열 자료형 - 자바스크립트의 기본적인 배열 자료형은 다음의 두가지 메서드를 제공한다. - push() 메서드: 마지막 위치에 원소를 삽입하며, 시간 복잡.. 2023. 8. 15. 이전 1 2 3 4 5 다음
