\-입출력 제한 사항\-입출력 예시\-문제의 마지막 말최대, 최솟값을 물어보는 문제는 그리디, DP중 하나이다. 그리디, DP 비교하기 => 입출력으로가 and 감이 필요해 + 과거의 정보가 미래에 영향을 끼치면 DP, 안끼치면 그리디그리디, DP는 세트로 풀어보자..
정렬 : 10989
테스트 케이스의 개수를 미리 입력하지 않는 경우는 좀 햇갈릴 수도 있다. 이 같은 경우는 try, except문을 사용해 보도록 한다.
이런 경우 그냥 다음과 같이 하자
위와 같이 풀면 시간 복잡도가 켜져서 망한다. 2차원 배열을 했으면 더 빨리 풀었을텐데
아예 솔루션을 생각을 못했다. 코드를 봐버렸다. 솔직히 아직도 잘 이해가 안간다.
부분 증가 수열이랑 같은 맥락이지만 중간에 합을 초기화 하는 부분을 넣어 주어야 한다.
해결책
해결책
전혀 이런 방식을 생각을 못했다. 당연히 앞에에 다 포함 된다는 말을 믿어야 한다.
sort함수가 x,y알아서 다 정렬해준다.
요소별로 소트하는 방법이 잘 나와있다.
sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들어 sort하는 것 보다 크기 10,000인 리스트를
sorted 함수를 dictionary에 사용하는 방법이다.
평범한 문제라서 insert와 del을 사용해서 리스트를 수정할 수 있지만 0.3초라는 제한된 시간 속에서 너무 많은 시간( O(N) )을 잡아먹게 된다. 그럼으로 커서의 왼쪽 리스트와 커서의 오른쪽 리스트를 만들어 시간이 상대적으로 적은 append와 pop을 이용하
소수인 수 찾기 문제인데 그냥 노가다다. 처음부버 끝까지 다 탐색해야 한다.
처음에는 왤케 시간이 오래걸리지 했는데 생각해보니까 나누는 수를 소수인지 아닌지 확인할 필요가 없던 것이다. 이미 처음부터 소수로 나눠질만큼 나눈 상태에서는 그 다음 배수로도 나누어 질 수 없기 때문이다. 소수 확인까지 하면 시간이 너무 많이 걸린다.
이번 문제는 단순 조합 계산을 하면 어려워진다. 마지막 끝자리가 0이 나오는 개수를 새보려고 하면 2와 5의 조합을 생각을 해야하는데 사실상 어렵다. 아래 코드를 보면 좀 이해가 될란지 모르겠다.
간단한 문제인데 사실 그래프의 형태가 생소해서 잘 풀지 못했다는 점이 있다. 아무튼 처음에 알고리즘이 완벽하고 테스트 케이스도 완벽히 돌아갔는데 왜 틀렸는지 모르겠다. 일단 틀린 코드를 보면이고 맞은 코드를 보면그래프는 항상 저런 형태로 만들어 놔야 편하다.
이전에는 노드투 노드 그래프가 입력이 되면 graph = \[\[0] for i in range(n+1)]처럼 했다면 메모리를 줄이기 위해 새로운 방법을 도입한다. 와 같이 그래프를 만들자. 메모리 부분에서 훨씬 더 효율적이다. 그리고 시간초과.....가 나오면 무조건
처음에는 각 정점마다 사이클의 시작인지 아닌지만 구분하는 방법으로 코드를 구성하였다. 그렇게 하면 근데 각 정점마다 탐색을 해야하므로 시간이 너무 오래 걸린다. 그래서 모든 정점이 사이클의 시작이 아닌 dfs로 사이클을 찾는 순간 다 처리해준다. 그러면 시간이 줄어든다
정말 간단한 문제였지만 그 쉬운 한가지를 생각하지 못했다. 위 같은 경우 최댄 거리를 찾는 문제라 기본적으로 bfs를 사용하고 시작 지점이 둘 이상인 경우 단순히 시작 지점 둘다 큐에 넣어주면 그만인 것이다. 그리고 하나 더 프로그램을 종료싶은 경우 exit(0)를 사
시간 초과가 떠서 풀지 못했던 문제다. 아마 for문을 너무 많이 사용한 것 같다. 수정 후딕셔너리를 적절히 사용하자..... string에는 sort()함수를 사용할 수 없지만 sorted()함수는 사용할 수 있다.
해쉬 문제가 익숙지가 않어 답을 전혀 알지를 못했다.
그냥 어려웠음