늘 겸손하게

주어진 숫자 n이 소수인지 판단하는 함수를 만들어보자. 방법 1 단순하게 숫자 2부터 n - 1 까지 모든 숫자를 하나씩 나누어봤을때 나누어 떨어지면 소수가 아니라고 판단하는 방법이 있다. 이 방법은 단순하고 직관적이나 효율적이지 못하다. 왜냐하면, 2를 제외한 짝수는 모두 소수가 아니고, 모든 수는 제곱근의 제곱으로 나타낼 수 있기 때문에 n - 1까지 모두 나누어 볼 필요없이 n 제곱근 이하의 숫자만으로도 소수 판별이 가능하기 때문이다. 방법 2 숫자 2부터 n - 1의 제곱근까지 수 중, 홀수 숫자만으로 나누어서 소수 판별. 자바 public boolean isPrime(long number) { if (number == 1) return false; if (number == 2 || number ..

코딩테스트 문제를 풀다보면 순열, 조합 혹은 중복순열, 중복조합을 활용해야 하는 경우가 종종 있다. 하나하나 정리해보자. 1. 순열 순열은 주어진 n개의 원소에서 순서에 상관있게 r 개를 나열하는것을 말합니다. 예로 1, 2, 3, 4 에서 2개의 원소를 뽑아 나열하는 경우 1, 3 3, 1 은 다른 경우가 됩니다. 두 경우 모두 1과 3으로만 이루어져 있지만 순서가 다르기 때문에 다른 경우로 봅니다. 경우의 수는 총 nPr = n! / (n - r)! 구현 방식 백트래킹 방식으로 구현 가능하며 한 번 방문한 요소는 다시 방문할 필요가 없으므로 visit 배열을 활용해 방문하지 않은 원소 위주로 탐색합니다. depth를 1씩 늘려가며 이전에 방문하지 않은 요소를 정답 기록용 배열 (int[] rec) 에..

[ LCS 정의 ] LCS는 Longest Common Substring, Longest Common Subsequence 두 가지를 의미합니다. Longest Common Substring는 최장 공통 문자열, Longest Common Subsequence는 최장 공통 부분수열. [ 둘의 차이점은? ] 둘의 차이점은 연결되는 문자열인가, 수열인가의 차이입니다. 최장 공통 부분수열은 수열을 찾는것이기 때문에 연결되지 않아도 문제없습니다. ABCDEF GBCDFE -> BCDF ABCDEF GBCDFE -> BCDE 하지만 최장 공통 문자열은 문자열이기 때문에 연결되어 있는 동시에 공통된 문자열을 찾아야 합니다. ABCDEF GBCDFE -> BCD 최장 공통 문자열 ( Longest Common Sub..

[ 후위 표기식? ] 우리가 일반적으로 사용하는 수학식은 '중위 표기식'을 사용합니다. '3 + 5'와 같이 연산자가 (+, -, *, / ) 피연산자(숫자) 중간에 위치하는 방식이 '중위 표기식' 입니다. '후위 표기식'은 '35+'와 같이 연산자가 피연산자 뒤에 있는 방식입니다. 중위 표기식을 후위 표기식으로 바꾸는 일은 스택(Stack)을 활용한 차량기지 알고리즘으로 가능합니다. [ 차량기지 알고리즘 ] 수학식을 맨 앞부터 참조하며 1. 피연산자(숫자)는 바로 출력 2. 연산자의 경우 2 - 1. ' ( ' 의 경우 바로 스택에 저장 2 - 2. ' ) ' 의 경우, ' ( '을 만날 때까지 스택에서 pop한 값 출력 2 - 3. 곱하기와 나누기( * , / )는 스택 맨위의 연산자가 곱하기 또는 ..