오늘 공부한 내용 & 푼 주요 문제...너무 바빠서 공부할 틈이 없었다!오늘 푼 잔여 문제4문제 풀었다.현황레이팅: 1230 -> 1231(+1)푼 문제 수: 492 -> 496(+4)

오늘 공부한 내용 & 푼 주요 문제에라토스테네스의 체 & 유클리드 알고리즘에 대해 공부했다. 다른 문제를 풀면서 정수론이 생각보다 많이 사용된다 느꼈고, 이를 보완하기 위해 이틀 정도 더 공부할 예정이다. 4948 - 베르트랑 공준(실버 2)https://www.acmicpc.net/problem/4948에라토스테네스의 체를 이용해주면 되는 단순한 문제. 2981 - 검문(골드 4)https://www.acmicpc.net/problem/2981유클리드 호제법을 사용해주면 되는 문제. n으로 나눈 나머지가 같을때 뺀 값이 n의 배수라는 점을 잘 이용하면 된다. 오늘 푼 잔여 문제17문제 풀었다.현황레이팅: 1210 -> 1230(+20)푼 문제 수:473 -> 492(+19)

유클리드 알고리즘이란 정수 a와 b의 최대공약수 gcd(a,b)를 효율적으로 계산하는 방법이다.다음과 같은 공식을 기반으로 한다.def gcd(a,b): if(b==0): return a #만약 b가 0이라면 a=최대공약수 return gcd(b,a%b) #b와 a를 b로 나눈 나머지의 최대공약수이 알고리즘이 올바르게 작동하는 이유는 최대공약수 x는 a와 b 모두의 약수이기 때문에 a mod b의 약수이기도 하기 때문이다.이 알고리즘을 이용하여 시간복잡도를 O(log n)까지 줄일 수 있다. 이를 이용한 연습문제를 하나 풀어보고 마치겠다. 2981 - 검문(골드 4)https://www.acmicpc.net/problem/2981n개의 수가 주어졌을때 이 수들을 나누었을때 나머지가 모두 같은 ..

에라토스테네스의 체(sieve of Eratosthenes)는 2이상 n 이하의 정수 x가 소수인지 판별하는 알고리즘이다.다음은 n=10일때의 작동원리이다.2부터 시작하여 새로운 소수 x를 발견할 때마다 2x,3x,4x...를 소수가 아니라 체크한다.이러한 과정을 통해 시간 복잡도를 O(n log log n)까지 줄일 수 있다. 또한 이를 최적화 할 수 있는 방법이 몇가지 있다.1.새로운 소수 x를 발견할때마다 2x,3x,4x...를 소수가 아니라 체크하므로 x^2이 n보다 작을 때 까지만 실행하면 된다.2.새로운 소수 x를 발견하면, x부터 시작하는 것이 아닌 x^2부터 시작하면 된다. 이유는 그 사이값들은 이미 x보다 작은 소수들에 의해 체크되었기 때문이다. 이를 이용하여 간단한 백준 문제를 연습해보..

오늘 공부한 내용 & 푼 주요 문제9251 - LCS(골드 5)(업로드됨)https://www.acmicpc.net/problem/9251어제 기록을 남기고 새벽에 고민 끝에 푼 문제. dp를 사용해서 풀면 된다. 이 문제를 마지막으로 클래스 4 20문제를 달성했다! 2133 - 타일 채우기(골드 4)https://www.acmicpc.net/problem/2133이 또한 dp를 사용하는 유명한 문제. 내일 이어서 타일 채우기 2,3,4도 풀어보려 한다. 26099 - 설탕 배달2(실버 4)https://www.acmicpc.net/problem/26099그리디 알고리즘을 사용하는 간단한 문제. 설탕 배달 1 코드를 잘 짜놔서 그대로 제출했더니 풀렸다.오늘 푼 잔여 문제14문제 풀었다.현황레이팅: 114..

문제:https://www.acmicpc.net/problem/9251난이도: 골드 5 LCS(Longest Common Subsequence, 최장 공통 부분 수열)를 찾으면 되는 문제이다. DP를 쓰는 방법에 있어서 꽤 애를 먹었다.아이디어1처음 생각했던 풀이는 배낭 문제에서 영감을 얻어 두 번째 리스트에서 각 문자열마다 가질 수 있는 최장 부분 문자열을 저장해주는 것이었다. 이중 for문을 사용해서 같은 문자열이 나오면 그 전 값 중에서 최댓값을 찾아 +1 해주는 식으로 코드를 짜봤다. 아래는 모식도이다.입력:ACAYKPCAPCAK시도1n=input()m=input()l=[0]*len(n)for i in n: t=l[:] for j in range(len(m)): if i==..

오늘 공부한 내용 & 푼 주요 문제11444 - 피보나치 수 6(골드 2)https://www.acmicpc.net/problem/114442749 - 피보나치 수 3(골드 2)https://www.acmicpc.net/problem/2749피보나치 수를 구하는 간단한 문제. 분할 정복 연습하는데 딱 좋은 문제였다. 1927 - 최소 힙(실버 2)https://www.acmicpc.net/problem/192711279 - 최대 힙(실버 2)https://www.acmicpc.net/problem/1127911286 - 절댓값 힙(실버 1)https://www.acmicpc.net/problem/11286우선순위 큐를 구현하는 문제... 이나 몇번의 시도 끝에 그냥 모듈 쓰기로 했다...  구글링 없이도..

문제:https://www.acmicpc.net/problem/11444난이도: 골드 2단순히 피보나치 수를 구하는 문제. 다만 n이 무지막지하게 큰.아이디어 1처음에는 분할 정복을 어떻게 쓸지 생각이 안 떠올랐다. 그렇게 고민을 하다가 피보나치 수를 직접 나눠서 써보기로 하였다.우선 n이 짝수일 때이다. n=2k일 때 k번째 항까지 분할을 하였다.f(10)을 예시로 들어봤다. 2개로 계속해서 나누었을 때 항의 개수가 피보나치수열을 이루는 것을 알 수 있다. n/2까지 과정을 반복해 보면 다음과 같은 식을 얻을 수 있다.다음은 n이 홀수 일 때다.n=k//2+1이라 할 때 k번째 항까지 분할하였다. 일반항으로 나타내면 다음과 같다.나도 왜 이런 식이 나오는지는 모른다. 2시간 정도 노트에다가 끄적여보며 ..

오늘 공부한 내용 & 푼 주요 문제1629 - 곱셈(실버 1)https://www.acmicpc.net/problem/1629오랫동안 이해하지 못했던 문제. 책을 보고 그제서야 이해하고 풀었다. 분할 정복이라는게 뭔가 쉬우면서도 어려운거같다. 12865 - 평범한 배낭(골드 5)(업로드됨)https://www.acmicpc.net/problem/12865주어진 무게의 최솟값을 맞추며 가치를 최대로 이끌어내는 문제. 이 또한 문제점을 오랫동안 찾지 못했던 문제이다. 내 풀이가 dp인줄 알았으나 완전 탐색이어서 dp의 형태로 변형하여 풀이를 이끌어냈다. dp의 개념을 잘못 알고 있었던거 같기도 하다. 15654 - N과 M (5)(실버 3)https://www.acmicpc.net/problem/15654백..