전체 글 (349) 썸네일형 리스트형 백준 2216 - 문자열과 점수 icpc.me/2216 Solution. 다음 점화식을 고려하여 탑 다운 dp로 푼다. dp[i][j] := 첫번째 문자열을 i개, 두번째 문자열을 j개 썼을 때 얻을 수 있는 최대 점수 이때 테이블의 초기화는 값이 겹치는 걸 방지하기 위해 아주 큰 값이나 아주 작은 값으로 초기화 한다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include #include #include #include using namespace std; int dp[300.. 백준 1513 - 경로 찾기 icpc.me/1513 제약이 까다로워 애를 먹었던 dp 문제이다. 오락실의 방문 순서는 순증가여야 한다는 점과 오락실은 출발점과 도착점에도 존재할 수 있다는 것이 문제를 어렵게 만든다. 다만 도시의 크기는 50 * 50이기 때문에 메모리를 넉넉하게 사용할 수 있다. 제약을 고려하여 사차원 테이블에 다음 점화식을 세울 수 있다. f(row,column,last,cnt)= row 행 column 열에서 마지막으로 방문한 오락실의 순서 번호가 last일 때 남은 오락실 방문 가능 횟수 cnt map을 사용하여 오락실의 순서 번호를 저장한 뒤, 점화식으로 탑 다운 dp를 돌리면서 cnt번의 방문으로 학교에 도착할 수 없거나 방문했었던 오락실보다 순서 번호가 더 낮은 오락실에 방문하.. 페르마의 소정리를 활용한 알고리즘 문제 풀기 이 게시글에서는 페르마의 소정리를 간략하게 배우고 관련 알고리즘 문제를 푼다. 정수 a와 p가 있고 a가 p의 배수가 아니면서 p가 소수(Prime number)일 때 다음이 성립한다. a^{p} \equiv a (\mod p) 여기서 \equiv 는 합동을 의미하는 기호인데 a^{p}를 p로 나눈 나머지는 a를 p로 나눈 나머지와 같다는 뜻이다. 또한 여기서 양변에 a를 나누는 것으로 다음 두 식을 유도할 수 있다. a^{p - 1} \equiv 1 \; (\mod \; p) a^{p - 2} \equiv a^{-1} \; (\mod \; p) 페르마의 소정리에 대해 알았으니 이를 이용하는 문제를 하나 풀어보자. icpc.me/16134 16134번: 조합 (Combinat.. [ICPC] 백준 2159 - 케익 배달 icpc.me/2159 N명의 고객의 위치가 이차원 평면 좌표로 주어지며 그 좌표 (r, c)는 0 \leq r, c \leq 100000 의 범위를 가지고 있다. 좌표의 범위가 너무나도 크기에, 선아가 배달을 하러 갈 수 있는 지역을 이차원 배열로 나타낼 수 없고 빵을 받는 고객은 자기 위치와 상 하 좌 우 한칸 떨어진 곳까지 케익을 수령할 수 있다. 또한 고객들이 주문한 순서대로 받길 원한다. 이를 통해 선아는 i번째 고객까지 배달을 했으면 무조건 i + 1번째 고객에게 가야되며 i + 1번째 고객에게 케익을 배달할 수 있는 좌표는 갈 수 없는 곳을 제외해 최대 5개가 된다고 정리할 수 있다. 즉, 선아는 다음 고객으로 갈 때 최대 5개의 좌표만 고려하면 된다. 따라서 가능한 좌표를 배열이나 벡터.. 기본적인 소수 판별 알고리즘 2가지 소수가 자기 자신과 1만을 약수로 가진다는 것은 널리 알려진 사실이다. 알고리즘 문제를 풀 때 어떤 수가 소수인지 아닌지 판별할 상황이 오는데 그 수가 너무 크지만 않다면 게시글에서 알려줄 두가지 방법을 이용하여 적절히 해결할 수 있다. 판별법 1. 완전 탐색을 통한 검사 자연수 N이 소수인지 아닌지 판별하는 가장 간단한 방법은 2부터 \sqrt[]{N} 까지 나눠보면서 나눠지는지 아닌지 확인하는 것이다. 왜 모든 수를 나눠보는게 아니라 제곱근으로도 충분할까? N이 합성수라고 한다면 N은 N = ab = ba처럼 두 자연수 a, b의 곱으로 나타낼 수 있다. 이 때 a와 b는 2 \leq a \leq \sqrt[]{N}, \; \sqrt[]{N} \leq b \leq \frac{N}{2} 또는.. 이전 1 ··· 55 56 57 58 59 60 61 ··· 70 다음 58/70
