알고리즘 작은 팁

커버 이미지용 최근에 찍은 사진!

알고리즘 공부를 하면서 블로그에 길게 적을 내용은 아니지만 외워두면 좋을 내용들이 많다. 오늘은 그 중에서 기억나는 것들만 추려서 정리해보려고 한다.

 

1. 거듭제곱 메소드, 제곱근 메소드

• 거듭제곱 : Math.pow(제곱할 수, 제곱 값)
• 제곱근: Math.sqrt(제곱근을 구할 수)

 

 

2. 타입 변환 방법

• char -> int : Character.getNumericValue(문자)
• int -> char : Character.forDigit(숫자, 진수)
• string -> int : Integer.parseInt(문자)
• int -> String : String.valueOf(숫자)

 

 

3. 연속하는 자연수의 합

정수론에서 "연속하는 자연수의 합은 홀수인 약수의 개수이다." 라는 말이 있다고 한다. 따라서 이를 알고리즘 문제 풀이시에 적용하여 쉽게 풀 수 있다. 예를 들어, 15이내의 연속하는 자연수의 합이 15인 값의 개수는 15를 소인수분해 했을 때 1, 3, 5, 15 이므로 4개라는 정답을 도출할 수 있다. 관련된 자료가 적어서 해당 문제풀이를 보고 이렇게 해석했다.

만약 틀렸다면 댓글 부탁드립니다!!

 

 

 

4. Arrays.sort()와 Collections.sort()의 정렬방법 차이

• Arrays.sort()는 Dual-Pivot Quick Sort  이다. 이는 Insertion Sort와 Quiuk Sort를 합친 것이다. 최악의 경우, 시간복잡도가 O(n^2)가 될 수 있다.
•  Collections.sort()는  Tim Sort  이다. 이는 Insertion Sort와 Merge Sort를 합친 것이다. 최악의 경우 시간복잡도가 O(nlogn)이다.

 

 

이번 게시물은 이정도이다.

공부하면서 다른 팁들도 알게 된다면 꼭 블로그에 적어서 잊지 않도록 해야겠다. 오늘도 좋은 하루였다!