류나의 작은 DB

27살 류나의 바르고 다르게 살기

Programming 17

UCPC 2022 예선 후기

캐티님, 빙하님과 [투어리스트의 올바른 가르침.] 팀으로 UCPC 2022에 참가했습니다. 팀원들은 PS 경험이 꽤(사실, solved.ac Diamond 티어를 달성했을 정도로 상당히) 있는 분들로서 이전에 포켓몬 배틀 씬에서 만난 분들입니다. 팀이 결성되었던 4월 초 당시 저의 티어가 Silver III이었던 걸로 기억하는데, 막 PS를 시작하는 단계였던 저를 믿어준 팀원들에게 무한한 감사를 전합니다. 시간을 맞춰 대회 셋을 푸는 팀 연습은 5월부터 6번 정도 한 것 같습니다. 저희 팀은 팀원 간의 실력차가 큰 편이기 때문에 제가 스코어보드를 따라가며 많이 풀린 문제를 맡고, 나머지 두 분이 적게 풀린 문제를 맡는 식으로 연습했습니다. (Codeforces Gym에서 연습하면 스코어보드를 실시간으로 ..

UCPC 2022 예선 D-13 문제풀이 일지

목차 1. 오늘의 알고리즘 진도 - 2740번: 행렬 곱셈 - 10830번: 행렬 제곱 - 11444번: 피보나치 수 6 - 1655번: 가운데를 말해요 - 16500번: 문자열 판별 - 11066번: 파일 합치기 - 11049번: 행렬 곱셈 순서 오늘의 알고리즘 진도 오늘은 '단계별로 풀어보기'에 포함된 분할 정복 3문제와 우선순위 큐 1문제를 풀고 나서, 조금 어려운 다이나믹 프로그래밍 문제들에 도전해 보기로 했습니다. C++ 템플릿 코드 #include using namespace std; typedef long long ll; typedef long double ld; typedef pair pii; typedef tuple tiii; #define F first #define S second #..

UCPC 2022 예선 D-14 문제풀이 일지

목차 1. 오늘의 알고리즘 진도 - 1958번: LCS 3 - 13711번: LCS 4 - 13305번: 주유소 - 18258번: 큐 2 - 6064번: 카잉 달력 - 14500번: 테트로미노 - 11401번: 이항 계수 3 2. AtCoder Beginner Contest 256 - A번: 2^N - B번: Batters - C번: Filling 3x3 array - D번: Union of Interval 3. Codeforces Round #801 (Div. 2) - A번: Subrectangle Guess - B번: Circle Game - C번: Zero Path 오늘의 알고리즘 진도 오늘은 다양한 분류의 문제를 풀어보기로 했습니다. C++ 코드 템플릿 혹시 제 코드를 참고하실 분들은 코드 최상단..

UCPC 2022 예선 D-16, D-15 문제풀이 일지

목차 1. 오늘의 알고리즘 진도 - 24416번: 알고리즘 수업 - 피보나치 수 1 - 9184번: 신나는 함수 실행 - 1912번: 연속합 - 1932번: 정수 삼각형 - 14002번: 가장 긴 증가하는 부분 수열 4 - 11054번: 가장 긴 바이토닉 부분 수열 - 12105번: 가장 긴 증가하는 부분 수열 2 - 14003번: 가장 긴 증가하는 부분 수열 5 - 2565번: 전깃줄 - 2568번: 전깃줄 - 2 - 9251번: LCS - 9252번: LCS 2 - 12865번: 평범한 배낭 - 9084번: 동전 오늘의 알고리즘 진도 오늘은 다이나믹 프로그래밍 수련의 날로 정했습니다. 그래서 다이나믹 프로그래밍 문제를 14개 풉니다. C++ 코드 템플릿 혹시 제 코드를 참고하실 분들은 코드 최상단에 ..

UCPC 2022 예선 D-20~D-17 문제풀이 일지

6월 12, 13, 14일을 설렁설렁 보내다가 15일이 되어 정신이 든 나... 늦었다고 생각할 때가 가장 빠른 때라고 하니 달려보겠습니다. 목차 1. 알고리즘 진도 - 2750번: 수 정렬하기 - 10815번: 숫자 카드 - 14425번: 문자열 집합 - 1269번: 대칭 차집합 - 11478번: 서로 다른 부분 문자열의 개수 - 3009번: 네 번째 점 - 2477번: 참외밭 - 3053번: 택시 기하학 - 1002번: 터렛 - 1004번: 어린 왕자 - 1358번: 하키 - 5086번: 배수와 약수 - 1037번: 약수 - 1934번: 최소공배수 - 2981번: 검문 - 3036번: 링 - 1010번: 다리 놓기 - 2004번: 조합 0의 개수 - 15651번: N과 M (3) - 2580번: 스도..

UCPC 2022 예선 D-21 문제풀이 일지

블로그 업데이트는 오랜만입니다. 지난 두 달 동안은 공부한 내용을 굳이 공개된 곳에 전부 깔끔히 정리해 포스팅할 필요는 없지 않을까~라는 생각에 개인 GoodNotes 계정에만 정리해두고 있었습니다. 굿노트가 워낙 효율이 좋아서인지 기존보다 훨씬 많은 공부량을 뽑아낼 수 있었지만, 최근 며칠 동안은 공부할 의욕이 잘 나지 않아 고민하던 차에 업데이트가 뜸하던 블로그가 생각났습니다. UCPC 2022에 출전하게 됨에 따라 예선(그리고 잘 되면 본선까지..)을 대비해 매일 일정 수의 문제를 풀어보려고 하는데, 푼 문제를 블로그에 일지 형식으로 정리해보면 좋겠다고 판단해서 글을 작성하기 시작했습니다. 목차 1. 오늘의 알고리즘 진도 - 2941번: 크로아티아 알파벳 - 1193번: 분수찾기 - 10757번: ..

우선순위 큐, 힙과 이진 탐색 트리

이번 글에서는 우선순위 큐에 대해 알아봅니다. 이를 구현할 수 있는 두 가지 방법인 힙과 이진 탐색 트리에 대해서도 살펴봅니다. 목차 1. 우선순위 큐, 힙과 이진 탐색 트리 - 우선순위 큐란 - 힙이란 - 이진 탐색 트리란 2. 우선순위 큐의 구현 - 우선순위 큐의 두 가지 구현 - STL의 priority_queue와 multiset 3. 문제풀이: 힙과 이진 탐색 트리 - BOJ 11279번: 최대 힙 (실버 II) - BOJ 1927번: 최소 힙 (실버 II) - BOJ 11286번: 절대값 힙 (실버 I) - BOJ 5639번: 이진 검색 트리 (골드 V) 4. 문제풀이: 우선순위 큐 - BOJ 7662번: 이중 우선순위 큐 (골드 IV) - BOJ 2075번: N번째 큰 수 (실버 I) - B..

BOJ 1654번: 랜선 자르기 문제로 알아보는 "최적화 문제 결정 문제로 바꿔 풀기"

지난 주 코로나19에 걸려 격리를 하면서 매일 근근이 solved.ac [CLASS 2] 문제만 풀고 있었는데, 순서대로 풀다가 맞닥뜨린 "랜선 자르기" 문제에 의외의 중요한 알고리즘 설계 패러다임이 담겨 있다고 생각해 글을 작성하기로 했습니다. 목차 1. 문제 훑어보기 2. 최적화 문제와 결정 문제 3. 이분 탐색과 매개 변수 탐색 4. BOJ 1654번: 랜선 자르기 (실버 III) 참고한 자료 알고리즘 문제 해결 전략, 구종만 https://book.algospot.com/ 알고리즘 문제 해결 전략 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트, ISBN 978-89-6626-054-6 새 소식 책 소개 은 새로운 알고리즘 책입니다. 종이에 적힌 의사코드 book.al..

트리의 개념과 이진 트리의 순회

이번 글에서는 트리 자료구조의 개념과, 가장 간단한 트리의 일종인 이진 트리의 순회에 대해 알아봅니다. 목차 1. 트리의 구현과 순회 - 트리란 - 트리의 표현 - 트리의 순회 2. 이진 트리 - 이진 트리의 개념 - 이진 트리의 순회 3. 문제풀이: 트리 기본 - BOJ 1068번: 트리 (골드 V) - BOJ 15681번: 트리와 쿼리 (골드 V) - BOJ 11725번: 트리의 부모 찾기 (실버 II) - BOJ 15900번: 나무 탈출 (실버 I) 4. 문제풀이: 이진 트리의 순회 - BOJ 1991번: 트리 순회 (실버 I) - BOJ 9934번: 완전 이진 트리 (실버 I) - BOJ 4256번: 트리 (골드 III) - BOJ 2263번: 트리의 순회 (골드 II) 5. 문제풀이: 간선의 가..

배열, 연결 리스트, 스택과 큐 기본 문제

이번 글에서는 지금까지 공부한 자료구조들(배열, 연결 리스트, 스택, 큐)을 활용하는 기본 문제를 풀어봅니다. 목차 1. 동적 배열과 연결 리스트 - 동적 배열: C++ STL의 vector - 연결 리스트: C++ STL의 list - vector vs. list - 문제풀이 2. 스택과 큐, 데크 - C++ STL의 stack, queue - C++ STL의 deque - 문제풀이 참고한 자료 알고리즘 문제 해결 전략, 구종만 https://book.algospot.com/ 알고리즘 문제 해결 전략 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트, ISBN 978-89-6626-054-6 새 소식 책 소개 은 새로운 알고리즘 책입니다. 종이에 적힌 의사코드 book.alg..