코딩테스트/백준 9

[1735] 분수 합(C#)

알고리즘 : 유클리드 호제법 난이도 : Silver Ⅲ 유클리드 호제법을 활용하여 푸는 문제. 유클리드 호제법(Division algorithm) 이란? 주로 큰 두 수의 최대공약수를 파악하기 힘든 경우에 먼저 '큰 수'를 '작은 수'로 나눈 나머지를 구한 뒤 '나눴던 수'를 그 '나머지'로 나누는 과정을 되풀이하여 최종적으로 나머지가 0이 될 때 마지막 계산에서 나누는 수로서 최대공약수를 얻을 수 있다. 예를 들면 아래와 같다. string[] strFirstFraction = Console.ReadLine().Split(' '); string[] srtSecondFraction = Console.ReadLine().Split(' '); int[] firstFraction = Array.ConvertA..

[1676] 팩토리얼 0의 개수(C#)

알고리즘 : 구현 난이도 : Silver Ⅴ 규칙을 찾아내어야 하는 문제. 팩토리얼 연산을 수행하다 보면 0의 개수에 대한 규칙이 보인다. 처음에는 5의 배수만큼 0가 증가하는 것으로 판단했는데, 25쯤 가니까 갑자기 0이 추가로 증가하는 것을 보고서 단순 5의 배수가 아니라는 것을 알게됐다. (25!에서는 0가 6개..) 알고보니 10의 개수로 세는거였다. 그런데 이 때 10 = 2 * 5 이므로 5의 개수를 세면 된다고 착각할 수 있었는데, 음.. 비슷하다. 5의 등장 횟수보다 2의 등장 횟수가 더 많으므로. 그러나 25의 경우에는 5 * 5 이므로, 여기에 2를 두 번 곱하여 10을 만들 수 있기 때문에 10이 한번에 두번 등장하는 것과 동일하게 볼 수 있다.(일타쌍피!) 그러니까 25!을 살펴보면..

[1459] 걷기(C#)

세준이가 집에 가기까지 걸리는 최소시간을 구하는 문제. 처음에는 복잡하게 생각했다. 경우의 수를 나누어 하나의 값만 도출되게 했는데, 가지수를 크게 나누어 min값을 출력하면 된다. 나는 대각선으로 최대한 이동할 수 있는 만큼 이동 후 수평이동 조건을 생각하지 못해서 예제입력 6번이 제대로 재현이 안 되는 난관을 겪었다...🥺 난.. 언제쯤.. 알고리즘 : 많은 조건 분기 난이도 : 실버 Ⅴ 정답 비율 : 26.248% string[] inputs = Console.ReadLine().Split(' '); long X = long.Parse(inputs[0]); long Y = long.Parse(inputs[1]); int costofline = int.Parse(inputs[2]); int costo..

[1333] 부재중 전화(C#)

문제 이해하는데 좀 걸렸다. (어휘력을 길러야될 것 같음....😒 책 읽어야 돼 책) 결과적으로는 단순풀이법으로 아래와 같이 풀이를 했는데. 이 때 while 구문에서 if로 풀이하면 안 된다. 아래와 같은 Testcase의 경우에는 fail이 나기 때문. "1곡 재생, 한 곡당 7초 길이, 2초마다 벨이 울릴 경우" 알고리즘 : 단순 구현, 시뮬레이션 string[] NLD = Console.ReadLine().Split(' '); int N = int.Parse(NLD[0]); int L = int.Parse(NLD[1]); int D = int.Parse(NLD[2]); // 침묵의 구간 int[] fadeRange = { L, L + 5 }; // 벨이 울리는 시간(초) int secOfLastR..

[2748] 피보나치 수 2(C#)

N번째 피보나치 수를 구하는 문제. N은 자연수 90이하의 수로서 핵심은 피보나치 수를 계산할 때 자료형을 int가 아닌 long으로 받아야 한다는 것이다. 알고리즘 : Dynamic Programming 시간복잡도 : O(N) int N = int.Parse(Console.ReadLine()); // N은 90이하의 자연수이다. // int형으로 받으면 범위초과로 제대로 된 답을 얻을 수 없다. List fibo2 = new List(); fibo2.Add(0); fibo2.Add(1); for (int i = 2; i 1) fibo2.Add(fibo2[i-1] + fibo2[i-2]); Console.WriteLine(fibo2[N]); 다른 ..

[10989] 수 정렬하기3(C#)

10,000보다 작거나 같은 수를 최대 천만번 input을 받아서 정렬하는 문제로 Sorting과 관련한 내장함수로는 통과 조건을 만족할 수 없다. 천만번 input을 받는 대신에 그 값의 범위가 좁은 편이기 때문에 이럴때는 계수정렬 알고리즘을 활용한다. 계수정렬(Counting Sort)? 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정하고 각 배열의 값으로는 데이터가 등장한 횟수를 세어 입력 시간복잡도 : O(N) int N = int.Parse(Console.ReadLine()); int[] arrInt = new int[10001]; for (int i = 0; i < N; i++) { int intThisInput = int.Pars..

[18014] 나이순 정렬(C#)

단순 Sorting방식으로만 정렬해봤다면 고개를 갸우뚱 할 수 있는 문제. 제한시간 : 15mins 시간복잡도 : O(NlogN) var varN = Console.ReadLine(); int intN = varN == null ? 0 : int.Parse(varN); // Map형식으로 접근 시 input에서 키중복이 있을 수 있으니까, Tuple로 접근한다. List tList = new List(); for (int i = 0; i < intN; i++) { var vartmp = Console.ReadLine(); string strTmp = vartmp == null ? "" : vartmp; string[] arrstrTmp = strTmp.Split(' '); // 아래와 같이 Tuple.C..

[2750] 수 정렬하기(C#)

정렬 문제 중 가장 기본. 소요시간 : 8mins 30secs 시간복잡도 : O(NlogN) 나는 List의 기본 내장함수인 Sort()를 사용했기 때문에 시간복잡도 O(NlogN)을 가지지만, 중첩 for문을 활용하여 선택정렬로 구현할 경우 O(N^2)의 시간복잡도를 가지게 된다. var varN = Console.ReadLine(); int intN = varN == null ? 0 : int.Parse(varN); List intList = new List(); for (int i = 0; i < intN; i++) { var varTmp = Console.ReadLine(); int intTmp = varTmp == null ? 0 : int.Parse(varTmp); intList.Add(int..

728x90
반응형