본문 바로가기

Algorithm76

[알고리즘] 자바로 수학 log 구하기 log 성질 $\log _{3}{5} = \frac{\log {5} }{\log {3}}$ //둘 다 결과는 같다. System.out.println(Math.log10(5) / Math.log10(3)); System.out.println(Math.log(5) / Math.log(3)); 응용 $x^{6} = 64$ 의 $x$ 구하기 $6 = log _{x}{64}$ → $6 = \frac{log _{10}{64}}{log _{10}{x}}$ → $log _{10}{x} = \frac{log _{10}{64}}{6}$ 결론 : $x = 10 ^ {\frac{log _{10}{64}}{6}}$ System.out.println(Math.pow(10, Math.log10(64) / 6)); //결과 : 2.0 2020. 10. 17.
[알고리즘] 10진수 → 2진수 변환 //10진수 -> 2진수 int quotient = 3; ArrayList list = new ArrayList(); while(quotient > 0) { //나머지값 계산후 입력 int remainder = quotient % 2; list.add(remainder); quotient /= 2; } //역순 출력 for(int i = list.size()-1;i>=0;i--) System.out.print(list.get(i)); //결과 : 11 2020. 10. 16.
[알고리즘] 풍선 터트리기 (월간 코드 챌린지 시즌1 - 9월) 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 월간 코드 챌린지 9월에 나온 레벨3 문제다. 9월 10월 둘 다 풀면서 느낀건 브루트 포스 문제보단 아이디어로 시간복잡도를 최소화 해가면서 푸는 방식을 원하는 것 같다. 이 문제 또한 N이 최대 1백만이기에 O(N ^ 2)으론 풀 수가 없다. Solution 먼저 파악해야할 것은 어떤 특정값이 최후까지 살아남는지 알아볼 때, 양쪽에 있는 수들은 서로 만날 수가 없다. 그렇기에 특정값을 기준으로 왼쪽 오른쪽으로 나누어서 살펴봐야 한다. 그리고 양쪽에서 최후까지 살아남을 수 있는 수는 각각 2가지가 되는데 '최소값, 최소값보다 한단계 더 큰 값'이 될 수 있다. 최소값은.. 2020. 10. 9.
[알고리즘] 코딩테스트 전, 알고리즘 문제 유형 정리 ※ 생각 나는 대로 적는 중... (잘못된 부분이 있을 수도 있음) 브루트 포스 (완전 탐색) N의 범위를 잘 파악해서 1초 미만으로 해결이 가능한 경우 10! 이하의 시간복잡도인 경우 (재귀 호출 시 깊이가 10 이하인 경우) 1. 백트랙킹 순열 : 순서 고려 O, 값의 중복 X (시간복잡도 : O(N!) ) 중복 순열 : 순서 고려 O, 값의 중복 O (시간복잡도 : O(n ^ r), 여기서 r은 재귀의 깊이 ) 조합 : 순서 고려 X, 값의 중복 X 중복 조합 : 순서 고려 X, 값의 중복 O 재귀 호출 시 깊이를 보고 시간복잡도 파악 가능하다. 2. BFS 출발값이 존재 도착값까지 '최소' 시간 or 거리 or 횟수 만에 도착해야하는 경우 간선의 가중치(노드 간 거리)가 전부 같은 경우 (무가중 .. 2020. 10. 7.