문제 설명제한사항 및 입출력구역의 개수가 5 * 10^6이고 쿼리의 개수가 10^6로 꽤나 많다.풀이총 세 가지의 연산이 있다. 1번 연산은 명소 토글, 2번 연산은 이동, 3번 연산은 가장 가까운 다음 명소찾기.첫 번째로 신경써야 할 연산은 시계방향으로 몇 칸 움직여야 명소를 찾을 수 있는지이다. 이 구현은 첫 번째 명소가 나올 때까지 그냥 돌려서는 시간초과가 난다. 만약 구역이 희소하거나 없다면 하나하나 구역을 찾는 연산은 5 * 10^6의 시간을 갖는다. 시간 제한이 1초이므로 단순히 생각해봐도 100번만 반복해도 시간초과가 난다. 여기서 시간을 줄여야하는데 가장 적합한 방법은 이진탐색이다. 그냥 배열로 장소를 표현하면서 명소를 토글하는 방식으로 1번 연산을 수행한다면 1번 연산은 수행하기 편하지만..

문제설명제한사항 및 입출력풀이두 가지 색상으로 노드를 칠하는데 색상이 연속되지 않도록 칠하는 문제이다.생각해보면 사이클이 없다면 두 가지 색상이 겹칠 일이 없다. 불가능한 경우는 사이클이 있고 사이클 내부 노드의 개수가 홀수인 경우이다.하지만 이런 복잡한 조건을 생각하지 않아도 그래프를 탐색하며 1, 2로 칠해나가다가 다음 노드가 이번 노드와 같은 색이라면 불가능! 이라고 판단하면 된다.그리고 모든 노드를 출발지점으로 고려해보아야한다. 주어진 노드가 전부 연결되어있지 않은 경우가 있기 때문에 여러 그래프가 생겼을 때 모든 그래프를 확인해야한다. (이거 고려 안 했다가 한 번 틀렸다..)내 코드bfs 풀이def bfs(start, visited): queue = deque([start]) vis..

문제설명제한사항 및 입출력이 문제는 서브태스크가 있는 문제이다. 하지만 신경쓰지 말고 한 번에 100점을 받아보자!풀이좌표평면 위의 두 직사각형이 어떤 위상으로 교차하는지를 판별하는 문제이다.별 생각없이 문제를 봤을 땐 전체 좌표평면을 0으로 초기화한 후 직사각형의 범위를 1로 칠하면서 2의 개수(겹쳐진 면적)를 확인하려고 했는데 좌표의 범위가 무려 -1e9 ~ 1e9이다! 절대로 이 방법으로는 풀 수 없다는 것을 직감한 후 다시 생각해보았다. 결국 직접 비교하는 구현은 엄청 넓은 사각형이 주어지게 된다면 필연적으로 시간초과가 난다. 주어지는 두 좌표(왼쪽 하단 꼭짓점, 오른쪽 상단 꼭짓점)만 가지고 한 번에 비교할 수 있는 방법이 있을까 고민했다.x축에서 겹치는 구간 범위와 y축에서 겹치는 구간 범위를..

문제설명제한사항 및 입출력 풀이문제를 잘 읽어보면 제한사항에 k번째 회의는 k-1, k+1과 겹치지만 다른 회의랑은 겹치지 않는다는 것을 알 수 있다. 해당 조건으로 회의의 시작 시간, 종료 시간은 필요가 없어지는 정보가 된다. 핵심은 인접한 것을 선택하지 못한다는 것이다. 기초적인 dp 문제라고 생각했다. 현재 값을 선택하거나, 선택하지 않거나.dp[i] = i번째 회의까지 진행했을 때 최대 인원상태전이: max(해당 회의를 선택했다면 i-2 + 현재, 해당 회의를 선택하지 않았다면 i-1)내 코드import sysinput = sys.stdin.readlinemis = lambda: map(int, input().split())n = int(input())num = []for _ in range(n)..

문제 번호도 4자리 숫자이고 문제 제목도 4자리 숫자이니 뭔가 헷갈린다. 문제설명제한사항 및 입출력제한시간은 1초로 약 1억번의 연산 안에 정답을 도출하면 된다. 테스트 케이스의 개수가 20개까지 주어지고 각 테스트케이스마다 500만번의 연산을 넘기지 않으면 된다.풀이시간 복잡도가 굉장히 널널하기 때문에 각 4자리 숫자를 분리 후 최대, 최소로 재조립하여 빼주는걸 6174가 나올 때 까지 반복하는 방향으로 생각하였다. 내 코드def find_minmax(num): min_num_list = ['0', '0', '0', '0'] max_num_list = ['0', '0', '0', '0'] for i in range(4): try: min_num_list[..

문제설명 제한사항 및 입출력풀이문제의 제한사항을 확인해보면1 1 으로 제한되어있다. 따라서 모든 던전의 순서를 확인해도 8!이기 때문에 굉장히 작은 것을 알 수 있다. 그러므로 간단하게 permutations을 활용하여 모든 경우의 수를 확인하고 가장 큰 값을 리턴하는 완전탐색으로 구현했다. 내 코드가지 못하는 곳은 break를 해주면서 빠르게 제외시켜주었다. 실제로는 던전의 개수가 8개일 때 8!에 던전의 개수만큼 한 번 더 반복하기 때문에 8! * 8인 것을 확인할 수 있다. 약 32만이라는 작은 숫자이므로 간단하게 통과할 수 있었다. 고찰내가 생각한 코드의 시간복잡도는 O(n * n!)로 매우 크다.던전의 개수가 12개만 넘는다고 해도 5억에 가까운 숫자이므로 완전탐색은 힘들 수 있다. 1. 정렬을..