돌이 코딩하는 방

문제 링크 : www.acmicpc.net/problem/3408 문제 힌트 1. 모든 부분 배열에 대해서 non-boring 한지 확인할 수 있을까? 2. 모든 non-boring 한 배열에는 unique한 원소가 존재한다. 더보기 3. unique 한 원소를 포함한 모든 부분 배열은 non-boring 하다. 4. 순서를 잘 바꿈으로써 시간 복잡도를 만족시킬 수 있다. 문제 풀이 -스포 주의- 더보기 우리의 목표는 모든 부분 배열에 대해서 그 부분 배열이 non-boring 한지를 알아내는 것이다. 이에 앞서 우리는 모든 원소에 대해서 그 원소와 같은 값을 가지는 바로 왼쪽 원소와 오른쪽 원소의 위치를 모든 원소에 대해서 저장하고 있을 것이다. 첫번째로 구간을 배열 전체로 설정하자. 이 배열이 non..

문제 링크 : www.acmicpc.net/problem/14636 문제 풀이 호드를 위한 돈. 이 문제를 처음보면 꽤나 직관적이라는 것을 알 수 있다. A그룹에서 숫자 쌍 하나, B그룹에서 숫자 쌍 하나를 꺼내 수 차이의 곱을 최대화 시키는 것이다. 여기서 가장 쉽게 생각할 수 있는 것은 A그룹에서는 숫자쌍이 작을 수록 이득이라는 것과 B그룹에서는 숫자쌍이 클수록 이득이라는 것. 즉 A그룹에 (1,3),(2,5)가 있으면 (1,3)이 상위호환이기 때문에 (2,5)는 절때 답을 만들 수 없으며, B그룹에서도 똑같은 방법으로 답이 될 수 없는 숫자 쌍 들을 고를 수 있다. 이렇게 숫자 쌍으로 묶고 나니까 좌표평면이 생각나게 되었다. 숫자 쌍을 좌표평면 상의 점으로 대입해서 생각하게 되면, 문제를 좀 더 직..

문제 링크 : www.acmicpc.net/problem/13361 문제 풀이 이 문제를 풀기 위해서는 아주 간단하지만 핵심적인 관점 바꾸기를 하나 해야한다. '뒤집어서 생각하기' 우리가 구하고자 하는 것은 가장 긴 세로의 길이의 합이다. 근데 이는 전체에서 가장 짧은 가로 길이의 합을 뺀 것과 같다. 만약 이 문제가 같은 길이로도 이어 붙일 수 있었으면 어땠을까? 굉장히 쉬운 문제가 되었을 것이다. 그냥 모든 판을 길이가 짧은 쪽을 가로로 돌린다. 임의의 정수 집합은 같거나 작아지는 순서대로 배치 할 수 있기 때문에 항상 작은 쪽을 가로로 선택해도 조건에 맞게 해결을 할 수 있게 된다. 하지만 본 문제에서는 같은 길이도 선택을 할 수 가 없다. 이 부분이 핵심이고, 따라서 판들을 같은 길이가 존재하는 ..

문제 링크 : www.acmicpc.net/problem/10806 문제 풀이 step 1 그래프에서 가장 먼저 생각했던 것은 사이클의 관찰이었다. 사이클에서는 어떠한 간선을 한 개 끊어도 임의의 정점에서 다른 정점으로 이동할 수 있다. 또한, 사이클 내의 한 정점이 간선 하나를 끊어도 다른 정점 a에 갈 수 있다면, 사이클 내의 임의의 정점은 간선 하나를 끊어도 정점 a에 갈 수 있다. 이 관찰을 하니까 connecting supertrees라는 문제가 생각났고, 사이클을 하나의 정점으로 치환해야겠다는 생각이 들었다. 처음 주어진 그래프에서 사이클을 계속해서 정점으로 치환하면 트리가 된다. 그 트리에서 최소환의 간선을 추가해서 사이클을 정점으로 바꾸는 연산을 계속 할 때 결국 한 개의 정점만을 남겨야 ..

문제 링크 : www.acmicpc.net/problem/19857 문제 풀이 이 문제를 딱 보고나서, 당연히 이 문제는 greedy or DP 느낌의 문제라고 생각이 들었다. 하지만 조금 더 고민을 해보니 DP라고 할 만한 요소가 하나도 존재하지 않다는 것을 깨달았다. 그리고 나서는 '만들 수 있는 최댓값'이라는 단어에 집중을 했고, 어떤 값이 만들 수 있는지 판별하는 것이 훨씬 쉬울 것 같아 파라메트릭 서치를 쓰는 방향으로 설정하였다. 마지막에 광물 i를 남길 수 있을까? 직접 i를 역추적 해보면서 생각하였다. 어떤 광물 j를 만들기 위해서는 0~j-1가 하나씩 존재하면 된다. j 보다 큰 광물은 하나도 쓸모가 없다. j이상의 광물을 가장 잘 쓰는 방법은 그 광물 하나로 0짜리 광물 하나는 만드는 것..

