찰떡개발자 코딩

알고리즘에 대해서 너무 모르는것 같아 하나씩 시간 날때마다 공부해 보려고 한다. 이진탐색 알고리즘이란 정렬되어 있는 자료들의 집합에서 특정 자료를 찾고자 할 때 많이 사용 이진 탐색은 '퀵정렬'과 유사하게 '분할 후 정복(divide and conquer)'의 전략을 사용 실행시간은 log 특히 문제의 크기를 정확히 양분하는 경우에는 최악의 경우 logN의 성능을 보장한다. 이진 탐색의 탐색 시간은 'T = K * logN'으로 O(logN)이다. 선형 탐색의 시간보다 상당히 빠르지만 이진 탐색은 반드시 정렬이 되어있어야 한다. 정렬하는 비용이 든다는 단점이 있다. 다음과 같은 상황에서 이진 탐색은 효율적인 성능을 제공한다. 1) 새로운 자료가 추가되었어도 모든 자료가 재정렬이 일어나지 않는 경우 -> ..

여러가지 정렬 알고리즘 중 선택정렬, 버블정렬, 삽입정렬에 대해 정리를 해보려고 한다. 1). 삽입정렬 (Insortion Sorting) : 삽입정렬은 기준이 되는 인덱스의 앞쪽을 검사하여 기준이 되는 인덱스가 들어갈 자리를 찾아서 삽입하는 정렬이다. class Sort { public List sortNum(int[] arrs) { List list = new LinkedList(); loop:for (Integer num : arrs) { for (int i = 0; i num) { list.add(i,num); continue loop; } } list.add(num); } return list; } } public class TE..

재귀함수 사용의 가장 기초적인 팩토리얼을 연습해보려고한다. 다시 한번 복습하는 생각으로 보면 괜찮겠다. public class testMain { public static int Function(int num){ System.out.println(num); if(num == 1){ return 1; }else{ return num * Function(num -1); } } public static void main(String[] args) { System.out.println(Function(5)); } } 부르고 ~ 부르고 ~ 부르고 ~ 부르고~ 끝

우선 크게 String과 StringBuffer & StringBuilder로 차이점을 확인 해보자. String & StringBuilder & StringBuffer 비교 1). String vs StringBuilder & StringBuffer 차이점 String : 객체는 한번 생성되면 할당된 공간이 변하지 않음(immutable) StringBuffer & StringBuilder : 객체의 공간이 부족해지는 경우 버퍼의 크기를 유연하게 늘려줍니다. (mutable) 메모리 관점으로 설명을 추가해보자면... String은 Immutable하기 때문에 메모리상에 추가적인 공간을 할당받아야한다 예를 들어 , hello를 메모리에 올리고, world를 추가해서 이어붙이려고한다. 이때 메모리상에서는 ..

1). 문제 : www.hackerrank.com/challenges/minimum-absolute-difference-in-an-array Minimum Absolute Difference in an Array | HackerRank Given a list of integers, calculate their differences and find the difference with the smallest absolute value. www.hackerrank.com 2). 풀이 : 2중 For문으로 처음에 풀었다가, Timeout으로 TestCase 몇개가 걸렸다. 아래 풀이의 KeyPoint는 인접한 값의 차이 = 최소값 이라는 점이다. import java.io.*; import java.math.*..

1). 문제 : www.hackerrank.com/challenges/sherlock-and-valid-string Sherlock and the Valid String | HackerRank Remove some characters from the string such that the new string's characters have the same frequency. www.hackerrank.com 2). 풀이 : import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; p..

1). 문제 : www.hackerrank.com/challenges/sherlock-and-anagrams/ Sherlock and Anagrams | HackerRank Find the number of unordered anagramic pairs of substrings of a string. www.hackerrank.com 2). 풀이 : Comparator를 알고있는지 모르는지에 대한 문제였던것 같다. compareTo를 사용했을때 클때, 같을때 작을때 1, 0, -1 을 return하는것만 알고있으면 비교할때 쉬울수있는 문제. import java.util.*; class Player { String name; int score; Player(String name, int score) { ..

1). 문제 : www.hackerrank.com/challenges/two-strings Two Strings | HackerRank Given two strings, you find a common substring of non-zero length. www.hackerrank.com 2). 풀이 : import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; public class Solution { // Complete the twoStrings function below. s..

1). 문제 : www.hackerrank.com/challenges/ctci-ransom-note/ Hash Tables: Ransom Note | HackerRank Given two sets of dictionaries, tell if one of them is a subset of the other. www.hackerrank.com 2). 풀이 : import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; public class Solution { // Complete th..

Set 정의 : 중복되지 않는 데이터의 집합 => 수학적으로 집합과 동일하다. 특징 : 데이터가 중복되지 않는다. 순서가 보장될수도 있다. Set은 인덱스로 관리하지 않는다고 했다. 그러므로 데이터를 검색하기 위해서는 iterator() 메서드로 반복자를 생성하고 데이터를 가져와야 한다. 시간복잡도를 먼저 알아보자 추가적으로 HashSet이 TreeSet이나 LinkedHashSet보다 성능이 더 빠르고, 메모리를 적게 사용한다. 1). HashSet 정의 : 중복이 안되고 순서가 없는 형태의 Set 특징 : 빠른 접근속도 중복 허용하지 않음 순서 보장하지 않음 => 순차적으로 정렬해준다고 100% 믿으면 안됀다. 예제 : public static void main(String[] args) { Set ..