오늘 배운 내용
-
알고리즘 코드키타
-
gcd, 유클리드 호제법
-
큰수 String 계산프로그래머스 - 크기가 작은 부분문자열
알고리즘 코드카타
오늘부터 알고리즘 코드카타를 시작했다.
매일 알고리즘 문제를 2~3문제 풀고 푼 문제를 등록해서 현황판을 비교할 수 있었는데
다른 사람들이 어디까지 풀고있는지 볼 수 있으니 더 동기 부여가 되는것 같다.
초반에는 간단한 문제가 많아서 오늘은 1레벨에 해당되는 문제를 모두 풀어 봤다.
역시 알고리즘은 계속해서 하지 않으면 점점 헷갈리게 된다고 생각하면서 문제를 풀면서
여러가지 함수들의 사용법을 다시 리마인드 할 수 있었고, 잊고 있던 부분도 다시 찾아보면서 공부할 수 있었다.
gcd 유클리드 호제법 프로그래머스 - 최대공약수와 최소공배수
유클리드 호제법은 최대공약수를 구하는 공식으로
큰 수 a와 작은 수 b 가 있을 떄, a와 b의 최대공약수와 b와 a% b의 최대공약수는 같다.
라는 점을 이용한 알고리즘이다.
전에 코딩 테스트를 준비하면서 알고리즘 문제를 풀때 수학과 관련된 문제들을 처음에 풀었는데
굉장히 어려웠다고 느꼈다. 하지만 이번에는 유클리드 호제법이라는게 있고 어떤 방식으로 작동하는지 어느정도 기억에 남아있어서
쉽게 구현할 수 있었다.
using System;
public class Solution {
public int[] solution(int n, int m) {
int max = Math.Max(n,m);
int gcd = GCD(max, (max == n ? m : n));
return new int[] {gcd , n*m / gcd};
}
public int GCD(int a,int b){
return (a % b == 0) ? b : GCD(b, a%b);
}
}
큰수 String 계산프로그래머스 - 크기가 작은 부분문자열
주어진 긴 문자열 안에서 짧은 문자열의 길이와 같은 부분 문자열들을 비교하고
주어진 짧은 문자열보다 작은 부분 문자열들의 갯수를 구하는 문제였다.
간단하게 푸나? 싶었는데 런타임 에러가 발생했고
제한 사항을 뒤늦게 확인해보니 p의 길이가 18까지였다. 10의 18승이면…
아무튼 너무 큰수라서 int나 long으로는 감당할 수 없어서 런타임 에러가 발생했다고 생각했고
전에 사용해봤던 큰 숫자를 문자열로 큰수를 계산하는 방법이 떠올라서 사용했다.
using System;
public class Solution {
public int solution(string t, string p) {
// 숫자 문자열 t에서
// p와 길이가 같고 p보다 작거나 같은것의 횟수를 구해라.
// 시작점 ~ 길이
// ?? p의 최대길이가 18
// 그러면 10의 18승?? -> 문자열로 비교해야됨
int answer = 0;
int length = p.Length;
for(int i = 0; i<= t.Length - length; i++)
{
answer += CompareNumString(p, t.Substring(i, length)) ? 1 : 0;
}
return answer;
}
public bool CompareNumString(string a, string b)
{
for(int i =0; i< a.Length; i++)
{
if(a[i] < b[i])
{
return false;
}
else if(a[i] > b[i])
{
return true;
}
}
return true;
}
}
