✨ Be__Simon 😎

10217 KCM Travel Link 문제 기본적으로는 1 -> N 까지 가는데 걸리는 최소 시간을 구하는 문제이고, 거기에 추가로 M원 이하로 사용해야하는 변수가 추가로 존재한다. 지난번 풀었던 1162 도로 포장 과 굉장히 유사한 문제 접근 edge가 시간을 나타내기 때문에 모두 양수이고, 최단 시간을 구하는 문제이기 때문에 베이스로 다익스트라 알고리즘을 쓸 수 있다. 다만 dp 배열을 2차원으로 만들어서 cost도 고려해줘야한다. 그래서 dp[i][j] = 1 -> i 까지 j 원을 써서 갈 수 있는 최소 시간 을 나타내게 된다. 처음에는 다익스트라 하던대로 min heap을 써서 해결하려고 했는데 시간초과가 나왔다. 왜일까... heap에서 꺼냈을 때 최소값인지도 확인 해줬고, cost 값 이상..

1162 도로포장 Link 문제 기본적으로는 그래프 상에서 1번 -> N번 노드까지 이동하는 최단거리를 구하는 문제이다. 거기에 K개의 도로를 포장해서 소요시간을 0으로 만들어버릴 수 있다는 추가 조건을 고려해야한다. 접근 가중치는 시간 이기 때문에 항상 양수이고 기본 알고리즘은 다익스트라를 사용하면 된다. 거기에 고려해야할 점은 K개의 edge의 weight를 0으로 만들 수 있다 라는 것. 그리고 꼭 K개를 채워서 포장할 필요는 없다. 자주 나오는 문제 유형인데, 다익스트라도 DP 기반이니까 2차원 DP를 쓰면 된다. 2차원 DP 배열에서 row는 node 번호를 가리키고, column은 포장한 도로의 개수를 나타내서 최종적으로 dp[i][j] 는 1 -> i 번 노드로 이동하는데 도로 포장을 j번 ..

2243 사탕 상자 link 문제 풀이 문제를 정리하면 배열에 사탕이 들어있고, 사탕의 맛은 숫자로 표현된다. (최대 2,000,000,000개) A가 1인 query가 들어오면 배열에서 B번째로 맛있는 (B번째로 작은) 사탕을 꺼내준다. (출력한다) 사탕의 맛은 1 ~ 1,000,000 이므로 백만개 길이의 배열을 두고 각 Index에 그 맛을 가진 사탕을 저장하는 방법을 생각해볼 수 있다. 그런 후에 사탕을 꺼내려면 앞에서부터 B번째 사탕의 맛을 찾아 떠나야한다. 그러면 query가 최대 100,000, 배열 최대 길이가 1,000,000이니까... 무조건 시간초과고 더 효과적인 방법을 찾아야한다. 조금만 생각을 바꿔보자. 앞에서부터 B번째 사탕을 찾는다 = 낮은 숫자부터 사탕이 몇개씩 있나 누적합을..

11003 최솟값 찾기 Link 문제 길이가 L인 구간에서의 최솟값을 찾는 문제 문제 접근 세그먼트 트리 일단 처음에는 길이 L 구간에서의 최솟값을 빠르게 구하기 위해 세그먼트 트리 를 이용해서 구현해보았다. 수열 A에서 i번째 숫자를 트리에서 업데이트하는데 logN, 업데이트 후 구간에서의 최솟값을 가져오는데에 logN으로 O(NlogN) 의 시간복잡도를 가진다. # input N, L = map(int, input().split()) arr = [0] arr.extend(list(map(int, input().split()))) MAXN = 5000000 tree = [0 for _ in range(MAXN * 2 + 1)] inf = 1000000000 def query(node, s, e, l, ..

1806 부분합 문제 수열에서 연속된 수들의 부분합 중에서 합이 S이상 이고 길이가 가장 짧은 구간 의 길이를 구해야한다. 접근 간단하게 생각해봤을 때, 수열의 모든 원소들에 대해서 해당 원소로 시작하는 모든 구간을 탐색해보면 가능하긴 하다. 물론 이렇게 하면 O(N^2)로 타임아웃이 날 것이다. (0.5초의 시간 제한..) 어떤 구간의 합 이라고 하면 먼저 세그먼트 트리가 떠오르긴 하지만, 모든 구간을 명시해줘야하므로 이 문제와는 맞지 않는다. (오히려 O(N^2 logn) 일 것 같은데?) 여기서는 간단하게 투포인터 방식으로 O(N) 안에 탐색을 끝낼 수 있다. code N, S = map(int, input().split()) seq = list(map(int, input().split())) s ..

문제 9 x 9 2차원 배열이 주어지면 스도쿠 규칙에 의거해서 빈칸에 숫자를 채우면 된다. 접근법 가로, 세로, 9칸 구역에 같은 숫자가 없는지 판단하고, 넣을 수 있는 숫자를 넣고 다음 빈칸으로 넘어간다. 다음 빈칸에서 불가능하면 원래 빈칸으로 넘어와서 다른 숫자를 넣어본다 (백트래킹) pypy로 하면 통과하는데 python3로 제출하면 계속 시간초과가 난다. 처음엔 빈칸들을 deque로 관리해서 그냥 배열로 변경해보고, 1~9 숫자를 넣을 때마다 중복체크 해주던 로직을 따로 빼서, 가능한 숫자들만 가지고 트래킹을 해봐도 시간초과다. 나머지는 필요한 로직 같은데.. cpp로 하면 되려나 시간초과를 잡는 것 보다 다른 공부를 하는게 생산적일 것 같아 일단은 넘어간다. Code # input board =..

문제 집-치킨집의 거리는 맨하탄 거리로 구한다. ( |x1 - y1| + |x2 - y2| ) 어떤 집의 치킨 거리는 가장 가까운 치킨집과의 거리이고, 모든 집들의 치킨 거리의 합이 도시의 치킨거리이다. 이 때 도시의 치킨거리가 최소가 되도록 치킨 집을 m개 골라야한다. 접근법 1