키자드에 등록된 deuslovelt의 네이버 블로그 포스트 목록

오랜만에 뛰는 코포라 감이 많이 떨어진 것 같다.B번도 너무 오래걸렸고 C는 이상한 접근 방법만 떠올리다 끝나버려서 D번은 쳐다도 못봄 https://codeforces.com/contest/1459/problem/A한 카드에 두 수가 적혀있고 카드를 배열했을때위쪽과 아래쪽의 값의 크기가 큰 쪽이 이긴다면이길 확률이 높은 쪽을 선택하는 문제이다.위아래가 같은 값을 가진 카드만 N장 있다면 어떻게 배치해도 비길 수 밖에 없음이때 한장을 위쪽 값이 크도록 바꾸면 위쪽 플레이어가 이기게 되고만약 N-2 카드는 값이 같고 나머지 두장은 각각 한쪽이 큰 카드라면 이때는 큰 카드가 앞쪽에 있는플레이어가 승리한다 당연히 이 확률은 같으므로 draw이다.즉 값이.......

BOJ 2651 / 자동차경주대회 [내부링크]

https://www.acmicpc.net/problem/2651딱봐도 dp 스러운 문제인데dp를 잘하지 못해서인지 다익스트라 쪽으로 푸는 풀이가 바로 떠올라시작점 정비소 끝점을 노드로 하고거리상 가능한(두 노드 간 거리가 최대 주행 거리를 넘지 않는) 노드에정비소 비용을 가중치로 하는 간선을 그어 다익스트라를 돌렸다.

CF-div2 edu 100(virtual) [내부링크]

https://codeforces.com/contest/1463오늘도 코포 버츄얼을 하나 돌렸는데 아침부터 배가 아파서 조졌문제가 잘 안풀렸다B번에서 접근이 너무 느렸다.<소스 코드>https://github.com/ohsolution/HPS/tree/main/CodeForce/div2_edu-100https://codeforces.com/contest/1463/problem/A전형적인 A번 문제이고7의 배수 번째 공격 때 모든 몬스터의 피가 1,1,1 이면 된다.진짜 멍청하게 a+b+c -3 에 6을 모듈러 쳤다.당연히 7번째 공격 때 전범위로 공격하는 걸 고려해줘야 하므로6 3 6 3 ... 이런식으로 공격이 이루어지기 때문에9로 모듈러 했을때 6이 나오면 OK 다,단 몬스터가 마지막 공격 때 죽어야 하므로 a,b,c 가 먼저 죽는 경.......

RunningMedian 알고리즘 [내부링크]

사실 알고리즘이라고 하기도 뭐한데전체 set 에 값이 추가되거나 삭제될 때 중앙값을 바로 찾을 수 있는 방법이다.이번 SCPC 2차 예선 B번이 이러한 유형의 문제였다.펜윅트리나 세그트리를 이용해도 이 유형의 문제를 풀 수 있지만이 쪽이 조금 더 간단하긴 하다.이 방법의 기본적인 아이디어는 이렇다두개의 힙(또는 균형이진트리)을 이용해서 전체 값들 중 낮은 값 절반을 내림차순으로 한 쪽에 두고높은 값 절반을 반대편 힙에 오름차순으로 둔다.즉 낮은값들은 최대힙에 높은값은 최소힙에 담는다.그렇다면 중앙값은 항상 최대힙의 top에 위치할 것이므로 바로 알 수 있다.숫자들이 무작위로 들어올 때 이러한 구조를 어떻게 계속 유.......

Knapsack [내부링크]

얼마전 코포 문제에서 냅색을 못한다고 느껴서오늘 knapsack 태그 문제만 풀고있다.물론 dp로 풀리는 knapsack 을 얘기하고 있다.dp는 메모리와 시간을 치환하는 기법이라 생각한다.문제를 푸는 입장에서 보자면 냅색문제는 어떤 정수값의 범위가 메모리에 올리기 좋아보이게 나온다.https://www.acmicpc.net/problem/1472812865,17845 와 동일한가장 기본적인 knapsack 문제이다. 시간 값을 메모리에 올린 후 각 시간에 점수 최댓값을 dp로 계산하면 된다.이때 값이 오염되지 않도록 뒤에서 부터 돌린다.https://www.acmicpc.net/problem/13350데이터 하나에 경우가 세가지 나오는데* 우리팀이 무조건 이기는 경우* 적팀이 무조건 이.......

Codeforces#692 - div2(virtual) [내부링크]

https://codeforces.com/contest/1465/problem/AA번은 간단한 구현 문제였다.(여기서도 끝을 잘못 잡아서 시간 딜레이가 있었다.)https://codeforces.com/contest/1465/problem/BB번은 대회 시간 내에 해법을 떠올리지 못했다.스코어보드를 보고 생각보다 많이 풀려서 풀이가 간단할 거라 생각했고믿음의 for문을 그냥 돌려볼까도 생각했지만 이유가 마땅치 않아서 그냥 넘겼었다.생각해보면 숫자가 바뀜에 따라 자릿수마다 숫자가 바뀌어 버려서 이렇게 핸들할려면 무리가있다.대회가 끝나고 생각해보니 1부터 9까지 최소공배수를 구하면 얼마 안되지 않나 싶었다.계산해보면 2520이 나오는데 결국 최악의 경우에도 2520 번안에 무조건 조.......

2020 천하제일 코딩대회 Open Contest 후기 [내부링크]

요즘은 백준에 올라오는 오픈 콘테스트도 매번 참가중이다.오늘 선린고 코딩대회인 천하제일 코딩대회 오픈 콘테스트를 봤고간략하게 문제를 정리하려고 한다.< 소스코드 >https://github.com/ohsolution/HPS/tree/main/OpenContest/2020%EC%B2%9C%ED%95%98%EC%A0%9C%EC%9D%BC%EC%BD%94%EB%94%A9%EB%8C%80%ED%9A%8CPA 부터 PD 까지는 간단한 구현문제였는데PB,PD 에서 딜레이가 있었다.PB번 문제에서 if문을 중복해서 쓰는 부분에서 문법 상 오류가 있었고PD번 문제에서 가능한 인덱스를 찾을때 시간 조건 상 이분 탐색으로 찾았어야 했는데최소 최대 인덱스 처리 방식이 좀 달라서 lower_bound 와 upper_bound를 쓰는 부분에서 딜레이.......

Codeforces Good Bye 2020 후기 [내부링크]

어제 밤에 커피를 마시면서 사이클을 깨면서 까지 good bye 2020 을 보게 되었다.e번까지 1시간 30분 안에 끝내고 f번이 1시간 30분 남았었는데.문제를 디스크립션 부터 이해하기가 힘들어서 결국 시간내에 풀어내지 못했다.a번 부터 e번 까지 간략하게 정리하자!https://github.com/ohsolution/HPS/tree/main/CodeForce/goodbye2020A. Bovine Dilemma a 번은 간단한 구현문제 였다.0,1 점과 x축의 두점으로 만드는 삼각형의 넓이로 나올 수 있는 모든 경우를 세면 된다.n이 작으므로 이중포문으로 밑변의 길이를 set 에 넣는 방식으로 해결한다.문제 디스크립션에서 non zero area 를 구해야 한다는 설명이 있는데삼각형이 일직선 상의.......