PS하는 abra
-
2023 UCPC 예선 후기PS하는 abra/후기 2023. 7. 5. 06:45
7월 1일에 봤던 대회인데 이제야 후기를 쓴다. 대회 이틀 후에 여름학기 중간고사가 있어 바로 벼락치기 on 해버렸고, 시험당일은 시험을 조진줄 알고 우울해서 안 썼고, 그 다음날은 내가 시험을 잘봤다는 것을 알게되어서 기분이 좋아져 놀아버렸다. 정말 변명이다..# 대회 시작 전 : 팀 전략?팀은 팀연습도 할겸? 올해 ICPC 나가기로 한 팀으로 나갔다. 팀 결성에 많은 이슈가 있었으나 최종적으로 옥테인, 서리와 하기로 했다. UCPC 신청 마감 약 3시간 전에 팀명 안아줘요, 닉네임 덤벼줘요 알려줘요 끝내줘요로 급조했다. 팀연습은 한번도 하지 않았고, 예선 시작 n분 전에 3k 번은 서리가, 3k+1은 옥테인이, 3k+2는 내가 맡기로 했다. 여기서 살짝 문제가 발생해버렸는데, 10문제일 것이라는 고정..
-
Small to Large(큰거 작은거)PS하는 abra/알고리즘 2023. 7. 5. 03:51
# Small to Large란? Small to Large(큰작(큰거 작은거)이라고도 부름)는 두 집합을 하나로 합치는 것을 반복적으로 할 때 시간복잡도를 줄이기 위해 쓸 수 있는 방법이다. 나이브하게 합쳐보자. 두 집합 A, B를 합치려고 할 때, B의 원소들을 A로 옮겨서 합친다고 하면 옮기는 데 걸리는 시간은 B의 크기가 된다. 하지만 이 방법의 worst case를 생각해보면 이는 매우 오래 걸린다. B의 크기는 x이고 A는 1이라고 해보자. 그러면 x번 옮긴 후 A의 크기는 x+1이 되었다. 그런데 이 다음에는 크기가 1인 집합 C와 A를 합치라고 한다. C에 A를 옮기면 x+1번을 또 옮기게 된다... 따라서 원소의 개수가 n이라고 하면, 전제 원소를 다 합칠 때 최악의 경우에는 n(n - ..
-
2022 LG CNS Code Monster 예선 후기PS하는 abra/후기 2022. 11. 13. 01:39
11월 12일 오전 10시부터 1시까지 3시간동안 4문제로 진행되었다. 오랜만에 아침부터 머리 굴리려니 좀 졸렸던 것 같다. 요즘 PS는 후배 가르치는 용도로만 해서 좀 걱정도 됐지만 다행히 실력이 녹슨건 아닌것 같다. 1번 보고 구현이 좀 귀찮겠다 싶어서 그냥 4번까지 쭉 풀이 생각하고 구현은 나중에 몰아서 했다. 거의 1시간동안 1~4번 문제이해&풀이구상을 했다. 1번 구현이 살짝 꼬여서 30분, 2번이 18분, 3번은 7분정도 걸렸다. 4번은 LCA를 원래 짜던 방식으로는 처리하지 못하는 부분이 있어서 살짝 바꿔서 짜느라 중간에 좀 더 생각했었다. 45분정도 걸려서 12시 40분에 무사히 모든 문제를 제출했다. 제출을 해도 결과를 안알려줘서(히든 데이터라고 하나?) 좀 찜찜하기도 하고 지금 생각하니..
-
세그먼트 트리 (Bottom-up)PS하는 abra/알고리즘 2022. 11. 9. 12:25
# 세그먼트 트리란? 세그먼트 트리란 구간에 대한 쿼리를 효율적으로 처리하기 위한 자료구조로, 각 노드가 자신의 두 자식 노드가 관리하는 구간을 합한 구간에 대한 정보를 갖는 완전 이진 트리이다. # 구현방법 : Bottom-up과 Top-down 구현하는 방법으로는 Bottom-up과 Top-down 방식이 있는데, 기본적인 세그를 구현할 때는 바텀업을 사용하는 편이다. 탑다운은 쿼리를 처리할 때 위에서 아래(루트에서 리프로)로 내려가면서 처리하는 방법이고, 바텀업은 밑에서 위로(리프에서 루트로) 올라가며 처리하는 방법이다. 탑다운은 재귀로 구현하지만 바텀업은 반복문으로 구현하기 때문에 구현하기도 쉽고 실행속도도 빠르다. 바텀업으로 구현할 때, 구현상의 편의를 위해 포화 이진 트리로 구현한다. lazy..
-
KOI 정리PS하는 abra/문제 풀이 2022. 10. 25. 10:25
문제가 너무 많아서 천천히 추가해나갈 예정 ★ : 응용 문제가 많은 유형? 알아두면 쓸 데 많아보이는 것들 ☆ : 너무 식상하지 않으면서 좀 재밌는 문제? (개인적으로 추천하는 것) DP는 사실 다 좋은 것 같다. 초1: 단지번호붙이기(2667) #DFS ☆초2: 숫자고르기(2668) #사이클 ★초3: 직사각형 네개의 합집합의 면적 구하기(2669) #구현 #배열에 마킹 ★중1: 연속부분최대곱(2670) #브루트포스(N 작음) #DP(N) 중2: 잠수함식별(2671) #오토마타 ★중3: 여러 직사각형의 전체 면적 구하기(2672) #좌표압축 #스위핑 고1: 잠수함식별(2671) 고2: 교차하지 않는 원의 현들의 최대집합(2673) #DP(N^3) 고3: 삼각퍼즐(2674) #백트래킹 *미해결. 풀 수 있..
-
2022 이화여대 전국 여고생 프로그래밍 경진대회 후기PS하는 abra/후기 2022. 9. 21. 11:20
2022월 9월 17일 토요일에 봤던 대회이다. 자소서 쓰느라 바빠서 후기를 지금 올린다. 자소서 쓰는게 얼마나 바쁘겠어 하면서 대회를 신청한 몇달전의 나를 때리고 싶었다. 올해도 온라인으로 진행되었고, 프로그래머스를 이용해 대회를 봤다. 오후 2시부터 4시까지, 2시간동안 6문제를 풀어야하는 대회였다. 1시부터 접속해서 이것저것 셋팅하라던데 별로 할 건 없어서 접속해두고 자소서 썼다;; 이번에는 규정이 좀 더 빡세져서 물이나 종이같은 것도 있으면 안됐었다. 이 두개까지 막는 대회는 처음 본 것 같다.. 근데 사실 원래 물을 자주 안 마시고, 종이를 많이 쓰는 편도 아니고, 이화여대 대회는 더더욱 안 써도 돼서..괜찮았다. 전체적으로 문제를 이해하기 힘들었고, 조건이 명시되지 않았으며, 사람을 쓸데없는 ..
-
2022 제7회 국민대학교 알고리즘 대회 후기PS하는 abra/후기 2022. 8. 5. 23:36
다 풀긴 했는데 버그잡느라 시간을 너무 많이 써서 좋은 상은 못 받을 것 같다. 3문제 나와서 각각 100점씩 총 300점 만점이었다. 1번은 그냥 쉬운 수학이었고, 각 값을 m으로 나눈 나머지별로 개수를 세고 각각 짝이 맞는 것끼리 가짓수를 곱해서 경우의 수를 구했다. 이때, 나머지가 0인 것이나 m이 짝수일 때 나머지가 m / 2인 것은 컴비네이션 2로 계산해야 한다. 2번이 제일 오래 뇌절했던 문제였는데 살짝 잘못 생각해서 시간을 오래 잡아먹었다. 그러고도 인덱스를 i를 써야되는데 j라고 써서...이거 찾느라 정말 오래 걸렸다. 하필 예제는 왜 맞는 건데;; 세 가지 경우로 나눠서 생각하면 된다. 내가 방문하려는 점 P(x, y)에 대해서 1. 점 P가 '마스크를 쓰는 점들을 모두 포함하는 가장 작..
-
2022 KOI 2차 대회 후기PS하는 abra/후기 2022. 7. 18. 10:58
7월 16일에 봤었던 대회인데 대회 끝나고 노느라 지금 후기를 올린다.. 고3이라서 이번이 마지막 KOI였는데 실력은 크게 늘진 않은 것 같아서 1, 2번 풀고 3, 4에서 부분점수 50점정도 긁어 은상 턱걸이를 하자는게 목표였다. 하지만 대회가 시작되고, 1번을 보니 어려웠다. 문제를 읽고 대충 생각나는 풀이를 짜서 내보니 시간초과가 나서 망했구나 싶었다. 그게 내 최선의 풀이라고 생각했었기 때문이다. 혹시 몰라서 '난이도순이 아닌가'라는 희망을 품고 문제들을 다 읽어보기로 했다. 2번도 어려워보였다. 3번은 조금 쉬워보였는데 막상 풀이를 생각하려니 어렵구나 싶었다. 4번은 문제가 뭔 소리인지 도무지 이해할 수 없었다. 그래서 난이도순이 맞는 것 같다고 생각하고 1번으로 돌아와 풀이를 다시 생각해 보았..