전체 글 (10) 썸네일형 리스트형 Codeforces #930 Div. 1 3줄 요약 1. A, B, C를 생각보다 빨리 풀었지만, 쓸데 없는 패널티 4개를 받아서 굉장히 안타까웠다. 2. 그럼에도 불구하고 레드 퍼포가 나왔고, 최대 레이팅 달성에 성공했다. ㅎㅎ 3. IOI 국대 선발고사 연습한게 효과가 좀 있는 듯 하다. ㅠㅠ 서론 2/29(목)에 오랜만에 Codeforces #930 시험에 응시했다. 본계정으로 시험을 보는 것은 작년 10월 이후에 처음이었다. 오랜만에 코포를 하는 것이기 때문에 낮에 옛날 코포 Div. 1 버추얼을 돌았다. 성적이 꽤나 잘 나왔고, 전보다 실력이 늘었음을 느낄 수 있었다. 시험이 시작되었다. A A 문제를 읽었다. 최댓값이 N-1보다 크거나 같은 최소의 (2^k-1)꼴 자연수가 될 것이라는 것을 알아냈고, 모든 N에 대해서 0 PS 연습 1 1/14 ~ 2/18 위 기간 동안 2024 1/2차 선발고사를 대비하여 푼 문제들 목록이다. 매일은 아니지만 꽤나 자주 서브태스크가 있는 문제로 4문제 5시간 셋을 만들어서 풀었고, 그 외의 시간은 시간 중에 풀지 못한 문제를 업솔빙하거나, 서브태스크가 없는 문제를 풀었다. (O : 직접 푼 문제 / X : 업솔빙한 문제) 27508 던전(O) -> 2차원 DP 27511 야유회(X) -> 아이디어, 투스텝 27605 기지 간소화(O) -> 대충 큰작 -> pair 절대 쓰지 말자. 엄청 느리다. 27607 학생들(O) -> 재밌었던 아이디어 문제. 문제의 조건을 완벽히 이해하면 나머지는 할만 함. 3654 L퍼즐(O) -> 2-SAT 22029 철도(O) -> 그냥 투스텝 17624 검은 돌(X) -.. 큐(Queue) 큐가 뭐에요 큐는 가장 먼저 넣은 값이 가장 먼저 빠져나오는 FIFO(First-In-First-Out)의 자료구조입니다. 큐에 push 연산을 하면 원소가 추가되고, pop 연산을 하면 가장 먼저 넣은 원소가 삭제됩니다. 그 외에도 size(큐의 크기), front(가장 앞에 있는 원소), back(가장 뒤에 있는 원소), empty(비었는지) 연산이 있습니다. 참고로 큐는 나중에 BFS에서 나오니 꼭 알아두세요. 구현은 어케 해요 구현은 스택과 마찬가지로 연결 리스트를 통해 구현할 수도 있고, STL 내장 기능을 사용하는 방법이 있습니다. 특별히 STL을 사용할 수 없는 환경이 아니라면 STL 내장 큐를 사용하는 것이 훨씬 편합니다. queue 이름;과 같은 방식으로 선언해서 push(원소), pop.. KOI 2023 중등부 2차 후기 대회 준비 영재고 2차 시험과 정보올림피아드 2차 시험이 6일차이나는 바람에 정보올림피아드 준비를 할 시간이 부족했다. 그래서 영재고 2차 시험이 끝난 다음날부터 미친듯이 정보를 공부했고, 준비했던 기간이 매우 짧았던 만큼 더 집중도 있게 공부할 수 있었다. 준비했던 방법은 그냥 우사코 골드 문제를 계속 풀었다. 우사코 골드 정도의 문제가 골드 상위 ~ 플래티넘 중하위 정도의 문제가 섞여있어 연습하기 적절했다. 대회 직전 벌써 3년째 치루는 온라인 시험이기 때문에, 화장실 시간 분배가 매우 중요하다는 사실을 깨달았다.. 대회 시작 전에는 최대한 물을 마시지 않았고, 방에 물을 2병만 들고 갔다. (그마저도 결국 후회하긴 했지만...) KOI는 매번 온라인 시험 때 줌을 사용했는데, 다른 참가자들 때문에 .. 스택(Stack) 스택이 뭐에요 스택은 가장 늦게 넣은 값이 가장 먼저 빠져나오는 LIFO(Last-In-First-Out)의 자료구조입니다. 스택에 push 연산을 하면 원소가 추가되고, pop 연산을 하면 가장 늦게 넣은 원소가 삭제됩니다. 그 외에도 size(스택의 크기), top(가장 위에 있는 원소), empty(비었는지) 연산이 있습니다. 구현은 어케 해요 구현은 연결 리스트를 사용해서 직접 구현하는 방법과 STL의 내장 기능을 사용하는 방법이 있습니다. 구현은 생각보다 복잡하기 때문에 별로 추천하지는 않습니다.(STL을 사용할 수 없는 환경일 때만 사용합시다.) (코드) 더보기 template struct Stack { struct Node { T num; Node*next; Node() { num=0; ne.. 동적 계획법(Dynamic Programming) 동적 계획법이 뭐에요 동적 계획법을 한 마디로 정의내리기는 힘들지만 핵심은 큰 문제를 해결하기 위해 더 작은 문제를 해결한다는 것입니다. 실제로 PS를 할 때 가장 많이 보이는 문제 유형이기도 하고, solved.ac 기준 3번째로 많은 태그입니다. 예시로 설명해요 피보나치 수열로 예를 들어보겠습니다. $$F_n = \begin{cases} 0 & \text{if }n = 0 \\ 1 & \text{if }n = 1 \\ F_{n-1} + F_{n-2} & \text{if }n > 1 \end{cases}$$ 피보나치 수열의 점화식은 이렇습니다. $F_n$이라는 큰 문제를 해결하기 위해 $F_{n-1}$과 $F_{n-2}$ 같은 작은 문제의 결과를 이용합니다. 간단하게 재귀 함수로 코드를 짜면 int f.. 그리디 알고리즘(Greedy Algorithm) 그리디가 뭐에요 그리디 알고리즘이란 말 그대로 욕심을 부리면서 답을 찾는 알고리즘을 말합니다. 그때 그때 상황에서의 최적해로 답을 정하는 방식입니다. 이 방식으로 풀리는 문제는 많지 않지만, 이 방식이 통하는 문제가 존재하기에 꼭 알아둬야 합니다. 그리디 알고리즘으로 해결하는 문제들은 대부분 그리디로 풀린다고 증명을 하기 보다는, 직관을 많이 요하고 Proof by AC가 많습니다. 문제를 읽다가 어떻게 하면 될 것 같다는 생각이 들면 반례를 찾아보고, 없으면 빠르게 구현하면 됩니다. 예시 1 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전.. 이분 탐색(Binary Search) 이분탐색이 뭐에요 이분 탐색은 $N$개의 원소가 정렬되어 있을 때, 특정 원소 $x$를 $O(log N)$의 시간복잡도에 찾는 알고리즘입니다. 이분 탐색은 다음의 원리로 동작합니다. 원소들 중 가장 가운데 값을 $x$와 비교합니다. 편의상 가운데 값을 $mid$라고 하겠습니다. $mid$가 $x$보다 크다면 끝 위치를 가운데 위치-1로 바꿔서 진행합니다. $mid$가 $x$보다 작다면 시작 위치를 가운데 위치+1로 바꿔서 진행합니다. $mid$과 $x$가 같다면 알고리즘을 종료합니다. 시간 복잡도는 어떻게 돼요 한 단계가 진행될 때마다 범위가 $\frac{1}{2}$로 줄어드므로 시간복잡도를 $x$라고 하면, $N \times (\frac{1}{2})^x = 1$ $2 ^ x = N$ $x = log .. 이전 1 2 다음
