분류 전체보기 (124) 썸네일형 리스트형 협성 알고리즘 동아리 알파벳 홈페이지가 배포되었습니다🎶 안녕하세요 블로그 주인입니다. 다름이아니라 드디어 학교 알고리즘 동아리 홈페이지가 배포되었습니다. 블로그에 소소하게 트래픽이 있는데 대부분 같은 학교 학우분들이라 생각되어 여기에 적습니다. 홈페이지는 여기에 있습니다. 아무래도 1인 개발이다 보니 능력이 부쳐 여러모로 부족한 점이 많지만 차차 개선해 나가겠습니다. P.S. FE는 여기 BE는 책 한권과 여러 웹사이트를 참조하여 만들었습니다. 어서 빨리 학교만의 여러 디자인과 특색을 더하고 싶네요🙂 codeforces R701 D2 solved: 0 out of 6 바로 어제 밤을 새서 스킵하려다 그냥 쳤는데 무려 0솔입니다 😅 따라서 업솔한 문제는 그때 그때 추가하겠습니다🙃 A. Add and Divide 그냥 수학문제입니다. 저는 대회중에 식은 다 뽑았는데 구현을 못하고 끝났습니다. 각각의 연산에 대해 k번 n번 했다고 했을 때, WLOG, $b = k$ 그리고 $a = \left \lfloor \frac{a}{b^n} \right \rfloor$ 따라서 이때 $min\left ( n+k \right ), a a) { ans=min(ans, i+j); break; } } } AtCoder ABC 191 solved: 2 out of 6 2문제를 10분안에 해결해서 기대 했었는데 역시나 C번에서 전을 구워버렸습니다. 주어진 다각형이 convex할때는 고려했지만 concave할 수도 있다는 사실을 고려못했는데 많은 사람들이 비슷한 실수를 한 것 같습니다. A - Vanishing Pitch 주어진 위치에서 공이 보이지 않는지 확인해주면 됩니다. B - Remove It 처음부터 입력을 받을 때, X와 다르면 입력을 받고 같으면 입력을 받지 않는 식으로 문제를 해결 할 수 있고 이는 $O\left ( N \right )$입니다. C - Digital Graffiti 에디토리얼이 올라오는대로 풀이를 추가하겠습니다 Codeforces R699 D2 solved: 1 out of 6 A번을 빠르게 해결하고 B번에서 전 굽다가 라운드가 끝났습니다. B번에서 중요한 관찰 2가지는 발견 했지만 문제를 해결 못했습니다. 개인적으로 너무 아쉬운 부분입니다. A. Space Navigation 단순한 구현문제로 문제에서 제시한 그대로를 구현하면 됩니다. B. New Colony 결국 돌이 최대 $\left (n-1 \right )\times \left ( max-1 \right )$개이며 이보다 크면 무조건 -1이라는 사실을 알 수 있습니다. 이때 max는 최대 100이고 n도 최대 100임으로, -1이 아닌 돌은 총 1만개까지라 구현으로 문제를 해결 할 수 있습니다. 왼쪽 산부터 돌을 굴려주면서 마지막 위치를 갱신해주고 만약 돌이 끝까지 굴러간다면 -1을 출.. BOJ 문제풀이 4(W20) dp로 상태를 정의하며 문제를 풀 때, 같은 패턴으로 항상 틀린다는 점을 발견했습니다. 서울에서 경산까지 문제의 경우(boj 14863) 1. me: k분 이하로 이동 가능하면 그때의 최대를 배열에 저장 아니라면 -INF를 리턴해주면 풀겠네! dp배열을 서울부터 i까지 j를 이용하여 이동했을때 최대로 모금한 금액이라 정의한다면 아래와 같은 식을 쉽게 얻을 수 있구나! $ \overset{\underset{\mathrm{}}{}}{dp\left ( i, j \right )=max\left ( dp\left ( i-1, j \right ), dp\left ( i-1, {j}' \right ) \right )}$ 2. 손풀이 다 하고 컴퓨터로 옮기는중... 뭔가 갖고있는 정보가 부족한걸 알아챔(이 문제의 경우.. AtCoder ABC 190 solved: 3 out of 6 C번까지 푸는데 30분이 안걸렸는데, D번 수학에서 막혔습니다. A - Very Very Primitive Game 둘이 같은 수의 캔디를 들고 있는 상황을 고려하면 쉽게 해결 할 수 있습니다. if (c==0) { if (a>b) cout 2월 계획 1. LIS를 세그먼트 트리 이용해 풀어보기 2. LIS 그리디 풀이 복습(이분탐색) 3. 문자열 문제 파이썬으로 풀기 4. SCC 복습 BOJ 문제풀이 3 15975 화살표 그리기 N이 최대 10만입니다. 따라서 각각의 좌표마다 가장 가까운 좌표를 찾아주면 $O\left ( N^2 \right )$으로 TLE입니다. 주어진 좌표를 색상별로 정렬을 하고 각각의 색상 안에서 가장 가까운 좌표를 찾아줘야합니다. 저는 그냥 색을 기준으로 정렬시키고 그 이후 좌우에 있는 좌표를 보면서 더 가까운 좌표까지의 거리를 모두 더해주니 AC를 받았습니다. 색상별로 정렬이후 같은색끼리는 좌표기준으로 정렬을 한번 더 해줘야 할 것 같은데 *왜 맞았는지 모르겠습니다. *pair를 sort해주면 first다음 second가 정렬되어 한번만 해주면 됩니다! 2042 구간 합 구하기 답이 long long인 것에 유의해야합니다. 전형적인 세그 트리 문제입니다. 쿼리당 $O\left (.. codeforces R698 D2 solved: 2 out of 6 A,B 두 문제를 40분이 안되는 시간안에 삽질 없이 해결하여(WA없이) 오늘 드디어 색을 바꾸는구나 했는데 C,D가 수학이라 좌절한 라운드입니다. C번은 오늘 자고 일어나서 다시 에디토리얼을 읽는데도 도통 이해가 가지 않아 우선 풀이를 보류합니다. A. Nezzar and Colorful Balls N이 정말 너무너무 작아서 $O\left ( N^2 \right )$풀이로 AC를 받았습니다. 길이 N짜리 배열을 돌면서 색을 그냥 칠해주면 됩니다. int n;read(n); int A[n]; rep(i, n) { int tmp;read(tmp); A[i]=tmp; } int painted[n]; fill(painted, painted+n, -1); int color = .. segment tree 세그먼트 트리는 어떤 범위에 대한 쿼리를 효율적으로 대답해 줄 수 있는, 또 그러면서 수정도 가능한 자료구조 중 하나입니다. 아래와 같은 쿼리 2개를 생각해 봅시다. 1. 길이가 N인 어떤 수열 A에서 A[i]부터 A[j]까지의 합을 구하라 2. 길이가 N인 어떤 수열 A에서 A[i]를 v로 바꿔라 일반적인 경우 이 두 쿼리는 $O\left ( N \right )$으로 해결 할 수 있습니다. 그런데 구간 트리를 이용하면 $O\left ( logN \right )$으로 쿼리를 해결 할 수 있습니다. 위 그림과 같이 각 노드가 구간을 커버하면서 구간에 해당하는 값을 가지고 있는 형태를 세그먼트 트리는 가지고 있습니다. 1번이 루트 노트이고 아래로 2,3번을 자식 노드로 갖는점에 유의해주세요! 세그 트리를 구.. 이전 1 ··· 7 8 9 10 11 12 13 다음
