데옴's 기록장

아마 이번에도 본선은 쉽지 않지 않을까 생각이 들정도로 못본거 같다. 1교시는 쉬운데 노가다성이 강한 문제가 아주많아서 그냥 더러웠다.1교시 연습을 좀 했는데 효과가 그래도 있던거 같기도.. 2교시 1번은 그냥 날먹 그리디너무 쉬워서 당황쓰 2번 트리 dp또는 금광세그 비슷하게 풀 수 있다는데.. 암튼 나는 못했다. 3번 r=n일때 긁기 시도, 개같이 멸망 결론: 그냥 망했다.운좋으면 장려는 타려나...

아이디어만 있다면 풀 수 있다 이건가요? 내가 문제 2개를 고르면 상대가 가장 자신 있는 문제 하나를 가져간 후 내가 남은 문제를 가져간다.'나'와 상대는 i 번째 문제에 대해 각각 Ai, Bi 만큼의 자신감 수치를 가지고 있다.내가 문제 2개를 고르지만 정작 문제의 선택권은 상대에게 있다.문제 2개를 적절하게 잘 고르면 최적의 상황을 얻을 수 있다는데.... 당장은 보이지 않는다.우선 문제의 선택권이 상대에게 있다는 것에 초점을 두고 Bi를 기준으로 정렬을 해보자.4 2 8 66 5 7 8  2 4 8 65 6 7 8 여기서 맨 뒤에 있는 문제는 무조건 상대가 가져가는 문제, 맨 앞의 문제는 무조건 내가 가져갈 수 있는 문제임을 알 수 있다.그럼 어떤 식으로 두 개의 문제를 골라야 자신감 수치를 최대화..

여행 갈 때 얼마나 효율적으로 돈을 사용할 수 있는지 생각을 해본 적은 따로 없던 것 같다.가끔 코딩 문제를 풀다 보면 이런 상황을 자주 마주치게 되는 거 같아 나름? 신선한 거 같기도 하고..아무튼 이번 문제는 티어에 맞는 난이도를 가지고 있는 것 같다.  문제 요약을 하자면 지내야 하는 호텔들의 수가 주어진다.각 호텔마다 Pi만큼의 돈을 내야한다.호텔에 한번 숙박하면 1개의 쿠폰을 주고 k 개의 쿠폰이 모이면 호텔을 한번 무료로 숙박할 수 있다.이때 사용해야 하는 최소 금액을 출력하는것이 문제가 원하는 것이다. 당연히 호텔에 숙박할 때마다 쿠폰 개수가 k보다 크면 사용하는 것이 이득이다.문제는 이 쿠폰을 어떤 호텔에서 사용하는것이 관건인 것이다.호텔에 사용할 쿠폰을 정하는것은 최소 힙를 이용해 판별해..

문제가 원하는 것은 마법사가 책을 자지 않고 다 읽을 수 있는지 판별해 주는 것이다.마법사는 책을 읽을 때 즐거움 ai 만큼 소모하고 다 읽으면 bi 만큼 즐거움을 얻는다. 관찰 1. 우선 ai ≤ bi인 책을 읽으면 읽기 전보다 즐거움이 감소하지 않는다. 따라서 이런 책만 읽을 때에는 ak가 작은 순서대로 읽으면 된다. 관찰 2. 다음으로 ai > bi인 경우이다. 이 경우 책을 읽을 때마다 즐거움이 감소한다. 따라서 책을 거꾸로 읽는 방법을 생각해 보면 되는데 이 경우에는 관찰 1번과 같은 방법을 사용하면 된다. 그렇기에 bi가 큰 순서대로 읽으면 된다. 이제 즐거움이 감소하지 않는, 이득이 되는 책을 전부 읽은 후 이득이 되지 않는 책을 읽으며즐거움이 0 밑으로 떨어지는지 확인하면 정답을 구할 ..

