이 문제는 수학적인 규칙을 찾는게 어려웠던 문제 이다. 규칙을 찾고 나면 코드는 굉장히 간단해서 살짝 허무할 정도다...ㅎ 일단 순서대로 누적합을 구해본다 1 2 3 1 2 의 누적합은 1 3 6 7 9 가 된다 이때 문제를 풀기 위해 가장 중요한 규칙은 M으로 나눈 나머지가 같은 누적합 A, B가 있을 때 A~B까지의 구간의 누적합은 M으로 나누어 떨어진다. 정리하자면 위와 같다 그래서 이를 토대로 각 나머지의 경우의 수를 구하고예를 들어, M이 3이라면 나머지가 0인 경우의 수 중 2개를 고르는 조합의 수, 1인 경우의 수 중 2개를 고르는 조합의 수, 2인 경우의 수 중 2개를 고르는 조합의 수를 모두 더해주면 된다. 정답 코드n,m = map(int,input().split())arr..

문제 이 문제는 사실 문제를 이해하는게 가장 어려웠던 문제였던거 같다 조건이 많고 문제가 한번에 이해되지 않아서 애를 먹었다.. 경사로는 크게 두가지 종류가 있다 내려가는 경사로가 될 조건(1) 현재 좌표가 이전 좌표보다 1 낮다.(2) 현재좌표부터 L개의 좌표의 높이가 같다.(3) 현재 좌표부터 L개의 좌표에 올라가는 경사로가 설치되어 있지 않아야한다 올라가는 경사로가 될 조건 (1) 현재 좌표가 이전 좌표보다 1 낮다.(2) 이번좌표부터 L개의 좌표의 높이가 같다.(3) 이번 좌표부터 L개의 좌표에 올라가는 경사로가 설치되어 있지 않아야한다 이를 바탕으로 구현을 하게 되면 아래와 같은 코드가 나온다 정답코드 #높이차가 1이고 그러한 칸의 길이가 L의 배수일때 1 높일 수 있음# n1: ..

문제 처음 이 문제를 접했을 때 한 정점에서 각 정점까지의 최단거리를 구하는 다익스트라 알고리즘을 써야겠다. 라고 생각을 했는데 문제는이 문제에서 물어보는 것은 왕복 거리라는 거다. 그래서 여기서 구해줘야하는 것은 1. i번 정점 -> x정점 까지의 최단 거리2. x 정점 -> i 번 정점까지 최단 거리 이 둘을 합한 값이 최대인 값을 구해주면 된다. 그러기 위해서는 다익스트라 알고리즘을 모든 정점을 시작 노드로 주고 구해주면 된다. 그리고 1번 + 2번의 값을 정해서 최대값을 찾아주면된다. 정답 코드import heapqn, m, x = map(int,input().split())graph = [[] for _ in range(n+1)]for _ in range(m): s,e,t = ma..

문제 이 문제를 풀기 위해서는 먼저 위상정렬이라는 개념을 알아햐한다 위상정렬이란?위상 정렬(Topology Sort)이란 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미합니다. 진입 차수(Indegree) : 특정한 노드로 들어오는 간선의 개수진출 차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 동작과정은1. 진입차수가 0인 모든 노드를 큐에 넣고2. 큐가빌 때까지 다음의 과정을 반복한다. 1. 큐에서 원소를 꺼내고 해당 노드에서 나가는 간선을 그래프에서 제거한다. 2. 새롭게 진입차수가 0이된 노드를 큐에 넣는다. 이렇게 되면 모든 노드의 방향성을 지켜가면서 순서대로 나열 할 수 있게 된다. 이때 시간 복잡도는 모든 노드를 확인하며 해당 노드와..

문제 처음에 이 문제를 보고 떠오른 알고리즘은 union-find 그리고 다익스트라였다. 하지만 문제가 잘 풀리지 않아 구글링을 해본 후 벨만포드 알고리즘이라는 것을 알게되었다. 참고 자료: https://velog.io/@mjieun/Algorithm-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Bellman-Ford-algorithm-Python [Algorithm] 벨만-포드 알고리즘(Bellman-Ford algorithm) - Python벨만-포드 알고리즘을 통해 그래프에서 최단 거리를 구하고, 음수 사이클 존재 여부를 판단하는 방법을 알아보자.velog.io 벨만 포드 알고리즘이란 특정 출발 노..

