14284 : 간선 이어가기 2접근처음엔 단순하게 간선과 가중치가 나오길래 최소 신장 트리를 생각했었다. 하지만, 모든 정점을 연결하는 것이 아닌 특정 정점 두 개만 연결시켜야 했고 최소신장트리로는 풀 수 없음을 느꼈다. 그 다음으로 생각한 것은 유니온 파인드인데, 이것도 두 정점을 연결했을 때 최소 비용임을 보장할 수 없다. 마지막으로 생각한 것은 다익스트라였다. 모든 정점을 다 고려해도 두 정점 간의 최소 비용으로 연결을 보장한다.간선 연결 과정에서 최악의 형태는 1자형태로 쭉 뻗은 그래프 형태가 되는데, 그렇게 되면 간선이 N - 1개가 된다. 그렇다면 최대 100,000개의 간선에는 중복이 있을 수 밖에 없다. 따라서, 그래프 저장시 가중치가 더 낮은 간선 취하면 될 듯 싶었다.풀이풀 때는 중복되..
Problem Solving
접근예전에 도전했다가 실패했었던 문제.12345BBE, YBEA, YABEAA, YAA, BEK, YKBEAAD, YAAD, BEKD, YKD, BEAN, YAN만약 1≤ code[i - 1] * 10 + code[i] ≤ 26라면, dp[i] = dp[i - 2] + d[i - 1]아니라면 dp[i] = dp[i - 1]풀이다른 분들 풀이를 참고하니 좀 더 간단한 방법도 있었다. 특정 조건을 만족할 때만, 값을 더해주는 방식이다. 만약 현재 자리가 0이 아니라면 일단 문자로 만들 수 있다. 따라서, 바로 직전에 만든 문자열에 문자 하나를 추가하면 된다.이를 식으로 나타내면 아래와 같다.for idx in range(1, len(code)): if code[idx] > 0: dp..
접근평범한 BFS 문제라고 생각했는데 조금 다른 부분이 있었다. 기존에 많이 풀어봤던 땅 문제들과 다르게 단순히 땅의 개수가 아닌 가장 높은 높이를 기준으로 땅을 세는 방식이다. 초반에 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야 한다 이 부분을 잘못봐서 조금 헤멨다. 결국 생각해보니 특정 지점이 가장 높다면 산봉우리로 볼 수 있다는 것으로 해석이 가능하다. 그러려면 순차 탐색으로는 찾기 어려울 수 있다. 왜? 산봉우리라고 생각했던 지점이 실은 인접한 격자일 수 있기 때문이다. 그렇다면 '차라리 값을 기준으로 최대힙으로 저장해놓고, 이를 꺼내서 사용하는 방법은 어떨까?'하는 생각이 들었고 이 방향으로 진행했다. 여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정..
접근처음에는 ((A % M) + (B % M)) % M = (A+B) % M 을 사용하는 문제라고 생각했다. A + B == C일 때, ((A % M) + ((C - A) % M)) % M = C % M를 활용하면 될 것 같았는데, 수가 최대 1,000,000,000까지이므로 인덱스를 어디로 잡는지가 문제였다. 제한 시간이 초과되었고, 알고리즘을 확인해보니 유클리드 호제법이 있었다. 이전에도 몇 번 접했지만 자주 쓰지 않을 거라고 판단해서 그 때 그 때마다 찾아서 확인했었다. 자주 접하게 되어서 아예 에라토스테네스의 체처럼 기억을 해둘 필요를 느꼈다. 유클리드 호제법두 양의 정수 a, b(a > b)에 대하여 a = bq + r (0 ≤ r gcd(a, b) = gcd(b, r) 반복문 방식def euc..
