💻 1. 이분탐색(Binary Search)이란?이분탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 배열을 반으로 나누어 탐색 범위를 좁혀가며 값을 찾습니다. 그 덕분에 시간 복잡도가 O(log n)으로 매우 빠릅니다.🔍 1.1 이분탐색의 동작 원리배열의 중간 값을 확인합니다.중간 값이 찾고자 하는 값과 같다면 탐색을 종료합니다.중간 값이 찾고자 하는 값보다 크다면, 배열의 왼쪽 절반을 대상으로 탐색을 계속합니다.중간 값이 찾고자 하는 값보다 작다면, 배열의 오른쪽 절반을 대상으로 탐색을 계속합니다.이를 값이 발견되거나 탐색 범위가 더 이상 없을 때까지 반복합니다.📜 1.2 자바로 구현해보기이제 자바로 이분탐색을 구현해보겠습니다.public ..
알고리즘
🔐 문제 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다. 큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4..
package com.lth.algorithm.programmers; import java.util.Arrays; import java.util.Comparator; public class Sort { public static void main(String[] args) { Sort sort = new Sort(); System.out.println(sort.solution(new int[]{300,30030030, 12, 4, 647467454, 2222, 2, 0, 260})); } // 길이가 같을 경우 그냥 비교한다. // 길이가 다를경우 맨 가장 앞부터 하나씩 비교 // 끝까지 비교했는데 같은값이 나올경우 짧은 문자열의 길이만큼 긴 문자열을 자른 후 비교 // 위의 과정을 계속 반복 // 만약 ..
🔴 해당 문제는 자연수 x를 - x에 n을 더합니다 - x에 2를 곱합니다. - x에 3을 곱합니다. 이 세가지 연산을 통해 y로 변환하는 최소 연산 횟수를 구하는 문제입니다. 따라서 최소 연산 횟수를 구하기 위한 bFS로 구현을 하였습니다. import java.util.LinkedList; import java.util.Queue; public class ChangeNum { public static void main(String[] args) { ChangeNum test = new ChangeNum(); System.out.println(test.solution(2,5,4)); } //최단경우의 수를 찾는것이기 때문에 bfs를 이용 //x가 y로 되기 위한 방법은 최대 x ~ y까지의 경우가 존재..
정렬을 할때에는 여러 알고리즘을 적용할 수 있습니다. 알고리즘의 성능은 일반적으로 데이터의 크기에 따라 결정됩니다. 따라서 데이터 크기에 따라 가장 효과적인 정렬 방법을 예시 코드와 함께 정리해 보겠습니다 작은 크기의 데이터 (수십 개 이하) 버블 정렬, 삽입 정렬이나 선택 정렬과 같은 간단한 알고리즘들이 효과적일 수 있습니다. 버블 정렬 public class BubbleSort { public static void main(String[] args) { int[] array = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(array); System.out.println("Sorted array: " + Arrays.toString(array)); } static void ..
로또는 확률로 계산이 가능할까? 일확천금의 기회 로또 과연 로또는 당첨확률을 높이는 방법이 존재할까? 여러 싸이트 도는 스팸전화로 로또확률을 높여준다며 일명 황금번호를 픽 해줄테니 달마다 얼마를 내라 하는 것을 많이 봤을것이다. 과연 이것이 정말 효과가 있는지 알아보려한다. 나무위키를 참고해보자면 로또번호는 항상 독립된 경우의 수이기 때문에 수학적으로 계산이 불가능하다고 나와있다. 즉 이전에 무슨 번호가 나왔든 영향을 받지 않으며 항상 1/45 * 1/44 * 1/43 * 1/42 * 1/41 * 1/40 = 1/8,145,060 즉 800만분의 1이다. 이렇게 명확하게 나와 있지만 뭔가 찜찜한 기분은 지울 수 없다. 아무리 이전의 상황과 별개로 독립된 새로운 경우라고 해도 이전에 나왔던 번호보다는 새로..
소수라고 하면 1과 자기 자신으로만 나누어지는 수를 말한다. 이를 찾는 방법중에 가장 오래되고 알고리즘 적으로 많이 사용되는 에라토스테네스(아리스토텔레스)의 체에 대해 알아보고 JAVA로 구현하는 까지 해 보겠다. 에라토스테네스의 체란? 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수..
스택 수열 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 87906 32204 22766 36.172% 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을..
