본문 바로가기

전체 글53

백준 단계별로 풀어보기 2557번 Hello World (C, python) 문제Hello World!를 출력하시오.입력없음출력Hello World!를 출력하시오.링크https://www.acmicpc.net/problem/2557풀이C의 printf 함수나 python의 print 함수를 이용하여 Hello World!를 출력하면 된다.소스코드(C)#include int main(){ printf("Hello World!"); return 0;} 소스코드(python)print("Hello World!") 2025. 3. 6.
1167 트리의 지름 데이터 추가 코드포스 핵도 연습하는 겸 백준 문제에 데이터 추가가 필요한 문제를 물색해보기로 했다. 그러던 중 채점현황에서 누군가 이 문제를 해결하는 것을 보았고, 푼 문제길래 탐색해볼 겸 들어가게 되었다. 기본적으로 핵을 할 때는 tle 핵이 가장 노리기 쉽다. 이를 노리고 맞힌 사람 탭에서 가장 마지막 페이지로 이동하였다. 그런데, 가장 마지막 페이지의 코드는 O(n^2)의 시간복잡도인 것은 물론, dfs 탐색을 통해서 발생하여야 하는 recursion limit 초과 에러가 발생하지 않고 있었다. 즉, 일자로 n개의 노드가 연결되어 있는 그래프 데이터가 존재하지 않는 것을 알았다. 생각보다 간단하게 필요한 데이터를 알았으니 이를 구현해주기만 하면 된다.간단하게, 0 이 문제의 풀이 방식이 틀린 사람들보다는 re.. 2024. 9. 30.
코포, 대회 칠 때 꼭 지켜야 할 것들 서론블로그 글 소재도 떨어져 가서 좋은 소재가 있나 생각해봤는데, 정리할 필요가 있을 것 같아서 쓰게 되었다.사실 코포랑 앳코 박아서 내가 대회 치기 전에 보려고 쓴 건 안 비밀 대회 시작 전 - Online Contest 이거나 팀 노트를 사용할 수 있는 대회라면 미리 필요한 알고리즘들을 정리해놓자.특히, 문자열(아호코라식, kmp, 접미사와 lcp 배열), 세그먼트 트리(2차원 세그먼트 트리, 퍼시스턴트 세그먼트 트리, heavy light 분할, 오일러 경로 테크닉, 금광 세그), 좌표 압축, 오프라인 쿼리(제곱근 분할법, 모스 알고리즘, 희소 배열), 일부 수학 알고리즘(모듈로 역원, 밀러-라빈 소수 판별법, 폴라드 로, FFT), 기하(convex hull, 로테이팅 켈리퍼스), 동적 계획법 최.. 2024. 9. 8.
Codeforces Round 971 (Div.4) E, F, G1 풀이 현재 Div.4는 블루라 언레라 contest를 직접 치지는 않았다. 하지만, 컨테스트가 끝나고 심심해서 문제 이름을 보니 원신, 붕괴 스타레일 캐릭터길래 찍먹으로 E, F, G1 정도만 풀어보았다. E. Klee's SUPER DUPER LARGE Array!!! 클레가 가지고 있는 수열에서 mid를 기준으로 [k, mid], [mid+1, k+n-1]로 구간을 나누어 각자의 합을 구한 다음 차를 비교하는 것은 가우스 합 공식을 이용하면 O(1)에 가능하다. 이때, mid가 커질수록 [mid+1, k+n-1] - [k, mid] 값이 strict하게 증가하므로 mid의 부호에 따라 파라매트릭 서치를 통해서 이 값의 절댓값을 최소로 하는 인덱스를 찾아줄 수 있다. 소스코드#include #include .. 2024. 9. 5.

티스토리툴바