◈ Coding Test/알고리즘(Algorithm)🎡

[알고리즘] 완전탐색, 브루트 포스(brute force) [무차별 대입(無差別代入), A부터 Z까지 다 해보기]

- 완전탐색, 브루트 포스(brute force) 브루트 포스는 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식이다. 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)이라 불린다. 이 방식은 오래 걸리고 자원이 엄청나게 들어서 무식해보이지만, 항상 정확도 100%를 보장한다. ex) 4자리 숫자로 된 비밀번호 → 총 1만 개의 조합 중 하나 (0000, 0001, 0002, ... 9999) - 브루트포스 활용 문제 - 실버 5 💍 : 영화감독 숌 [백준/BOJ] 1436번: 영화감독 숌 - JAVA [자바] 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상..

[알고리즘] 에라토스테네스의 체(Sieve of Eratosthenes) [간단하고 빠르게 소수 찾기]

- 에라토스테네스의 체(Sieve of Eratosthenes) 에라토스테네스의 체는 간단하고 빠르게 소수를 찾는 방법이다. 아래는 에라토스테네스의 체를 구현해 놓은 코드이다. private static boolean[] eratos(int num) { // 0과 1은 소수가 아님 if(num < 2) { return 0; } // 0부터 num까지의 배열 생성 boolean[] nums = new boolean[num + 1]; // 0과 1을 true로 초기화. false는 소수, true는 소수가 아닌 수 nums[0] = nums[1] = true; /*에라토스테네스의 체에 맞게 소수를 구함 *1) nums[i]가 true이면 i 이후의 i 배수는 약수로 i를 가지고 있는 것이 되므로 i 이후의 ..

[알고리즘] 트리 정렬(Tree Sort) [이진 탐색 트리를 활용한 정렬 알고리즘]

- 트리 정렬(Tree Sort)이란? 이진 탐색 트리를 만들어 정렬하는 방식. 힙 정렬과 비슷해 보이지만 정렬될 자료의 각 원소 크기에 따라 부모 노드의 왼쪽 자식이 되느냐 오른쪽 자식이 되느냐가 다르다. - 트리 정렬의 정렬 과정 정렬될 배열의 맨 첫 값이 루트 노드가 된다. 다음 값부터는 기존 노드 값과 비교한다. 루트 노드에서 출발해서 추가될 노드 값이 기존 노드 값보다 작은 경우는 왼쪽 자식을, 기존 노드 값보다 크거나 같을 경우는 오른쪽 자식을 찾는다. 내림차순은 반대로 기존 노드 값보다 크면 왼쪽, 작거나 같으면 오른쪽을 찾으면 된다. 위 2에서 해당 방향의 자식 노드가 없으면 그 방향의 자식 노드로 추가한다. 있으면 그 방향의 자식 노드로 가서 크기를 비교하고 위 2와 같은 방법으로 해당 ..

[알고리즘] 퀵 정렬(Quick Sort) [찰스 앤터니 리처드 호어의 정렬 알고리즘]

- 퀵 정렬(Quick Sort)이란? 적절한 원소 하나를 기준(pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 그 뒤에 기준을 옮겨 기준보다 작은 것, 큰 것으로 나눈뒤 나누어진 각각에서 다시 기준을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다.

[알고리즘] 힙 정렬(Heap Sort) [힙 트리를 활용한 정렬 알고리즘]

- 힙 정렬(Heap Sort)이란? 선택 정렬과 거의 같은 알고리즘으로, 가장 큰 원소를 뒤로 보내는 데에 매번 쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점이다. - 힙 정렬의 정렬 과정 원소들을 전부 힙에 삽입한다. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다. 힙이 빌 때까지 2의 과정을 반복한다.