분류 전체보기 (124) 썸네일형 리스트형 Codeforces R697 D3 solved 1 out of 7 서버 문제로인해 대회가 미뤄지기도하고 채점이 진행되지않아 B번까지 보다가 그냥 잤습니다. 너무 아쉽지만 A번을 특이하게 풀어서 기록을 남깁니다. A. Odd Divisor 주어진 정수 N이 홀수로 나눠지는지 확인하는 문제입니다. 다만 이때 N의 크기가 $10^{14}$임으로 $O\left ( N \right )$으로 찾아주면 안됩니다. N이 홀수면, N은 무조건 Odd Divisor를 갖는다는 점을 활용하여 문제를 해결할 수 있습니다. func(N) { if N=odd return true else if N=even func(n/2) } 이렇게 N을 절반씩 나눠주면 $O\left ( logN \right )$안에 문제를 풀 수 있습니다. bool chk(ll k) { if.. 스프링부트와 AWS로 혼자 구현하는 웹 서비스 1 P71 lombok lombok 기능 테스트 코드가 책에서 설정한 그대로 진행하여도 정상적으로 동작하지 않습니다. import static org.assertj.core.api.Assertions.assertThat; 이 부분에서 부터 assertThat이 정상적으로 import되지 않는 문제가 발생합니다. 따라서 당연히 assertThat method는 호출 불가합니다. 해결법 1. 오타 확인 static 등을 적지 않을 경우 정상동작하지 않습니다. 2. build.gradle에 dependencies 추가 testCompile "org.projectlombok:lombok" annotationProcessor('org.projectlombok:lombok') testAnnotationProcessor.. CF R696 D2 solved 2 out of 6 A. Puzzle From the Future 문제 태그에는 그리디라고 되어있는데 문제를 풀면서 증명은 생각 못했고 그냥 구현문제처럼 풀었습니다. 문자열 a의 첫 글자는 무조건 1로 시작하고, 그 이후로는 현재 보고있는 인덱스를 i라고 할때 d[i-1]과 a[i]+b[i]의 값을 계속 다르게 해줘서 해결해주면 됩니다. rep(i, b.length()) { int k = b[i]-'0'; if (i==0) a+='1'; else { int tmp = (a[i-1]-'0')+(b[i-1]-'0'); // d[i-1] if (tmp!=k+1) a+='1'; else a+='0'; } } B. Different Divisors 대회중에 계속 공지가 떠서 특이한 문제였다고 기억이 .. ABC 188 대회중에는 A,B번까지 풀었다 A,B 두 문제를 10분안에 해결해서 C번은 풀 줄 알았는데 도무지 풀이가 생각나질 않아서 못풀었다 A - Three-Point Shot 삼점 슛을 넣고 역전이 가능한지 묻는 문제이다 문제에 나온 그대로 구현하면 풀 수 있다 주어지는 두 팀 중 무조건 점수가 낮은팀을 A, 높은 팀을 B로 보는게 구현의 팁 B - Orthogonality 벡터의 곱을 하여 0이 되는지 묻는 문제이다 N이 10만이라 $O\left ( N^2 \right )$보다 빠르게 풀어야 하는데, 그냥 1부터 N까지 더해주면서 그 합이 0인지 아닌지 확인하면 풀린다 C - ABC Tournament 비트연산을 이용한 구현인줄 알았는데 전혀 아니었습니다 키 포인트는 어찌됐든 매치의 결과로 파이널리스트는 왼쪽.. BOJ 문제풀이2 1920 수찾기 주어진 배열 A를 정렬해두고 M개의 숫자가 그 안에 있으면 1 없으면 0을 출력해주면 됩니다 다만 N이 10만이라 $O\left ( N^2 \right )$이 아니라 $O\left ( NlogN \right )$안에 해결하기 위해 이분탐색을 이용해 수를 찾아줘야 합니다 if (binary_search(all(A), tmp)) cout BOJ 문제풀이 1 1182 부분수열의 합 N이 최대 20입니다 비트마스킹을 이용하여 가능한 모든 부분수열의 합을 본다 하더라도 $O\left ( N2^N \right )$입니다 20502 Gum색 게시글을 우선순위 순서대로 방문하면서 해당 게시글에 키워드가 있는지 확인하면 $O\left ( QNM \right )$해결 할 수 있습니다 1012 유기농 배추 Board[i][j]가 1이면서 아직 방문하지 않은곳을 시작으로 DFS를 돌면서 총 몇번 DFS가 호출되었는지 카운팅하면 됩니다 1463 1로 만들기 3가지 연산에 대해 dp를 돌려주면 해결 할 수 있습니다 다만 N이 100만이라 $O\left ( N \right )$안에 해결하기 위해 저는 bottom-up으로 풀었습니다 1915 가장 큰 정사각형 dp문제입니다 dp[.. BOJ 1202 보석도둑 매트로이드(matroid) 구조를 가진 그리디 문제입니다 보석은 비싼순서대로 가방은 가벼운 순서대로 정렬해두고, 가장 비싼 보석부터 담을 수 있는 가능한 작은 가방에 담아주면 해결 할 수 있습니다 다만 이때 $N$의 크기가 30만이라 $O\left ( N^2 \right )$으로는 TLE를 받습니다 따라서 N한개에 뒤에는 로그가 따라오는 정도로 문제를 풀어야합니다 저는 $O\left ( Nlog N \right )$안에 해결했습니다 하지만 이 부분에서 가방을 그냥 벡터에 넣고 lower_bound를 쓰면 TLE를 맞습니다(벡터을 이용한 구현) 가방을 multi_set에 넣고 bag.lower_bound를 사용해야 시간안에 동작합니다(set을 통한 구현) set이 random-access iterator를.. Goodbye 2020 대회 중 2솔을 했고, 업솔빙한 C까지 풀어보겠습니다 A. Bovine Dilemma 그냥 $\binom{n}{r}$인줄 알았는데, 삼각형의 넓이가 같으면 같은 삼각형으로 생각하기 때문에 이를 고려하여 문제를 해결해야합니다 저는 어차피 높이는 1로 고정되어있다는 지문의 내용을 바탕으로 밑변의 길이를 set에 넣어 몇개가 있는지 카운팅했습니다 B. Last minute enhancements 처음에는 set에 넣어 해결하려 했었는데, 마지막에 가장 큰 숫자가 있을 경우 정답보다 무조건 한개가 더 많아 질 수 있고, 이와 비슷한 맥락의 비슷한 경우가 많이 있어 대회중에 풀이를 바꾸었습니다 곡에 들어가있는 수를 trg로 두고 들어갈 숫자(A)와 비교하며 이 문제를 해결했습니다 if $(A+1==trg)$ co.. codeforces edu round 101 Codeforces round 691 D2 이전 1 ··· 8 9 10 11 12 13 다음