문제 링크 : www.acmicpc.net/problem/19935 문제 소개 k 판의 게임을 진행한다. 각각의 게임은 m개의 숫자카드중 일부가 있는 n개의 카드 세트에서 1개씩을 뽑는다. 주최측이 원하는대로 수를 선정하고, 그 수와 뽑은 n개의 수의 차이의 절댓값 만큼 점수를 얻는다. 이때 주최측은 얻는 점수가 최소화 되도록 수를 선정한다. 이때 k 판을 진행하면서 얻는 점수가 최대가 되도록 각 판에서 뽑을 숫자카드를 설정하고, 이때 얻을 점수를 구하여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 이 문제를 시작한 이유. 1분 보고 나서 DP 느낌이 확 왔다. 뭔가 난이도의 대부분은 관찰이고, 구현은 그렇게 어렵지 않을 것 같다는 생각이 크..

문제 링크 : www.acmicpc.net/problem/19934 문제 소개 인접행렬이 주어진다. 이때 모든 값은 3이하이다. 이때 주어진 인접행렬을 만족하는 트리가 있는지 판단하고, 있다면 그 트리를 보여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 경로의 가짓수로 가능한 것은 0,1,2,3 인데, 각각의 경우에 대해서 두 노드가 어떤 식으로 배치 되어 있을지에 대해서 생각을 해보았다. 0가지일때: 둘은 같은 컴포넌트에 존재하지 않는다. 또한 0 이 아닌 두 노드는 항상 같은 컴포넌트에 존재해야 한다. 따라서 우리는 경우의 수가 0이 아닌 모든 쌍에 대해서 union &find 를 이용하여 같은 컴포넌트로 묶을 수 있다. 이때 같은 컴포넌..

문제 링크 : www.acmicpc.net/problem/5916 문제 태그 더보기 HLD ,segment tree lazy propagation 문제 풀이 문제를 보자... 1번 트리다. 2번 쿼리가 주어진다. 3번 그 쿼리가 경로 쿼리이다.... 아무리 봐도 이 문제는 HLD를 사용하는 문제라고 밖에는 생각이 들지 않는다. 경로에 모두 하나씩 심기 때문에 segment tree part에서 lazy propagation을 같이 섞어주면 문제를 해결할 수 있을 것 처럼 보인다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 4..

solved 기준 문자열을 너무 안풀었고, 문자열 관련 기초 코딩능력이 딸리는 것 같아서 아래와 같이 검색한 랜덤 문제를 푸려고 한다. 계속 푸는 대로 업데이트 할 예정이다. BOJ 17413 단어 뒤집기 제발 문제 좀 읽자. 1. 전체 뒤집은면 되는 줄 알고 reverse가 끝인줄 알았다. 2. 단어별로 뒤집는 것 인줄 몰랐다. 3. 자잘한 코딩 실수들. 정신좀 차리자. 대회면 망했다. 그래도 줄 입력이 getline(cin,s); 인것은 기억해냈다. 풀이는 입력 종류별로 케이스를 나눠서 뒤집어야 하는 것들은 스택에 담아두면 끝. 닥히 어렵지 않다. 더보기 #include using namespace std; typedef long long int ll; string s; string s2; stack..

문제 링크 : https://www.acmicpc.net/problem/13310 문제 태그 더보기 삼분 탐색, 로테이팅 켈리퍼스, 볼록 껍질 문제 풀이 가장 멀리 떨어진 두 별의 거리가 최소인 날을 구해야 한다. 다시 생각하면 임의의 두 별에 대해서 거리를 구한 후, 그 중 최댓값이 그 날에 대한 수치가 되는 것이다. 문제에서는 각 날별로 두 별의 거리를 구하는 것이지만 일단 관점을 바꿔서 두 별의 거리를 각 날별로 관찰해보자. V자. 이런식으로 나올것이다. 즉, 일정 시점까지는 두 별이 계속 가까워 졌다가, 일정 시점 이후부터는 계속 멀어질 것이다. 혹은 시간 구간 내에서는 계속 감소하거나 계속 증가할 수도 있다. 두 별에 대한 모든 거리 그래프를 겹친 후에 그 중 최댓값을 뽑아낸 그래프 G'를 생각..