본문 바로가기
반응형

코딩테스트 준비/백준 C#161

백준 C# - 1676 +) 풀이 서론 처음에 풀때 팩토리얼 계산을 이용해서 풀었다. 효율적이지 않은 것 같아서 인터넷을 찾아보니 5와 2의 소인수분해로 풀어야 된다는 것을 알게되었다. 풀이 5의 개수를 구하자 0이 생기는 경우는 5와 2가 곱해진 10이 존재하는 경우이다. 따라서 5와 2의 갯수를 구해야 한다. 팩토리얼 특성상 5가 있으면 2가 존재하므로 5의 갯수만 구하면 된다. while (n >= 5) { zeroCount += n / 5; n /= 5; } 예를 들어서 10이면 10/5이므로 2개 된다. 25이면 25/5이므로 5개에서 반복문을 한 번 더 돌아서 5/5 1개가 또 더해져서 6이 된다. 코드 전문 using System; namespace baek2 { class Program { static void Main(s.. 2023. 11. 5.
백준 C# - 10872 +) 풀이 풀이 재귀함수를 이용해서 팩토리얼을 풀면 된다. static int factorial(int n) { if (n 2023. 11. 5.
백준 C# - 6588 +) 풀이 문제를 풀기 앞서 아래 문제를 먼저 푸는 것을 추천한다. 백준 C# - 1929 백준 C# - 1929 +) 에라토스테네스의 체 풀이 처음에 1978과 같은 형식으로 문제를 풀었는데 계속 시간초과가 나왔다. 백준 C# - 1978 +) 풀이 풀이 소수 찾기 문제이다. 소수는 1과 자기 자신 만을 약수로 가지는 수이다. 01 1은 소수가 아니 code-piggy.tistory.com 풀이 01 에라토스테네스의 체 알고리즘 사용 상세 설명은 위의 문제에서 확인 StringBuilder sb = new StringBuilder(); int num = -1; bool[] isPrime = Enumerable.Repeat(true, 1000000 + 1).ToArray(); int[] prime = new int.. 2023. 11. 5.
백준 C# - 1929 +) 에라토스테네스의 체 풀이 처음에 1978과 같은 형식으로 문제를 풀었는데 계속 시간초과가 나왔다. 백준 C# - 1978 +) 풀이 풀이 소수 찾기 문제이다. 소수는 1과 자기 자신 만을 약수로 가지는 수이다. 01 1은 소수가 아니므로 제외 if(int.Parse(token[i]) == 1) { answer--; continue; } 2) 나머지가 0이 나오면 소수가 아니므로 0이 나 code-piggy.tistory.com 위의 방식대로하게 된다면 시간 복잡도는 O(N²)이다. 두 반복문에서의 모든 i에 대해 모든 j값으로 나눗셈을 진행하므로 N * N이므로 O(N²)이 된다. 시간초과가 뜬다. 에라토스테네스의 체를 사용해야 한다. 왜 사용해야하는가? 임의의 자연수 n에 대하여 그 이하의 소수를 찾는데 제일 효율적인 방.. 2023. 10. 31.
백준 C# - 1978 +) 풀이 풀이 소수 찾기 문제이다. 소수는 1과 자기 자신 만을 약수로 가지는 수이다. 01 1은 소수가 아니므로 제외 if(int.Parse(token[i]) == 1) { answer--; continue; } 2) 나머지가 0이 나오면 소수가 아니므로 0이 나오는 수는 제외 if (int.Parse(token[i]) % j == 0) { answer--; break; } 코드 전문 using System; namespace baek2 { class Program { static void Main(string[] args) { int num = int.Parse(Console.ReadLine()); string word = Console.ReadLine(); string[] token = word.Split(.. 2023. 10. 31.
백준 C# - 1934 최대공배수, 최소공약수 설명 알아보러가기 백준 C# - 2609 +) 풀이 풀이 01 최대 공약수 for(int i = 1; i code-piggy.tistory.com 코드 전문 using System; namespace baek2 { class Program { static void Main(string[] args) { int num = int.Parse(Console.ReadLine()); while (num > 0) { string word = Console.ReadLine(); string[] token = word.Split(); int A = int.Parse(token[0]); int B = int.Parse(token[1]); int index = 1; int n = 0; if (A <.. 2023. 10. 31.
반응형

티스토리툴바