본문 바로가기

💻/Algorithm

(6)

힙(Heap) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 최대값과 최소값을 쉽게 추출할 수 있는 구조 최대힙과 최소힙

소수_에라토스테네스의 체 소수들을 대량으로 빠르고 정확하게 구하는 방법 for(int i = 2; i

최대 공약수_유클리드 호제법 : 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. private static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }

char to int / ASCII CODE Char > int char - '0'; ASCII CODE (int)char

완전 탐색/DFS/BFS 완전 탐색 (브루트 포스) 가능한 모든 경우의 수를 다 시도해 답을 찾는 방법 정확하고 확실하게 답을 찾을 수는 있지만, 시간이 오래 걸린다. 모든 경우의 수를 구하는 문제 같은 부분에서 많이 사용되는 알고리즘 - 완전 탐색 기법 종류 DFS(깊이 우선 탐색) : 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 어떤 노드를 방문했었는지 여부를 반드시 검사 1. 순환 호출 이용(자기 자신을 호출하는순환 알고리즘의 형태) 2. 명시적인 스택 사용 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업한다. 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다..

Stack/Queue/Deque/PriorityQueue Stack Last-In, First-Out -> LIFO 나중에 들어간 것이 먼저 나오는 구조 push: 데이터 삽입 pop: 데이터 조회 + 삭제 peek: 데이터 조회 clear: 데이터 전체 삭제 size: stack 사이즈 empty: stack 비어있는지 여부 contains: 특정 데이터 포함 여부 search: 특정 데이터 위치 반환 Queue First-In, First-Out -> FIFO 먼저 들어간 것이 먼저 나오는 구조 LinkedList로 생성 ex) Queue queue = new LinkedList(); add / offer: 데이터 삽입 remove / poll: 데이터 삭제 peek: 데이터 조회 clear: 데이터 전체 삭제 Deque queue의 양쪽으로 데이터를 삽입..

이전 1 다음

티스토리툴바