본문 바로가기

분류 전체보기

 (149)
2023년 5월 30일 일기 현대모비스 알고리즘 경진대회가 개최됩니다. 대략 한 달 정도 남았는데 열심히 준비해보겠습니다. 가장 공부가 시급한 주제는 문자열, 기하, 플로우 정도네요. 기하와 플로우는 버리고 문자열에 집중하려고 합니다. 모비스에 집중하기 위하여 백준 대회는 잠시 쉬려고 합니다. 어차피 기말고사 시즌이라 대회가 없기도 합니다. 지금까지 7 우승 7 준우승을 달성하였는데(고인물 분들이 안 계셔서 가능한 결과지만) 개인적으로 만족스럽습니다. 대회 리뷰 글이 4개 정도 밀렸는데 시간 나는 대로 작성하려고 합니다. 토요일에 오랜만에 코드포스하려고 계획 중이었는데 서버 문제로 하루 연기되었습니다. 안타깝게도 일요일은 도저히 시간이 안 나서 건너 뛰었습니다. 어제 문제 구경해보니 제가 못 푸는 문제들이었습니다. 하루 미뤄주셔서 ..
BOJ 28039번 - 카드 게임 2 28039번: 카드 게임 2 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net ICPC 인터넷 예선 2015 B번 문제에서 N 제한을 키운 문제이다. 기존 문제의 경우 O(N^2) dp 풀이가 가능하지만 이 문제의 최대 N은 1e6이다. 먼저 나는 이 문제를 풀지 못하였고 다른 사람의 코드를 보고 풀었음을 밝힌다. 엄밀한 증명 없이 대강 감만 잡은 상태에서 작성하는 글이기 때문에 잘못된 내용이 있을 수 있다. 잘못된 내용이 있다면 지적 부탁드립니다. 다음과 같은 배열 A를 정의하자. A[i] = i번 카드에 적힌 수 배열 A의 값을 그래프로..
BOJ 1377번 - 버블 소트 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 매 루프에서 어떠한 원소 A[i]의 상태는 다음 중 하나이다. 왼쪽으로 1칸 이동한다. 오른쪽으로 x칸 이동한다. 이동하지 않는다. 그리고 상태 전이는 항상 이 순서대로 이루어진다. 예를 들어 오른쪽으로 이동하다가 왼쪽으로 이동하는 일은 발생하지 않는다는 것이다. 오른쪽으로 이동하는 원소가 있다면 왼쪽으로 이동하는 원소도 반드시 존재함에 주목하자. 따라서 답은 max(A[i]가 왼쪽으로 이동한 횟수)가 되며 이는 정렬 한 번으로 구할 수 ..
2023 부산대학교 CodeRace Open Contest 2023 부산대학교 CodeRace Open Contest www.acmicpc.net A - 첨탑 밀어서 부수기 단순 구현 00:01 AC B - 영역 색칠 색이 k번 뒤바뀌는 영역은 최소 ((k + 1) / 2 + 1)번의 붓칠이 필요하다. 00:05 AC D - 게임을 클리어하자 dp로 풀이할 수 있는데 26093번과 매우 유사하다. 최솟값 2개만 구하면 되므로 O(NM)이 가능하다. 00:13 AC E - 시간이 겹칠까? 누적 합 00:15 AC imos법이라고 많이 불리던데 간단한 테크닉에 별도의 이름을 붙일 필요가 있나 싶다. F - 산지니의 여행계획 지문이 너무 억지스럽다. 여러 풍경을 차 안에서 느긋이 즐기고 싶다면서 마지막에는 운전 거리를 최대한 줄여보자고 한다. 아무튼 mst + dfs..
2023 우아한테크캠프 6기 1차 코딩테스트 [모집] 2023 우아한테크캠프 6기 | 우아한형제들 기술블로그 {{item.name}} 우아한개발자가 되고 싶은 분들을 위한 2023 우아한테크캠프 6기 모집이 시작됩니다! 올해 우아한테크캠프 6기는요! 🏝 여름방학 8주 동안 💡 Java 언어 기반의 백엔드 교육 👩🏽‍💻 techblog.woowahan.com 지금까지 코딩테스트 응시 경험이 단 한 번밖에 없었는데 그것도 2년 전 일이다. 올해는 일정상 본과정 참가가 불가능하지만 내년에는 참가할 수도 있으므로 경험 목적으로 응시하였다. 그 행사 때문에 2차 과제테스트 또한 응시가 불가능하다 :( 4개 문제가 출제되었고 사용 가능한 언어는 Java로 제한되었다. 13시에 시작하여 3시간 동안 진행되었는데 14시부터 부산대학교 오픈콘이 예정되어 있어 1시..
Codeforces Round 866 (Div. 1) Dashboard - Codeforces Round 866 (Div. 1) - Codeforces codeforces.com A - Constructive Problem 현재 mex를 x라고 하자. x = N이라면 답은 No가 된다. 그렇지 않다면 배열 A에 (x + 1)이 존재하는지 확인한다. (x + 1)이 존재하지 않는다면 답은 Yes가 된다. (x + 1)이 존재하는 경우 A[i] = (x + 1)을 만족하는 i의 최솟값과 최댓값을 각각 l과 r이라고 하자. A[l .. r]에 x를 할당하였을 때 mex가 (x + 1)이 되는지 확인하면 된다. 00:07 AC B - The Butcher h = max(a) or w = max(b)를 만족하여야 한다. 따라서 가능한 (h, w)는 최대 두 가지이다..
Ghudegy 정품 키 필요하신 분?
2023 가지컵 2023 가지컵 www.acmicpc.net A - 가지 교배 흰색 가지만 가지고 있는 조수가 있는지 확인하면 된다. 대회 당시에는 지문이 조금 이상하였는데 출제자의 의도를 파악해서 풀었다. 00:03 AC B - 가지 산사태 1층은 항상 빗물을 받게 되므로 1층만 확인하면 된다. 00:07 AC C - 하이퍼 가지 따기 xor 00:10 AC E - 가지 사진 찾기 가지 사진의 비율이 절반을 초과하므로 가운데 사진은 항상 가지 사진이다. 가지를 가리키는 이름을 알아낼 수 있으므로 가지 사진 번호의 범위는 이분 탐색으로 찾으면 된다. 00:18 AC G - 슬슬 가지를 먹지 않으면 죽는다 mst 00:22 AC F - 가지 이모지 가능한 gcd 값이 얼마 없다는 믿음을 가지고 set으로 풀이하였다. 00..

티스토리툴바