반응형 분류 전체보기160 팰린드롬 팰린드롬은 순서를 거꾸로 읽었을 때도 원래의 문자열이나 수열과 동일한 경우 1. 투포인터 방식public static boolean isPalindrome(String str) { int left = 0; int right = str.length() - 1; while (left 2. 문자열을 뒤집는 방식public static boolean isPalindrome(String str) { String reversed = new StringBuilder(str).reverse().toString(); return str.equals(reversed);} 시간복잡도는 모두 O(N)으로 동일하지만투포인터는 N/2이고, 문자열을 뒤집는 경우 2N이고 문자열 뒤집기는 새로운 문자를 .. 2025. 6. 14. 이진탐색 이진탐색(BinarySearch)정렬된 배열에서 타깃을 원하는 요소를 찾는 알고리즘시간복잡도 O(logN)이진탐색트리와 이름이 비슷하지만 이진탐색트리는 정렬된 요소를 저장하고 탐색하는 자료구조라면,이진탐색은 정렬된 배열에서 값을 찾아내는 알고리즘이다. [이진탐색 과정]1부터 100이 주어진 배열에서 77 찾기1차 탐색1...50...1002차 탐색50...75...1003차 탐색75...81...874차 탐색75...78...815차 탐색75...76...786차 탐색76...77...78 [이진탐색 java 코드]public static int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (.. 2025. 6. 14. 허프만 코딩 허프만 코딩문자의 빈도를 이용해 압축하는 방법으로 빈도가 높은 문자는 적은 비트로, 빈도가 낮은 문자는 높은 비트로 표현하여 필요한 비트 수를 줄여 압축하는 방식(-> 높은 압축률)문자열 압축을 위해 허프만 트리를 사용함각 문자에 대한 출현 빈도수를 구하여 내림차순으로 정렬한 뒤 빈도수가 가장 낮은 두 값을 자식 노드로, 빈도수의 합을 부모노드로 하는 연산을 반복적으로 수행하여 트리를 구성함허프만 트리를 구성하면 모든 문자열은 리프노드에 위치함왼쪽가지를 1, 오른쪽 가지를 0으로 표현하여 리프노드(문자열)에 노드에 도달하는데 거쳐가는 비트로 문자열 표기-> 문자열이 모두 리프노드에 위치하므로 문자열 간에 접두부가 겹치지 않음-> 문자열을 표현하는데 겹치는 비트가 없으므로 압축 이후 데이터 손실이 발생하지.. 2025. 6. 12. [정렬 알고리즘] 합병 정렬, 퀵정렬, 계수 정렬 합병정렬(머지소트)주어진 배열을 크기가 1인 배열이 될때까지 두개씩 쪼개나가는 분할 과정을 진행한 후 하나씩 합쳐나가며 정렬을 수행함(분할정복 알고리즘)합병정렬을 위해 추가적인 메모리 공간을 필요로함(제자리 정렬X)중복된 데이터에 대해 입력순서를 유지하는 안정정렬시간복잡도 : O(NlogN)2개씩 분할하는 과정을 보면 마치 이진트리가 생성되는 절차와 같다. -> logN크기가 1인 배열이 되면 다시 2개씩 합병하며 정렬을 수행함 -> N따라서, 정렬에 O(NlogN)의 시간복잡도를 보임분할정복 알고리즘분할 정복알고리즘은 큰 하나의 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음 결과를 모아 해결하는 기법이다.일반적으로 쪼갠 문제를 또다시 쪼개어 나가는 방식으로 순환호출 방식을 이용하여 구현한다. N.. 2025. 6. 12. 이전 1 2 3 4 5 6 7 ··· 40 다음 반응형