오랜만에 푼 재밌는 골드 그리디 문제였다.쉬운 문제여서 정신적 건강에 많이 도움이 되었다. 문제에 정점이 N개, 루트노드가 1인 트리가 주어진다.각 노드에는 가중치가 있고 i(1모든 리프노드는 자신의 부모노드보다 가중치의 크기가 작거나 같기 때문에 루트노드에서 인접한 노드들을 선택하는 상황이 가장 큰 이득을 볼 수 있게 만들 수 있다. 즉, 루트노드를 우선순위큐에 넣고, 그 루트노드에 연결된 노드들을 우선순위큐에 넣으면서 계속 관리하면 각 상황마다 얻을 수 있는 가치의 크기가 최대가 된다.  사실 그리디라기보다는 bfs에 가까운 문제였다.

그냥 문제가 너무 길다. 문제를 요약하자면 모든 정점들이 어느 한 정점으로 연결되어 있는 트리가 있고 두가지 쿼리가 주어진다. 1. 두 정점의 간선을 끊는다 2. 선택한 정점과 연결된 정점들의 개수를 센다. 일반적인 방법으로는 문제를 해결하기에는 어려워보인다. 1번 쿼리는 n-1개 들어오기 때문에 최종 상태에서는 모든 정점들이 서로 연결되어 있지 않음을 알 수 있다. 그러면 여기서 쿼리를 거꾸로 수행해보고 싶은 생각이 들 수 있다. 간선을 끊는 쿼리를 구현하는 것은 어려우므로 쿼리를 거꾸로 실행하게 되면 간선을 추가하는 쿼리로 바뀌게 된다! 여기서 바로 유니온 파인드를 사용할 수 있다. 1번 쿼리가 들어오면 두 정점을 유니온 하고 2번 쿼리가 들어오면 연결된 정점들의 개수를 세어주기만 하면 된다. 정점들..

디미고에 와서 1순위 목표는 해킹을 배우는 것이었다. 나는 선배들의 추천으로 리버싱을 해보게 되었고 리버싱을 가볍게 공부한 후 기초문제들을 풀어보았다. 처음에는 막막했는데 친구랑 같이 그냥 머리박고 하니까 잘 풀리더라ㅋㅋ rev-basic 0 그냥 ida로 디컴파일 하면 바로 플래그를 준다. rev-basic 1,2 함수 안에 보이는 문자들을 나열하면 플래그를 얻을 수 있다. rev-basic 3,4,5,6,7,8 함수안에서 암호화?가 이루어지는 것 같다. 이걸 잘 분석해서 역연산을 하는 방법도 있지만 n의 범위가 매우 작기 때문에 그냥 브루트포싱을 해도 된다. 나는 3~8의 모든 문제를 브루트포스로 해결했다. 사실 이 문제들은 그냥 알고리즘적인 사고가 어느정도 된다면 매우 쉽게 풀 수 있었다. 앞으로 ..

3/3, 방학이 너무 짧았던 것 같다. 눈 한번 감았다 뜨니 벌써 기숙사 입소일.. ㅠㅠ 한편으로는 디미고인으로서 기쁜 마음이었지만 막상 몸은 거부하고 있었다ㅋㅋ 기숙사에서 살아남기(희망편) 기숙사에서 첫날밤을 보냈다. 오전 6시 30분에 기상하고 35분에 아침점호를 한다. 1학년은 7시 40분 퇴실이라 시간이 아주 많이 남아서 여유롭게 준비하고 나갈 수 있다. 사실 다시 자러 간다. 아침기상곡이 매일 바뀌는데 첫날에는 "밤양갱"이라는 노래가 나왔다. 이제 이 노래만 들으면 기숙사 첫날밤이 머릿속에 생생하게 떠오른다..(좋은 건가) 기숙사 생활은 생각보다 재밌다. 단점이라면 겁나 피곤하다는 점? 그것만 제외하면 호실친구들과 함께 중학교 썰 푸는 게 개꿀잼이다. 일주일도 안 지났는데 벌써 어질어질한 드립들..

고등학교에 가면 필요한 물품들 중 가장 중요한 노트북과 태블릿을 사게 되었다. 내가 구매한 제품은 갤럭시 북 4 Pro, 갤럭시 탭 s9이다. 먼저 노트북에 대해 알아보자! 간단하게 중요한 스펙만 정리하면 이렇다. 제품 스펙: CPU: Intel Ultra 7 155H GPU: Intel Arc graphics RAM: 16GB SSD: 512GB 노트북은 한 달 정도 사용하고 있는데 나름? 괜찮은 성능이었다. 첫 부팅후 생각보다 많이 버벅거려서 불량인 줄 알았지만 그냥 최적화가 덜 되어 있었던 거였다ㅎㅎ. 시간이 지나니 심하게 버벅거리는 건 없어졌다. 가장 큰 16인치 모델로 샀지만 기존에 워낙 큰 모니터를 사용해서 그런지 너무 작게 느껴졌다. 그래도 전반적으로 매우 준수한 성능을 보여줘서 잘 사용하고..

2/20에 2차 진단고사를 보고 왔다. 원래는 1차 진단고사, 2차 진단고사를 나눠서 쓰려고 했지만 까먹고 2차 진단고사를 보고 나서 함께 후기를 올려본다 ㅋㅋ. 1차 진단고사 때 본 과목은 국어,영어,수학이다. 분명 공지받은 시간표에서는 국어,수학,영어 순으로 시험을 본다고 했지만.. 아니었고.. 1/17, 1차 진단고사. 매우 평범하게 잘 본줄 알았지만 수학에서는 계산실수를 한것 같.. ㅠㅠㅠ, 영어는 뭐.. 입꾹닫 그래도 국어라도 잘봐서 그래도 덜 우울한듯 하다 크흡.. 전반적으로 문제 난이도는 쉬웠지만 어째서인지 문제가 많았다.. 2/20, 2차 진단고사. 2차 진단고사는 아직 결과는 나오지 않았지만? 생각보다 잘 본 느낌을 받았다. (영어 제외) 1차때와는 다르게 정보 시험이 추가되었는데 파이썬..