숫자 뒤집기
예제 - LeetCode 9. Palindrome Number
1. 문제 이해
- 팰린드롬(앞에서부터 읽어도 뒤에서부터 읽어도 같은 수) 찾기
2. 요구사항 분석
- 입력
- x : int 범위
- 출력
- true : 펠린드롬 O
- false : 펠린드롬 X
3. 해결 아이디어
- 음수는 -기호로 인해 펠린드롬이 아님
- 수학적 뒤집기 : 입력 값을 뒤집은 값을 구하고 입력 값과 뒤집은 값이 같으면 펠린드롬
- 문자열 + 투포인터 : 문자열로 변환 후 투포인터로 앞, 뒤를비교하며 달라지면 펠린드롬이 아님
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 수학적 뒤집기 : 자릿수(최대 10)를 하나씩 뒤집으므로 O(n)
- 문자열 + 투포인터 : 자릿수(최대 10)를 하나씩 확인하므로 O(n)
- 공간 복잡도
- 수학적 뒤집기 : 고정된 개수의 변수만 사용하므로 O(1)
- 문자열 + 투포인터 : 길이가 n인 문자열이 필요하므로 O(n)
공간 복잡도에 이점이 있는 수학적 뒤집기 방법을 선택
5. 구현
class Solution {
public boolean isPalindrome(int x) {
// 1. 음수인 경우 false
if (x < 0) return false;
// 2. 기존 값과 뒤집은 값을 저장할 변수 할당
int original = x;
int reversed = 0;
// 3. 뒤집은 값 구하기
while (x != 0) {
int digit = x % 10; // 1) 일의 자리수 구하기
reversed = reversed * 10 + digit; // 2) 뒤집은 값을 한자리씩 앞으로 이동 + 3) 앞에서 구한 일의 자리수를 끝에 더하기
x /= 10; // 4) 다음 자리수를 구하기 위해 기존 값의 일의 자리수 버림
}
// 4. 기존 값과 뒤집은 값을 비교한 결과를 출력
return original == reversed;
}
}
정수에 1 더하기(받아올림)
예제 - LeetCode 66. Plus One
https://leetcode.com/problems/plus-one/description/?envType=study-plan-v2&envId=top-interview-150
1. 문제 이해
- 주어진 정수에 1을 더하기
2. 요구사항 분석
- 입력
- digits : 정수 배열, 1 <= digits.length <= 100
- digits[i] : 자릿수, 0 <= digits[i] <= 9
- 가장 높은 자릿수를 왼쪽에
- 첫번째 자릿수에는 0이 오지 않음
- 출력
- 1을 더한 후의 정수 배열
3. 해결 아이디어
- 1의 자릿수부터 1씩 더하기
- 결과가 10 이면 현재 자릿수는 0 할당, 다음 자릿수에는 1 더해주기
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 자릿수(최대 100)를 하나씩 확인하므로 O(n)
- 공간 복잡도
- 초과한 값을 더해줄 변수 1개와 기존의 배열보다 한칸 커지는 경우 새로운 배열이 필요하므로 O(n)
5. 구현
class Solution {
public int[] plusOne(int[] digits) {
// 1. 초과한 값을 저장할 변수 할당, 처음은 1을 더하므로 1로 초기화
int carry = 1;
// 2. 가장 낮은 자릿수(마지막 인덱스)부터 1을 더하기
for (int i = digits.length - 1; i >= 0; i--) {
int sum = digits[i] + carry; // 1) 현재 자릿수에 초과한 값 더하기
// 2) 합이 10을 넘지 않으면 해당 배열 바로 반환
if (sum < 10) {
digits[i] = sum;
return digits;
}
// 3) 합이 10이면, 현재 자릿수는 0으로 할당하고, 다음 자릿수에 1 더해주기
digits[i] = 0;
carry = 1;
}
// 3. 기존값보다 자릿수가 늘어나는 경우, 맨 앞은 1, 나머지는 0이 들어가야 함
int[] result = new int[digits.length + 1];
result[0] = 1;
return result;
}
}
소인수 분해(곱해진 소수의 갯수 구하기)
예제 - LeetCode 172. Factorial Trailling Zeroes
1. 문제 이해
- 팩토리얼을 계산했을 때, 맨 뒤에 연속으로 등장하는 0의 갯수 구하기
2. 요구사항 분석
- 입력
- n : 0 <= n <= 10,000
- 출력
- 0의 갯수
3. 해결 아이디어
- 10이 곱해진 갯수가 맨 뒤에 연속으로 등장하는 0의 갯수
- 2는 5보다 많이 곱해지므로 5의 갯수만 구함
- 5가 한개 곱해진 수, 두개 곱해진 수, .... 를 5의 제곱수를 나누면서 확인
- 5 -> 5가 한 번 곱해진 수의 갯수
- 25 -> 5가 두 번 곱해진 수의 갯수(이미 5에서 1개 더했으므로 1만 더함)
- 분모가 분자보다 작으면 분모에 5를 곱해가며 반복
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 5의 제곱수로 확인하므로 O(logn)(밑이 5)
- 공간 복잡도
- 고정된 개수의 변수만 사용하므로 O(1)
5. 구현
class Solution {
public int trailingZeroes(int n) {
// 1. 갯수와 분모를 저장할 변수 할당
int count = 0;
long divisor = 5;
// 2. 5, 25, 125, 625... 등 5의 제곱수를 계속 나누어가며 갯수를 더함
// 5 -> 5가 한번 곱해짐 1씩 더함
// 25 -> 5가 두번 곱해짐 1씩 더함(이미 5에서 한번 더했으므로 한번만 더하면 됨)
while (divisor <= n) {
count += n / divisor;
divisor *= 5;
}
return count;
}
}
제곱근
예제 - LeetCode 69. Sqrt(x)
1. 문제 이해
- 음이 아닌 정수의 제곱근 구하기
- 내장 함수 사용 불가(Math.pow(x, 0.5), x**0.5 등)
2. 요구사항 분석
- 입력
- x : int의 양의 범위
- 출력
- x의 제곱근에 근접한 최대값 구하기
3. 해결 아이디어
- 브루트 포스 : 0 ~ x까지 제곱을 하면서 확인
- 이분 탐색 : 0 ~ x의 범위에서 mid 값을 기준으로 반씩 줄여가며 확인
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 브루트 포스 : x까지의 수를 하나씩 확인하므로 O(n)
- 이분 탐색 : 0 ~ x 범위를 반씩 줄여가며 확인하므로 O(logn)
- 공간 복잡도
- 브루트 포스 : 고정된 개수의 변수만 사용하므로 O(1)
- 이분 탐색 : 고정된 개수의 변수만 사용하므로 O(1)
브루트 포스는 최대 약 21억번의 연산이 필요하므로 시간 초과가 발생하므로 이분 탐색을 선택
5. 구현
class Solution {
public int mySqrt(int x) {
// 1. 0 또는 1인 경우 자신을 바로 반환
if (x < 2) {
return x;
}
// 2. 이분 탐색을 위해 범위를 지정할 변수 할당
int left = 1;
int right = x;
// 3. 이분 탐색
while (left <= right) {
int mid = left + (right - left) / 2; // 3-1) 중간값 구하기
long square = (long) mid * mid; // 3-2) mid의 제곱은 int 범위를 넘을 수 있으므로 long 사용
if (square == x) { // 3-3) 제곱근 발견하면 mid 값 반환
return mid;
} else if (square < x) { // 3-4) 더 큰 제곱근이 필요하므로 왼쪽 경계를 옮기기
left = mid + 1;
} else { // 3-5) 더 작은 제곱근이 필요하므로 오른쪽 경계를 옮기기
right = mid - 1;
}
}
// 4. 반복이 끝났을 때 right(mid - 1)가 제곱근 이하 최대값
return right;
}
}
거듭제곱
예제 - LeetCode 50. Pow(x, n)
https://leetcode.com/problems/powx-n/description/?envType=study-plan-v2&envId=top-interview-150
1. 문제 이해
- x의 n 거듭제곱 구하기
2. 요구사항 분석
- 입력
- x : -100 < x < 100, 실수
- n : int 범위, 정수
- x가 0이 아니거나 n > 0
- -10,000 <= x의 n거듭제곱 <= 10,000
- 출력
- x의 n 거듭제곱
3. 해결 아이디어
- 브루트 포스 : x를 n번 곱하기
- 분할 정복 : 절반씩 계산
- n이 짝수 : xn = (xn/2)2
- n이 홀수 : xn = x × (x(n−1)/2)2
- n이 음수라면, n은 양수로 x는 1/x로 변경 후 계산
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 브루트 포스 : x를 n번 곱해야하므 O(n)
- 분할 정복 : 거듭제곱하면서 반씩 계산하므로 O(logn)
- 공간 복잡도
- 브루트 포스 : 고정된 개수의 변수만 사용하므로 O(1)
- 분할 정복: 고정된 개수의 변수만 사용하므로 O(1)
브루트 포스는 최대 약 21억번의 연산이 필요하므로 시간 초과가 발생하므로 분할 정복을 선택
5. 구현
class Solution {
public double myPow(double x, int n) {
// 1. n이 0이면 어떤 x든 간에 결과는 1
if (n == 0) {
return 1.0;
}
// 2.곱하는 값이 int 범위를 벗어날 수 있으므로 long으로 할당
long power = n;
// 2-1) 초기 power이 음수라면 power이은 양수로 x는 1/x로 변경
if (power < 0) {
power = -power;
x = 1 / x;
}
// 3. 결과를 저장할 변수 할당
double result = 1.0;
// 4. 분할 정복으로 거듭제곱 계산
while (power > 0) {
// 4-1) power이 홀수라면 x를 한번 곱함
if ((power % 2) == 1) {
result *= x;
}
// 4-2) x를 제곱하고 곱해야할 횟수를 절반으로 줄임
x *= x;
power /= 2;
}
return result;
}
}
소수 구하기
예제 - LeetCode 204. Count Primes
https://leetcode.com/problems/count-primes/description/
1. 문제 이해
- n보다 작은 모든 소수 구하기
2. 요구사항 분석
- 입력
- 0 <= n <= 5,000,000
- 출력
- n보다 작은 모든 소수의 갯수
3. 해결 아이디어
- 브루트 포스 : 모든 n에 대해서 √n까지 직접 소수 확인
- 에라토스테네스의 체 : 0에서 n-1까지의 수를 나열하고 배수를 지워나가는 방식으로 확인
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 브루트 포스 : 모든 n에 대해서 √n까지 소수 확인을 반복하므로 O(n √n )
- 에라토스테네스의 체 : 소수에 대한 조화급수의 근사치 O(nloglogn)
- 공간 복잡도
- 브루트 포스 : 고정된 개수의 변수(소수의 갯수만 셈)만 사용하므로 O(1)
- 에라토스테네스의 체: 길이가 n인 불리언 배열이 필요하므로 O(n)
브루트 포스는 최대 약 100억 이상의 연산이 필요, 에라토스테네스의 체는 약 1000만번의 연산이 필요하므로 에라토스테네스의 채 사용
5. 구현
class Solution {
public int countPrimes(int n) {
// 1. n이 2 이하라면 소수가 없음
if (n <= 2) {
return 0;
}
// 2. 에라토스테네스의 체를 위한 불리언 배열 할당, true로 초기화
boolean[] isPrime = new boolean[n];
for (int i = 2; i < n; i++) {
isPrime[i] = true;
}
// 3. 에라토스테네스의 체 실행 루트n까지만 확인하면 됨
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
// 3-1) i가 소수라면 i의 배수들을 false로 변경
for (int multiple = i * i; multiple < n; multiple += i) {
isPrime[multiple] = false;
}
}
}
// 4. 소수 개수 세기
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
}
최대공약수, 최소공배수
예제 - Programmers 최대공약수와 최소공배수
https://school.programmers.co.kr/learn/courses/30/lessons/12940
1. 문제 이해
- n과 m의최대공약수와 최소공배수 구하기
2. 요구사항 분석
- 입력
- 1 <= n, m <= 1,000,000
- 출력
- 크기가 2인 배열, 0번 인덱스에는 최대공약수, 1번 인덱스에는 최소공배수
3. 해결 아이디어
- 최대공약수 : 유클리드 호제법 사용, gcd(n, m) = gcd(m, n mod m)
- 최소공배수 : (n * m) / gcd(n, m), n*m이 int 범위를 벗어날 수 있음
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 최대공약수 : 수를 나눠가면서 계산하므로 O(logn)
- 최소공배수 : 값이 주어지면 바로 계산할 수 있으므로 O(1)
- 공간 복잡도
- 최대공약수 : 고정된 개수의 변수만 사용하므로 O(1)
- 최소공배수 : 고정된 개수의 변수만 사용하므로 O(1)
5. 구현
class Solution {
public int[] solution(int n, int m) {
// 1. 최대공약수 할당
int gcdValue = gcd(n, m);
// 2. 최소공배수 할당, n * m이 int 범위를 넘어갈 수 있음에 주의
int lcmValue = (int)((long) n * m / gcdValue);
return new int[] { gcdValue, lcmValue };
}
// 유클리드 호제법 + 재귀를 활용한 최대공약수 구하기
private int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
같은 직선 상의 점
예제 - LeetCode 149. Max Points on a Line
1. 문제 이해
- 같은 직선 상에 놓인 점의 최대 개수
2. 요구사항 분석
- 입력
- points : 정수 배열, 1 <= points.length <= 300
- points[i].length = 2
- -10,000 <= x,y 좌표 <= 10,000
- 모든 점은 중복되지 않음
- 출력
- 같은 직선 상에 놓인 점의 최대 개수
3. 해결 아이디어
- 임의의 점과 다른 점과의 기울기를 구함
- 기울기가 같은 점들은 같은 직선 상에 존재, HashMap에 기록
- 기울기 계산시 부동 소수점은 오차 발생 가능하므로 기약 분수로 관리
4. 시간 복잡도 및 공간 복잡도 확인
- 시간 복잡도
- 각 점마다 다른 모든 점의 기울기를 구해야 하므로 O(n^2)
- 공간 복잡도
- 각 점마다 해쉬맵을 만들어야 하므로 O(n)
5. 구현
class Solution {
public int maxPoints(int[][] points) {
// 1. 점이 2개이하라면 n개가 최대 점의 갯수
if (points.length <= 2) {
return points.length;
}
// 2. 계산의 편의를 위한 길이 변수와 정답 변수 할당
int n = points.length;
int maxCount = 1;
// 3. 각 점을 기준으로 나머지 점과의 기울기 구하기
for (int i = 0; i < n; i++) {
// 3-1) 기준점 할당
int x1 = points[i][0];
int y1 = points[i][1];
// 3-2) 변수할당
Map<String, Integer> slopeCount = new HashMap<>(); // 키가 기울기 값이 점의 갯수인 맵
int localMax = 0; // 현재 기준점에서 가장 많은 점이 공유하는 기울기
int verticalCount = 0; // 수직선의 점의 갯수
for (int j = i + 1; j < n; j++) {
// 3-3) 비교점 및 기울기에 필요한 분자, 분모 구하기
int x2 = points[j][0];
int y2 = points[j][1];
int dx = x2 - x1;
int dy = y2 - y1;
// 3-4) 기울기에 갯수 더하기
if (dx == 0) { // 수직선인 경우
verticalCount++;
localMax = Math.max(localMax, verticalCount);
} else { // 수직선이 아닌 경우
// 3-4-1) 기약분수 형태로 분자, 분모 만들기
int gcdVal = gcd(dy, dx);
dy /= gcdVal;
dx /= gcdVal;
// 3-4-2) dx, dy가 음수인 경우 양수일 때와 기울기가 같으므로 표준화 처리
if (dx < 0) {
dx = -dx;
dy = -dy;
}
// 3-4-3) 기울기에 점 갯수 더하기
String slopeKey = dy + "/" + dx;
slopeCount.put(slopeKey, slopeCount.getOrDefault(slopeKey, 0) + 1);
// 3-4-4) 최대 갯수 더하기
localMax = Math.max(localMax, slopeCount.get(slopeKey));
}
}
// 3-4-5)현재 점의 최대 갯수에 본인도 포함해야하므로 + 1해서 최대 갯수 구하기
maxCount = Math.max(maxCount, localMax + 1);
}
return maxCount;
}
// 최대공약수 : 유클리드 호제법 + 재귀
private int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}'코딩테스트 > 알고리즘' 카테고리의 다른 글
| 예제로 배우는 알고리즘 - 문자열 (0) | 2025.04.28 |
|---|---|
| 예제로 배우는 알고리즘 - 해싱 (0) | 2025.04.19 |
| 예제로 배우는 알고리즘 - 배열 (0) | 2025.04.13 |
| 예제로 배우는 알고리즘 - 비트 마스킹 (0) | 2025.04.04 |
| 예제로 배우는 알고리즘 - 투 포인터 (0) | 2025.03.06 |
