티스토리

BaaaaaaaarkingDog

검색하기

블로그 홈

BaaaaaaaarkingDog

blog.encrypted.gg/m

BaaaaaaaaaaaaaaaaaaaaaaarkingDog 님의 블로그입니다.

구독자: 69

방명록 방문하기

주요 글 목록

[BOJ] 9466번: Term Project 유튜브 링크 https://www.youtube.com/watch?v=yPuow6aACvE 문제의 첫 번째 예시는 그림으로 나타내면 이렇습니다. 화살표는 함께하고 싶은 학생을 향해 뻗어갑니다. 이 그림은 조금 알아보기 힘듭니다. 그림을 조금 바꿔보겠습니다. 이렇게 그래프로 나타내면 훨씬 더 직관적으로 알아보기 편합니다. 문제에서 --- 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다. --- 라고 설명이 되어있는 부분은 이 그림에서 (3) 혹은 (6 4 7)로 이루어진 사이클을 의미합니다. 사이클에 포함되지 않은 2, 1.. 공감수 14 댓글수 7 2021. 7. 21.
[BOJ] 2135번: String Compression www.acmicpc.net/problem/2135 보고 DP로 접근해야겠다는 생각이 쉽게 드는데, 일단 D[i][j]를 s[i:j]의 최소 길이라고 하겠습니다. 그러면 s[i:j] 구간은 어떤 적절한 부분문자열을 여러번 써서 만들어지거나(ex : abcabc=abc*2, gogogo=go*3), 아니면 중간에서 잘라 따로 따로 계산이 가능합니다. 즉 sep = i+1 to j에 대해 min(d[i][sep]+d[sep][j])를 계산하고 div = j-i의 진약수에 대해 min(2+d[st][st+div]+반복되는 횟수의 자리수)입니다. 2는 괄호 (와 )를 의미합니다. 코드를 참고해보세요. github.com/encrypted-def/BOJ/blob/master/2135.py 공감수 1 댓글수 3 2020. 12. 29.
[BOJ] 19235번: 모노미노도미노 www.acmicpc.net/problem/19235 곧이곧대로 짜면 되는데 최대한 코드를 예쁘게 만들려고 노력했습니다,, add_block 함수는 블록을 단순히 넣기만 하는 함수이고 add 함수에서는 한 줄이 꽉 찼을 때 / 0, 1행이 찼을 떄의 처리까지 포함되어 있습니다. 파란색 보드를 90도 돌려 초록색 보드와 동일한 로직으로 생각했고 vector를 이용해서 코드를 조금 더 편하게 만들었습니다. https://github.com/encrypted-def/BOJ/blob/master/19235.cpp 공감수 3 댓글수 2 2020. 10. 10.
[BOJ] 4889번: Seinfeld https://www.acmicpc.net/problem/4889 (면 +1, )면 -1을 하는 cnt 값을 계속 가지고 있습니다. cnt가 음수가 되면 그 순간의 )를 (으로 바꿔주고, 다 끝난 후의 cnt값을 확인해 cnt/2개의 (를 )으로 변환해주면 됩니다. https://github.com/blisstoner/BOJ/blob/master/4889.cpp 공감수 0 댓글수 0 2020. 3. 19.
[BOJ] 3078번: MALCOLM https://www.acmicpc.net/problem/3078 길이별로 인덱스를 모아둔 후에 two pointer로 하면 $O(20N)$에, 이분탐색으로 하면 $O(20NlgN)$에 해결 가능합니다. https://github.com/blisstoner/BOJ/blob/master/3078.cpp 공감수 0 댓글수 0 2020. 2. 28.
[BOJ] 14862번: 최대공약수 기댓값 https://www.acmicpc.net/problem/14862 맨 처음에는 prob1[i]를 gcd가 i의 배수일 확률($PQ^{-1}$), prob2[i]를 gcd가 i일 확률로 두고 $O(200000lg200000TK)$로 구했으나 시간초과가 발생했습니다. 그래서 mobius function을 통해 각 prob1[i]에 얼마가 곱해져야 하는지를 전처리로 계산해서 $O(200000lg200000 + 200000TK)$로 코드를 짜서 아주 간신히 통과됐습니다. 일단 $200000TK$가 왜 1.9초 가까이 걸리는지도 조금 의아하고, 수행시간이 아주 빠른 분들 코드를 봤는데 보고 나서도 오리무중이네요. https://github.com/blisstoner/BOJ/blob/master/14862.cpp 공감수 0 댓글수 4 2020. 2. 28.
[BOJ] 16409번: Coprime Integers https://www.acmicpc.net/problem/16409 Mobius number를 사용해서 해결할 수도 있고, 이 문제에서 사용한 것과 비슷한 테크닉으로 해결할 수도 있습니다. 저는 후자로 했지만 전자가 시간복잡도 상으로 더 우수합니다. https://github.com/blisstoner/BOJ/blob/master/16409.cpp 공감수 0 댓글수 0 2020. 2. 25.
[BOJ] 8291번: Coprime Numbers https://www.acmicpc.net/problem/8291 보고 나름대로 고민을 해서 얻은 생각은 square free number를 구해서 어찌저찌 하는건가 했는데 잘 감이 안왔고, JUNSEO님이 올리신 글을 보고나서 깨달음을 얻었습니다,,, ㄴㅇㄱ https://github.com/blisstoner/BOJ/blob/master/8291.cpp 공감수 0 댓글수 0 2020. 2. 25.
[BOJ] 12107번: 약수 지우기 게임 1 https://www.acmicpc.net/problem/12107 수 1이 이 게임에서 어떤 의미를 가지게 되는지 생각해보면 도움이 될 것입니다. https://github.com/blisstoner/BOJ/blob/master/12107.py 공감수 0 댓글수 0 2020. 2. 18.
[BOJ] 13318번: 위험한 해싱 https://www.acmicpc.net/problem/13318 LLL 알고리즘을 통해 충돌쌍을 알아낼 수 있습니다. 여기를 참고하세요. 아래 코드는 충돌쌍을 구해주는 sage 코드입니다. p = [29, 31, 37, 41, 43, 47, 53, 59, 61, 67] m = 10**9+7 N = 80 def sparse_poly(): L_rows = [] B = 10000000 for i in xrange(N): row = [1 if j==i else 0 for j in xrange(N)] for j in range(10): row.append(B*Integer(pow(p[j],i,m))) L_rows.append(row) L_matrix = Matrix(L_rows) L_redux = L_matr.. 공감수 0 댓글수 0 2020. 2. 1.
[BOJ] 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 https://www.acmicpc.net/problem/16977 톡방에서 계속 얘기가 나오길래 뭔가 싶어서 풀어봤습니다. 어떻게 한번에 맞춘건가 신기할 정도로 구현이 끔찍하게 까다로웠습니다. 일단 주어진 문제를 결정 문제로 만들어 parametric search가 가능하다는 사실을 알아내야 하고, 각 쿼리에 대해 작은 시간복잡도로 가능한지 아닌지 판단하기 위해 금광 문제를 풀 때 쓰였던 것과 비슷한 느낌의 lmax, rmax, allmax가 여기서도 쓰입니다. 오프라인 쿼리로 만들어 Parallel Binary Search로 할 수도 있고, 그냥 Persistent Segment Tree로 해결할 수도 있습니다. 저는 PST를 이용했습니다. 여담이지만 solved.ac를 비교적 최근에 설치했는데 정말.. 공감수 1 댓글수 0 2020. 1. 27.
[BOJ] 1933번: 스카이라인 https://www.acmicpc.net/problem/1933 multiset으로 현재 존재하는 빌딩들의 높이를 관리하고 event를 x좌표 순으로 처리하면 됩니다. https://github.com/blisstoner/BOJ/blob/master/1933.cpp 공감수 0 댓글수 1 2019. 12. 3.
[BOJ] 10167번: 금광 https://www.acmicpc.net/problem/10167 주어진 수열에서 연속한 구간의 최대 합 문제를 DP로 해결할 수도 있지만, 수열의 index를 1부터 $N$까지라고 할 때 - 1번째 원소를 포함하는 구간 중에서 최댓값을 저장하는 $lmax$ - $N$번째 원소를 포함하는 구간 중에서 최댓값을 저장하는 $rmax$ - 아무 제한 조건 없이 최댓값을 저장하는 $allmax$ 변수를 가지고 segment tree와 같은 느낌으로 해결할 수도 있습니다. segment tree를 활용할 경우 값의 update를 $O(lg N)$에 처리할 수 있다는 장점이 있기에 이 문제에서 사용하기 적합합니다. 일단 좌표압축을 하고, 특정 x좌표를 시작점으로 해 끝까지 가면서 update를 하고 최댓값을 구하.. 공감수 0 댓글수 0 2019. 12. 2.
[BOJ] 15293번: Knapsack Cryptosystem https://www.acmicpc.net/problem/15293 NEERC 2017 기출인데 솔직히 만약 대회 중이었다면 이 문제는 무조건 버렸어야 한다고 생각합니다. 물론 로씨아 형님들은 강해서 무려 3팀이나 이걸 풀었지만.. 1도 감이 안와 홈페이지에서 풀이를 찾아봤습니다. $N$이 42정도면 그냥 MITM으로 해결하고, $N$이 42보다 크면 $a[0]$이 $2^{64-N}$보다 작아야한다는 점을 이용해 $r$의 후보들을 구하고 해당 $r$에서 super increasing sequence가 되는지 체크하면 됩니다. inverse를 구할 때 __int128을 쓰면 시간초과가 발생하고 오일러 파이를 이용해야 합니다. 나름 암호학 전공하겠다는 사람인데 안풀고가긴 섭섭해서 풀고 가지만 정말 쉽지 않은.. 공감수 1 댓글수 0 2019. 10. 21.
[BOJ] 15896번: &+ +& https://www.acmicpc.net/problem/15896 아주 오랫동안 헤매다가 풀이를 보고 해결했습니다. &+의 경우에는 각 자리를 따로 보면 되니까 쉬운데 +&를 어떻게 해야할지 좀 많이 어려웠습니다. 결론적으로 +&에서도 각 자리를 따로 보는데, 해당 자리가 1이기 위해서는 모든 +의 결과가 1이어야 한다는 것을 알 수 있습니다. 예를 들어 5번째 자리가 1인지 확인하려면 0xxxx + 0xxxx, 0xxxx + 1xxxx, 1xxxx + 0xxxx, 1xxxx + 1xxxx 의 결과에서 5번째 자리가 1인지를 보면 되는데 모든 xxxx를 다 볼 필요가 없이 가장 큰 것과 가장 작은 것만 보면 됨을 알 수 있습니다. https://github.com/blisstoner/BOJ/blob/m.. 공감수 0 댓글수 0 2019. 10. 15.
[BOJ] 17513번: Hilbert's Hotel https://www.acmicpc.net/problem/17513 대회중에는 풀어내지 못했던 문제입니다. group의 시작 위치를 $ax+b$꼴의 segment tree로 관리하면 1, 2번 쿼리의 처리가 가능하고, 또 group이 추가될 때 마다 유한한 그룹은 묶어서 관리하면 3번 쿼리에 대해 최대 30개의 그룹 묶음을 확인하면 됨을 알 수 있습니다. 그룹 묶음 내에서 정확한 그룹을 찾기 위해서는 binary search를 이용해야 합니다. 3번 쿼리의 구현이 개념이 엄청 어려운건 아닌데 이상하게 계속 틀려서 정말 까다로웠습니다. https://github.com/blisstoner/BOJ/blob/master/17513.cpp 공감수 0 댓글수 0 2019. 10. 15.
[BOJ] 10464번: XOR https://www.acmicpc.net/problem/10464 이런 류의 문제는 늘 참 뭔가 까다롭지만, 재귀적으로 잘 해결하면 됩니다. 예를 들어 1부터 10110101(2) 까지의 XOR값을 구하고 싶다고 할 때, 1부터 1111111(2)까지의 XOR값은 0이니 떼버리고 뭐 그런식으로 구했습니다. https://github.com/blisstoner/BOJ/blob/master/10464.cpp 공감수 0 댓글수 0 2019. 9. 12.
[BOJ] 16685번: XOR 포커 https://www.acmicpc.net/problem/16685 XOR Maximization을 알고있다고 할 때, $a_0 a_1 a_2 a_3 \dots$에서 짝수개의 maximization은 $a_0 \oplus a_1, a_0 \oplus a_2, a_0 \oplus a_3\dots$에서의 maximization임을 이용해 바로 해결이 가능합니다. 이미 이 풀이를 대회장에서 출제자에게 들었기 때문에 직접 착안해낸건 아닙니다ㅎㅎ.. https://github.com/blisstoner/BOJ/blob/master/16685.cpp 공감수 0 댓글수 0 2019. 9. 12.
[BOJ] 11191번: XOR Maximization https://www.acmicpc.net/problem/11191 $N$개의 수들을 XOR한 값이 최대한 크게 만드는 문제입니다. 대충 basis를 구해서 싸바싸바하면 된다는걸 알았는데 구현을 어떤식으로 해야하나 애를 먹어 손을 안대고 있었습니다. 그런데 koosaga님의 블로그(https://koosaga.com/132)에서 참고용으로 올려놓은 코드를 보니 되게 깔쌈하게 잘 구현되어있네요. 덕분에 좋은 것 배워갑니다^^77 https://github.com/blisstoner/BOJ/blob/master/11191.cpp 공감수 0 댓글수 0 2019. 9. 12.
[BOJ] 4798번: Dirichlet's Theorem https://www.acmicpc.net/problem/4798 슬랙에서 sait2000님이 링크를 올린걸 보고 들어가서 풀어보려고 했습니다. 맨 처음엔 그냥 Miller Rabin 주구장창 돌리면 맞을 수 있는 문제인줄 알았는데 계속 시간초과가 떴고, 양심을 팔고 공식 풀이를 보니 마치 저희가 에라토스테네스의 체를 가지고 소수 판별을 하는 것 처럼 최대 $10^6$개의 후보들에 대해 걸러내는 방식으로 해결을 해야 하는 문제였습니다. 방법을 알고 코딩을 했음에도 불구하고 각종 까다로운 예외처리로 인해 굉장히 많이 틀린 후에 맞았네요. https://github.com/blisstoner/BOJ/blob/master/4798.cpp 공감수 0 댓글수 0 2019. 9. 11.
[BOJ] 13925번: 수열과 쿼리 13 https://www.acmicpc.net/problem/13925 Segment Tree의 lazy propagation 문제인데 각 노드는 자신이 담당하는 구간의 원소의 합(코드에서의 변수 $seg$)과 더불어 $a \times seg[node] + b$로 업데이트를 하면 된다는 것을 나타내는 $a, b$(코드에서의 변수 $lazy1, lazy2$를 들고 있으면 됩니다. https://github.com/blisstoner/BOJ/blob/master/13925.cpp 공감수 0 댓글수 0 2019. 9. 9.
[BOJ] 14897번: 서로 다른 수와 쿼리 1 https://www.acmicpc.net/problem/14897 직관적으로는 Mo's algorithm으로 해결할 수 있고, merge sort tree 혹은 persistent segment tree로도 해결할 수 있다고 합니다.(https://www.acmicpc.net/board/view/40731) 저는 Mo's algorithm으로 해결했습니다. https://github.com/blisstoner/BOJ/blob/master/14897.cpp 공감수 0 댓글수 0 2019. 9. 8.
[BOJ] 17373번: 녜힁 https://www.acmicpc.net/problem/17373 쿼리를 정렬하지 않을 경우 PST로, 정렬할 경우 그냥 일반 세그먼트 트리로 해결 가능합니다. 저는 PST로 풀이했습니다. 역시 구현은 쉽지 않네요. https://github.com/blisstoner/BOJ/blob/master/17373.cpp 공감수 0 댓글수 0 2019. 9. 7.
[BOJ] 16765번: Teamwork https://www.acmicpc.net/problem/16765 $D[i]$를 $i$번째까지의 최댓값이라고 했을 때 $i$번째 소를 포함하는 구간이 어디까지인가를 가지고 $D[i]$를 채울 수 있습니다. 간단한건데 굉장히 헤맸네여 https://github.com/blisstoner/BOJ/blob/master/16765.cpp 공감수 0 댓글수 0 2019. 8. 9.
[BOJ] 16764번: Cowpatibility https://www.acmicpc.net/problem/16764 예를 들어 어느 한 소가 선호하는 맛이 (1, 2, 3, 4, 5)라고 할 때 (1) (2) (3) (4) (5) (1 2) (1 3) (1 4) (1 5) (2 3) ... (1 2 3) (1 2 4) (1 2 5) (1 3 4) ... (1 2 3 4) (1 2 3 5) ... (1 2 3 4 5) 를 모두 저장합니다. map을 이용해도 되고 그냥 리스트에 넣어둔 후 정렬을 해두어도 됩니다. 이후 포함과 배제를 이용해, 나와 겹치지 않는 소의 수는 N - 맛 1개가 겹치는 소의 수 + 2개가 겹치는 소의 수 - 3개가 겹치는 소의 수 + 4개가 겹치는 소의 수 - 5개가 겹치는 소의 수이고 이를 이분탐색으로 빠르게 알아내면 됩니다. .. 공감수 0 댓글수 0 2019. 8. 9.
[BOJ] 16763번: Fine Dining https://www.acmicpc.net/problem/16763 우선 Dijkstra로 $N$과의 거리를 전부 구한 후, 다시 한 번 Dijkstra와 유사한 방식을 통해 각 지점이 food를 먹고갈 때의 비용을 계산하면 됩니다. https://github.com/blisstoner/BOJ/blob/master/16763.cpp 공감수 0 댓글수 0 2019. 8. 8.
[BOJ] 1099번: 알 수 없는 문장 https://www.acmicpc.net/problem/1099 $D[i] = S[0 \; to \; i]$에서의 최소 비용이라고 할 때, $D[i]$는 $D[i-1],\;D[i-2],\;\cdots$ 등의 값으로부터 쉽게 알아낼 수 있습니다. 전반적인 제한이 작아 굉장히 비효율적으로 짜도 상관이 없습니다. https://github.com/blisstoner/BOJ/blob/master/1099.cpp 공감수 0 댓글수 0 2019. 8. 1.
[BOJ] 10711번: 모래성 https://www.acmicpc.net/problem/10711 정직하게 매번 전체를 훑으면서 매 초의 흐름을 BFS로 확인하려고 한다면 시간초과가 납니다. 대신 다음 초에 부서질 곳은 반드시 이번 초에 부서진 곳과 인접해야 한다는 점을 이용해 O(NM)으로 풀이가 가능합니다. https://github.com/blisstoner/BOJ/blob/master/10711.cpp 공감수 1 댓글수 2 2019. 7. 23.
[BOJ] 8876번: 바자와 샤자(IOI'13 Game) https://www.acmicpc.net/problem/8876 IOI'13 Game 문제입니다. 굉장히 빡세다는 얘기만 듣고 구현해볼 엄두를 못냈는데, 큰 마음먹고 구현을 했습니다. 메모리를 절약하기 위해 pointer를 들고가는 대신 left, right index를 가져갔습니다. 2d segment tree를 처음 짜봤는데 굉장히 오류가 많아 열심히 뜯어고쳐서 간신히 맞았네요. 이걸 어떻게 고등학생때 풀 수 있는지 경이롭네요. 역시 국대는 넘사인 것 같습니다,,, https://github.com/blisstoner/BOJ/blob/master/8876.cpp 공감수 0 댓글수 0 2019. 7. 23.
[BOJ] 13505번: 두 수 XOR https://github.com/blisstoner/BOJ/blob/master/15940.cpp 0, 1을 가지고 Trie로 만들어두고 MSB부터 최대한 일치하지 않는 쪽으로 가는 방식으로 구현을 하면 됩니다. https://github.com/blisstoner/BOJ/blob/master/13505.cpp 공감수 0 댓글수 0 2019. 7. 4.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.