분류 전체보기
-
백준 1915(가장 큰 정사각형)전공/알고리즘 2020. 12. 15. 17:28
www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 이 문제도 Rebro님이 추천해주신 문제 10109 Troyangles랑 비슷한 유형의 2차원 dp문제이다. dp가 된다는 것을 알면 이제 남은건 간단하다 dp가 되는 규칙찾기 이 문제는 i,j가 정사각형의 맨왼쪽위로 설정한뒤에 앞선 문제와 동일한 방식으로 dp 테이블을 채워 나가면 된다. dp[i][j] = min(dp[i+1][j+1], dp[i+1][j], dp[i][j+1]) +1 #include #include using namespace std; #define MAX 1..
-
백준 10109(Troyangles)전공/알고리즘 2020. 12. 15. 17:19
www.acmicpc.net/problem/10109 10109번: Troyangles Troy loves triangles. He especially likes counting triangles. He has an N-by-N grid consisting of either “.” or “#” characters. Help him count the number of triangles formed only by “#” characters in the grid. Triangles are of the form # # ### www.acmicpc.net Rebro님이 최근 코포와 동일한 문제가 있다고 해서 풀어보았다. * *** 이런식의 좌우 대칭이면서 i번째 높이에는 2i-1 갯수의 별이 존재하는 트리의 갯수..
-
#689 div2 12/11대회/코드포스 2020. 12. 14. 19:15
codeforces.com/contest/1461 Dashboard - Codeforces Round #689 (Div. 2, based on Zed Code Competition) - Codeforces codeforces.com 요 근래 집에 있다보니 문제를 안 푼지 거의 3주가 된것 같다. 그래서 코포를 볼까 말까 하다가 걍 보자 싶어서 보게 되었다. A 진짜 문제가 무슨소린지 이해하기가 힘들었다. substring의 개념을 subsequence 랑 헷갈려서 더 그랬던것같고 펠린드롬이 aa가 길이 2, aaa가 길이 3, 순간적으로 이런식으로 이해해서 이상한 답을 출력하는 코드를 제출해서 pretest 1에서 WA가 뜨고 다시 확인하여서 제출하였다. 14분 솔브 B 이건 진짜 div2B라고 계속 생..
-
백준 13430(합 구하기)전공/알고리즘 2020. 12. 8. 20:08
www.acmicpc.net/problem/13430 13430번: 합 구하기 첫째 줄에 k와 n이 주어진다. (1 ≤ k ≤ 50, 1 ≤ n ≤ 1,000,000,000) www.acmicpc.net 행렬의 점화식을 이용한 문제이다. 문제에 행렬의 점화식을 이용해서 풀라 이런 문구는 없어서 풀이방법을 찾아내기 어렵겠지만 아마도 이런 점화식이 주어진 문제를 보면 또 N이 엄청나게 큰 문제를 보면 행렬의 점화식을 떠올릴 수 있을 것 같기도 한 문제였다. 먼저 우리에게는 점화식이 주어진다. S(0,N) = N S(K,N) = S(K-1, 1) + ... + S(K-1, N) 여기서 내가 짚고 넘어갈 것은 N의 범위가 10억까지이다. 따라서 N은 엄청나게 크고, O(N)의 풀이는 안되고, O(logN)같은 ..
-
#688 div2 12/04대회/코드포스 2020. 12. 5. 20:59
codeforces.com/contest/1453 Dashboard - Codeforces Round #688 (Div. 2) - Codeforces codeforces.com A 1초에 1씩 움직이고, 축에서 동시에 출발할때, 부딪히는 기차의 갯수를 구하는 문제이다. 문제가 진짜 길어서 문제 읽는데에 오래걸렸는데, 그림보고 예시 보니깐 축에서의 값이 같을때 부딪치는 기차가 된다 5분 솔브 B 이것도 문제가 이해하기 살짝 어려웠다. suffix라는 단어를 일단 검색해보았고, 예시로 이해를 했다 어떤 인덱스를 선택, 그 인덱스부터 뒤에를 1 더하거나 1 빼는 연산을 하여서, 최소연산으로 모든 원소를 같게 만드는 문제이다. 아 그런데 그냥 연산을 하는 문제가 아니라 내가 일단 어떤 원소를 같은 배열에 있는 ..
-
Educational 99 div2 11/30대회/코드포스 2020. 12. 1. 16:08
codeforces.com/contest/1455 Dashboard - Educational Codeforces Round 99 (Rated for Div. 2) - Codeforces codeforces.com 처음으로 4솔을 해봤다. 운동도 쉬고, 컨디션도 좋게 만들어놓고 코포를 기다렸는데 그래서 그런지 A부터 집중이 잘 되었다. A 수를 받고, 뒤집고, 처음에 있는 0들을 제거 한 함수를 f(x)라고 한다 어떤 범위 안에 값에서 x/f(f(x)) 값의 갯수를 구하는 문제인데, 대충 보니깐 자릿수랑 상관이 있었다. 그래서 그냥 예시에 나온거 세보니깐 자릿수 맞는것 같아서 제출 4분 솔브 B 아무리 생각해도 div2B인데 분명 쉬울텐데 왜 bfs로 풀 수 있는 문제가 나올까 했다. 짤수는 있겠지만 시간..
-
#603 div2 virtual 11/28대회/코드포스 2020. 11. 30. 15:11
codeforces.com/contest/1263 Dashboard - Codeforces Round #603 (Div. 2) - Codeforces codeforces.com 두번쨰 버츄얼 hwon233님과 같이 돌았다. 일요일에 그니깐 어제 코포가 있었는데 학회 종강총회때문에 못할것 같아서 11시에 버츄얼을 돌았는데,, 너무 피곤했다 진짜로 피곤해서 머리가 전혀 안돌아가는 기분을 느끼고 C까지 푼후에 바로 던졌는데 기억이 잘 안난다. 그래서 후기는 대충 이렇게 쓰고 오늘 11시 35분에 또 에듀코포 있는데 그거나 좀 잘 쳐보자 오늘은 운동안하고 해야겠다 왤케 피곤한지
-
백준 2749 피보나치 수 3(피사노 주기)전공/알고리즘 2020. 11. 28. 12:58
www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net blog.naver.com/PostView.nhn?blogId=richard0326&logNo=221142014183&categoryNo=83&parentCategoryNo=0&viewDate=¤tPage=1&postListTopCurrentPage=1&from=postView 피사노 주기(Pisano Period) 1) 설명 피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 됩니다. 이를 피사노 주기(Pisano Period... blog.naver.com 피보나치 수를 임의..