열심히해보겠씁니다

대표적인 LCA(최소 공통 조상, Lowest Common Ancestor) 문제이다. 정점을 트리로 만들고 두 노드 사이의 거리를 구하는 건 간단하다. 한 정점에서 출발해서 트리를 타고 가장 단거리로 다른 노드에 도착하기만 하면 되는 문제이기 때문이다. 하지만 이 문제는 2초의 시간 제한이 있고, 1만 개의 질문이 주어지므로 한 질문 당 20000 번 이하의 연산을 해야 한다. (왜냐하면 1만 x 2만 = 2억이기 때문에 C++ 에서 러프하게 2초로 잡을 수 있다.) 노드가 최대 4만개이기 때문에, 재수 없게도 일자로 쭉 펼쳐진 ㅡㅡㅡㅡㅡㅡㅡ 이런 트리일 때 양 끝의 노드만 계속 묻는다면 반드시 시간 초과가 뜬다. 물론 이런 극한의 케이스가 아니어도 보통은 시간 초과가 뜬다. 평균적으로 떨어져있는 기대..

모든 집의 치킨 거리의 합이 가장 작게 되도록 치킨집 M 개를 고르면 된다. 조금 더 빠르게 하기 위해서 각 집과 치킨집의 거리를 distmap [집][치킨집]으로 정해놓자. 이때 집과 치킨집을 지도에 직접 뿌릴 필요는 없다. 우리가 볼 건 지도를 직접 볼 필요가 없고 좌표만 가지고 계산하면 되기 때문이다. 그 후 완전 탐색을 이용하여 모든 경우의 수를 살핀다. 이 때 치킨집은 M개만 남기기 때문에 M개를 고른 후 distmap을 순회하여 가장 작은 값만 남기고 Min 값을 찾으면 된다. 집이 최대 2N = 100개고 치킨집이 M = 13 개 이므로 경우의 수는 13C5 * 100 * 13 이므로 시간이 오래 걸리지 않는다. #include int n,m; int ch, h;//치킨집 개수, 집 개수 i..

가장 긴 증가하는 부분 수열 시리즈 중 난이도가 높은 5이다. 일반적인 방법으로 풀 수 없는 제한 조건이 있다. 수열의 크기가 100만이고, 숫자가 -10억부터 10억까지이므로 기존에 2에서 쓰던 방법들은 시간이 너무 오래 걸린다. 배열을 한 번 순회하면서 O(N) 논리적으로 저장하는 방식이 O(logN)이라면 NlogN ~ 2천만 회 정도로 1초 안에 풀이가 가능하다. 사용할 방법은 백트레킹이다. 이름이 어려워 보이지만, 단순히 내가 한 행동을 저장해 놓고 나중에 다시 꺼내보겠다는 얘기이다. 방식은 다음과 같다. 1. 주어진 수열(A)을 순회한다. 2. 가장 긴 부분 수열을 저장하는 수열(B)에 저장한다. 3. 가장 긴 수열이 저장되었다면, 저장한 값이 A에서는 몇 번째인지 백트레킹으로 추적한 후 저장..

기초적인 파이썬과 자바의 문법을 익히기 위해 알고리즘 문제를 풀어보기로 했다. 어려운건 힘들기 때문에(c로 해도 힘든데...) 쉬운 실버부터 차근차근 풀어보도록 하자. 위 문제는 알파벳이 연속적으로 오느냐(1개만 있어도 ok) 혹은 알파벳 사이에 다른 종류의 알파벳이 껴있느냐를 묻는 문제이다. 즉, aaabbbcdd 같은 형태는 가능하고, aaabbbaaa 같은 형태는 불가능하다. 주어진 입력에서 그룹 단어의 개수를 체크하여 출력하면 된다. 자바와 파이썬 코드의 풀이 방식은 동일하다. 1. 입력받은 단어에서 a~z까지 하나씩 확인한다. 2. a를 확인한다면 index를 찾아서 연속되는지 (next-prev==1)인지를 확인하고 연속하지 않고 떨어져있다면 세지 않는다. 파이썬 코드 def group(s:s..