오늘 공부한 내용 & 푼 주요 문제2467 - 용액(골드 5)https://www.acmicpc.net/problem/24672470 - 두 용액(골드 5)https://www.acmicpc.net/problem/2470용액 시리즈를 풀었다. 2470은 2467에다가 sort()만 해주면 되는 별 다른거 없는 문제. 투 포인터를 처음으로 써보았다. 세 용액은 어떻게 풀어야 될지 모르겠다... 15988 - 1, 2, 3 더하기 3(실버 2)https://www.acmicpc.net/problem/15988간단한 dp 문제. 순서가 다르면 다른 걸로 취급해줘서 쉽게 풀 수 있었다. 13909 - 창문 닫기(실버 5)https://www.acmicpc.net/problem/13909재밌는 문제. n까지의 창..

오늘 공부한 내용 & 푼 주요 문제15649 - N과 M(1)(실버 3)https://www.acmicpc.net/problem/1564915651 - N과 M(3)(실버 3)https://www.acmicpc.net/problem/1565115655 - N과 M(6)(실버 3)https://www.acmicpc.net/problem/1565515656 - N과 M(7)(실버 3)https://www.acmicpc.net/problem/1565615657 - N과 M(8)(실버 3)https://www.acmicpc.net/problem/1565715663 - N과 M(9)(실버 2)https://www.acmicpc.net/problem/15663n과 m 시리즈를 밀어봤다. 백트래킹이 잘 구현이 안 되..

오늘 공부한 내용 & 푼 주요 문제...너무 바빠서 공부할 틈이 없었다!오늘 푼 잔여 문제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우선순위 큐를 구현하는 문제... 이나 몇번의 시도 끝에 그냥 모듈 쓰기로 했다...  구글링 없이도..