profile
군인입니당

오늘의 짬 개인정보 처리방침

개인정보의 처리 목적 <박명훈>(‘https://blog.naver.com/nrg1392’이하 ‘박명훈’) 은(는) 다음의 목적을 위하여 개인정보를 처리하고 있으며, 다음의 목적 이외의 용도로는 이용하지 않습니다.고객 가입의사 확인, 고객에 대한 서비스

2020년 3월 18일
·
0개의 댓글

백준 1315 : RPG

문제 링크dp를 이용해서 해결하였다. 이 문제에서 가장 중요한 점은 힘과 지능이 정해지면, 깰 수 있는 퀘스트도 이미 정해져 있다는 것이다. 따라서 diffi를 힘 i, 지능 j에 도달했을 때, 최대로 찍을 수 있는 스탯의 개수로 정의하고, pointi를 힘 i, 지능

2020년 3월 18일
·
0개의 댓글

백준 1126 : 같은 탑

문제 링크휴가를 보내고 와서 한동안 뜸했는데 다시 시작해야겠다고 본 문제인데 결국 풀이를 봤다. 풀이를 볼 때마다 느끼지만 항상 내가 생각한 거에서 한 발짝만 더 갔으면 먼가 실마리가 잡힐 수 있었을 거 같은 느낌적인 느낌이 든다. 그게 능력인가. 아무튼 그렇다. 최근

2020년 3월 18일
·
0개의 댓글

백준 1016 : 제곱 ㄴㄴ수

문제 링크소수를 이용해서 풀었다. min과 max의 범위가 최대 10^12이므로, 제곱이 되기 위한 수는 10^6까지만 봐줘도 된다. 10^6 까지 소수인 수들은 에라토스테네스의 체를 이용해서 구할 수 있다. 그 다음 이 문제의 특징은 min과 max의 차이가 최대

2020년 3월 18일
·
0개의 댓글

백준 10802 : 369 게임

문제 링크 두 수 a,b가 주어지고, 두 수 사이의 3의 배수이거나 숫자에 3,6,9중 하나라도 들어있는 수의 개수를 찾는 문제이다. 언듯 보면 굉장히 쉬운 문제인거 같지만, 이 문제의 특징은 무려 a와 b가 최대 10^100000이라는 것이다. 완전탐색의 ㅇ도 생각해

2020년 3월 18일
·
0개의 댓글

백준 3033 : 가장 긴 문자열

문제 링크접미사 배열을 이용하는 문제이다. 접미사 배열을 만든 후 lcp를 구하고, 그 중 최댓값을 구하면 문제에서 요구하는 두 번이상 등장하는 부분 문자열 중 길이가 가장 긴 것의 길이 그 자체를 구할 수 있다. 접미사 배열을 구하는데에 O(nlogn^2), lcp를

2020년 3월 18일
·
0개의 댓글

백준 2861 : 원섭동 사람들

문제 링크힘들게 해결했다.처음에 문제를 보고 사이클이 생겼을 때, 조금씩 빚을 상환해서 최소한의 돈으로 상환하는 것을 생각하고 풀었는데, 이 문제는 그런 게 아니라, 돈이 없으면 갚지 않고 있다가 돈을 시에서 지급해주던가, 다른 사람이 갚아서 돈이 생겨야지 일시불로 지

2020년 3월 18일
·
0개의 댓글

백준 2414 : 게시판 구멍 막기

문제 링크쾨닉의 정리를 이용한 문제이다. 먼저 테이프는 겹쳐도 되고, 구멍이 뚫려있지 않은 부분은 테이프를 붙일 수 없다는 문제의 조건에 따라서 붙여야 하는 테이프의 크기를 최대로 해서 테이프를 붙일 가로 테이프, 세로 테이프를 정리한다. 그렇다면 테이프는 최대 n\

2020년 3월 18일
·
0개의 댓글

백준 1561 : 놀이 공원

문제 링크이분 탐색을 통해 해결하였다.시간이 늘어남에 따라 태울수 있는 사람이 증가함수의 꼴로 늘어나므로, 시간이 x일 때 n명 이상을 태울 수 있는가?를 결정함수로 하여 이분 탐색을 적용하는데 문제가 없다. 따라서 n명이상을 태울 수 있는 최소의 시간을 찾아 준 후,

2020년 3월 18일
·
0개의 댓글

백준 9345 : 디지털 비디오 디스크(DVDs)

문제 링크최대, 최소 세그먼트 트리를 이용해서 해결하였다.주어진 문제에서 해결해야 하는 쿼리는 두 가지이다.1.선반 A와 B의 책을 바꿈2.L~R까지 책들이 L~R의 책으로 구성되어 있는지 판단1의 쿼리는 쉽게 해결할 수 있는데, 중요한 것은 2이다. 이 쿼리는 L~R

2020년 3월 18일
·
0개의 댓글

백준 4013 : ATM

문제 링크SCC를 이용하여 해결하였다. 같은 정점, 간선을 여러번 사용할 수 있고, 최대 뽑을수 있는 현금을 계산해야 하기 때문에 어떤 정점에 방문했을 때, 그 정점이 속한 scc를 모두 방문하고 와야 한다. 따라서 scc중 한 점을 방문하는 것은 scc에 있는 모든

2020년 3월 18일
·
0개의 댓글

백준 11062 : 카드 게임

문제 링크최선의 전략을 그리디로 짜보려고 했는데 어려움이 있었다. 그래서 DP를 이용해서 문제를 해결하였다. dpi = 근우의 턴에서 i~j까지 카드가 남았을 때 근우가 가질 수 있는 최대 점수라고 정의한다. 근우와 명우의 턴을 같이 계산하면서 dp를 전개해 나갈껀데

2020년 3월 18일
·
0개의 댓글

백준 1086 : 박성원

문제 링크간단하게 생각해보면 그냥 모든 경우, n!에 대해서 다 계산해주면 될 것 같지만, 15!은 10^12가 넘어가기 때문에 불가능하다. 집합에서 몇개의 수를 뽑으면 그 수들을 어떻게 나열하던간에 총 길이 합은 같다는 사실을 이용해서 비트마스크 dp를 이용하여 해결

2020년 3월 18일
·
0개의 댓글

백준 2336 : 굉장한 학생

문제 링크이 문제는 여기의 d번 문제와 비슷하다 라는 생각을 가지고 대단한 학생인 집합들을 union-find해주면서 해결할 수 있을꺼라는 생각을 하고 접근했지만, n이 7000이하인 D번 문제와는 달리 n이 50만 이하이기 때문에 그런 접근 자체가 불가능했다. 끝없는

2020년 3월 18일
·
0개의 댓글

백준 7469 : k번째 수

문제 링크머지 소트 트리를 연습해보고자 풀어본 문제이다. 세그먼트 트리에서 값이 아닌 배열을 저장해서 관리하는 방식은 처음으로 해보았다. 이 문제에서 k번째의 값을 구하기 위해서는 이분 탐색을 이용하여서 주어진 구간에서 x보다 작은 수들이 k-1개 이하로 있으면 m을

2020년 3월 18일
·
0개의 댓글
post-thumbnail

백준 11266 : 단절점, 11400 : 단절선, 10891 : Cactus? Not cactus?

그래프 단절점, 단절선에 대한 개념을 여기서 접하게 되었고, 연습하는 겸 문제를 풀어보았다.11266 단절점문제 링크주어진 그래프를 DFS트리로 바꾸면서 단절점 여부를 판단할 건데, 어떠한 점이 단절점인지 확인하기 위해서는 그 점의 모든 자식들이 그 점을 이용하지 않고

2020년 3월 18일
·
0개의 댓글

백준 1135 : 뉴스 전하기

문제 링크트리 dp & 그리디를 이용하여 해결하였다.dpi = i의 간접 혹은 직접 부하에게 모두 전화를 돌리는데 걸리는 시간 으로 정의하고, 자식들의 dp값을 모두 저장한 다음, 내림차순으로 정렬한 후, 차례대로 1,2,...씩 더한 값중 최댓값을 그 노드의 dp값으

2020년 3월 18일
·
0개의 댓글

백준 1765 : 닭싸움 팀 정하기

문제 링크1) 내 친구의 친구는 친구다2) 내 원수의 원수는 친구다 이 두 가지를 이용해서 만들어질 수 있는 팀의 개수를 찾는 문제였다. 서로 친구이면 같은 팀에 들어가야 하고, 같은 팀에 속에 있는 사람들끼리도 모두 친구여야 하므로 disjoint set을 떠올릴 수

2020년 3월 18일
·
0개의 댓글

백준 11046 : 팰린드롬??

문제 링크n과 m이 상당히 크므로 어떤 구간에 대해 팰린드롬인지 아닌지를 적어도 O(logn)안에 해결해야 하는데 도저히 모르겠어서 풀이를 찾아보니 처음보는 알고리즘이 있었다. O(n)만에 각 정점을 중심으로 하는 팰린드롬의 최대 길이를 찾을 수 있는 알고리즘이었다.M

2020년 3월 18일
·
0개의 댓글

백준 12016 : 라운드 로빈 스케쥴러

문제 링크세그먼트 트리를 이용하여 해결하였다.다른 사람들의 코드를 보면 펜윅 트리를 이용해서 끝난 작업의 수를 카운트해주어서 해결하였는데, 나도 비슷하게 세그먼트 트리를 이용하였지만, 문제에 나와있는 그대로 lazy propagation이용해서 시뮬레이션하듯이 해결하였

2020년 3월 18일
·
0개의 댓글