문제 처음 이 문제를 접했을때는 배열에서 나올 수 있는 두 수의 합에만 집중을 한 나머지 combination을 활용해서 풀어주려고 했다.그리고 이 풀이는 오답이였다. 왜냐하면 문제를 잘 읽어보면 다른 수 두개의 합으로 나타내는 것이 좋은 수 이다.즉, 본인을 제외한(현재 인덱스를 제외한) 다른 두 수의 합으로 표현될 수 있는지를 찾아주어야 한다는 것이다. 때문에 조합을 이용해서 구해주게 되면 현재 인덱스가 사용된 합인지 아닌지를 알 수가 없기때문에 오답이 발생했던 것이다. 그래서 이를 해결하기 위해서는 투포인터를 사용해서 문제를 풀어주면된다. n번씩 반복해서 현재 인덱스가 배열내에 다른 두 수의 합으로 표현되는지 확인해주면 된다. 풀이import itertoolsn = int(input())a ..

문제   처음 이 문제를 접했을 때는 dp인줄 알았다 어떤 수를 묶었을때 안묶었을 때 모든 경우의 수를 구해서 최대값을 구하는 그런 문제로 생각했는데 생각 보다 간단하게 풀리는 문제였다. 이 문제를 풀기 위해서는 최대값을 구하기 위한 경우의 수를 정리해봐야한다.   1. 양수 * 양수 (큰 애들 순서대로 묶어주면 됨)2. 음수 * 음수 (절대값이 큰 애들 순서대로 묶어주면 됨)3.음수* 0 (음수가 홀수 개 있어서 양수화 할 수 없는 음수가 있을때 0이 있다면 0으로 만들어줄 수 있다)  처음에는 이렇게 정리해서 문제를 풀었는데 오답이 발생했다  또 특이한 성질을 가진 숫자를 처리해주는 걸 까먹었다. 그 수는 바로  1 잘 생각해보면 3*1 보다 3+1이 더 크다. 즉, 1이 있는 경우 1은 양수*양수 ..

문제  일단 이 문제를 보면 연산 횟수인 k의 범위가 100만 이하로 굉장히 크다.그렇기 때문에 연산을 할때마다 정렬을 한다면 무조건 시간초과 가 발생한다는 것을 알 수 있다.  시간복잡도를 최대한 낮게 하면서 최댓값 또는 최솟값을 구하는 알고리즘을 생각하면 heap 이 딱 떠오르게 된다. 근데 문제는 최댓값 최솟값을 동시에 구해줘야한다는 것이다 최대힙, 최소힙 둘 다 구현하면 되는거 아닌가?  할 수도 있지만 최댓값 또는 최솟값을 삭제할 때 서로 어떻게 반영할 지가 이 문제의 관건이다.  이는 heap에 추가 할 때 몇번째  연산인지 정보가 담긴 key 값(몇 번째 연산이 되는지에 대한 정보는 고유하기 때문에 key 값으로 설정해주었다.)을 같이 저장해두어 방문여부를 통해 체크 해주면 된다   visi..

문제 팰린드롬이란?앞에서 부터 읽을 때랑 끝에서 부터 읽을때 똑같은 것 , 회문    이 문제는 시간을 최대한 최적화하는게 관건인 문제이다. 범위를 보면 알겠지만 N의 범위는 2000인 반면에 M의 범위가 100만으로 굉장히 큰편이다.  그래서 100만번 동안 2000개를 확인하면 무조건 시간초과가 나기때문에 어떻게 처리를 해야할지 머리가 아팠던 문제이다.. 하지만 생각의 전환을 해서  미리 최대 길이 2000의 배열에서 발생할 수 있는 부분배열을 전부 확인해두면 시간 복잡도가 100만번 * 2000이 아니라 2000개를 확인  + 100만이 되므로 시간을 줄일 수 있다.  그러면 어떻게 모든 부분배열의 경우의 수를 구하는가?  바로 dp 를 통해서 전부 확인해주면 된다. dp[s][e]가 1이면 s,e..

문제   이 문제는 문제를 이해하는데 오래걸렸던 문제이다....처음에는 단순하게 진실을 아는 사람이 속해있는 파티라면 참여를 못한다 생각했는데 당연히 오답이였다..  문제를 읽으면 알 수 있듯이 진실을 아는 사람이 파티에 속해있으면 진실을 몰랐던 사람도 이 파티에서 지민이가 진실을 말하기때문에 진실을 아는 사람이 된다.  즉, 진실을 아는 사람과 같은 집합이라면 진실을 아는 집합이 되는거다.  이런 패턴 어디서 많이 본 패턴이다. 바로 분리 집합 물론 이 문제는 집합 연산자로도 풀어줄 수 있는 문제이긴하나 Union-Find를 활용해서도 풀어주었다. 기존의 Union-Find는 대소비교로 작은값 또는 큰 값을 기준으로 union을 해줬다면 이 문제에서는 값의 크기를 기준으로 어떤 부모에 합쳐줄지 정하기 ..