문제 설명제한사항 및 입출력풀이정말 괴랄한 제한사항을 가지고 있다. 만약 주어진대로 2차원 배열을 만들어서 슬라이싱한다면 n^2이 걸리게 된다. 10^7^2 = 10^14이므로 택도 없다.사실 그냥 단순히 2차원 배열을 1차원 배열로 매핑해주면 된다. 연속된 구간이기 때문에 문제없이 매핑해줄 수 있다. (행, 열) 기준으로1차원 -> 2차원: [(i // n), (i % n)]2차원 -> 1차원: row * n + col % n으로 인덱스를 매핑할 수 있다.내 코드def solution(n, left, right): ans = [] for i in range(left, right + 1): row = i // n col = i % n ans.append(m..

문제 설명제한사항 및 입출력풀이분리되어있는 그래프가 몇 개인지 찾는 전형적인 그래프 탐색 문제이다.첫 번째 노드부터 bfs를 돌려서 이미 방문한 노드에 대해서는 visited를 체크하고 한 번의 그래프 탐색이 끝날 때마다 ans를 올려서 풀이해주었다.내 코드from collections import deque def solution(n, computers): # visited와 ans를 전역에서 관리 visited = [False] * n ans = 0 def bfs(graph, visited, start): nonlocal ans queue = deque([start]) visited[start] = True while..

문제 설명제한 사항 및 입출력풀이전형적인 DP 문제이다. 첫 번째 칸부터 선형적으로 순회하며 칸에 도달할 때마다 이전 칸에 도달하는 방법들을 모두 더해주면 된다. dp테이블의 정의는 다음과 같다.dp[i] = i칸에 도달할 수 있는 경우의 수내 코드def solution(n): dp = [0] * n # n이 1일땐 1반환 if n == 1: return 1 dp[0] = 1 dp[1] = 1 for i in range(n-1): dp[i+1] += dp[i] try: dp[i+2] += dp[i] except: continue return dp[-1] % ..

문제 설명제한사항 및 입출력풀이처음 문제를 봤을 때 dp와 dfs가 생각났다. 먼저 dfs 풀이는 각 숫자마다 -, + 두 가지 경우의 수를 모두 탐색하면서 내려가는 경우이다. 내려가면서 남은 모든 수를 더하거나 뺐을 때 목표 숫자가 나오지 않는다면 가지치기해주어서 최적화해줄 수 있다.내 코드def solution(numbers, target): ans = 0 n = len(numbers) # 가지치기를 위한 누적합 배열 suffix = [0] * (n+1) for i in range(n-1, -1, -1): suffix[i] = suffix[i+1] + numbers[i] def dfs(idx, total): nonlocal ans ..

문제 설명입출력 및 제한사항풀이문제 요약은 다음과 같다. n × m 도화지에 잘못 칠해진 칸의 좌표가 주어진다. 한 변 길이가 같은 정사각형 색종이를 최대 k장 사용할 수 있고, 색종이는 도화지의 아래 변에 붙여서 사용한다. 모든 잘못 칠해진 칸을 가릴 수 있도록 할 때, 필요한 색종이의 최소 한 변 길이 s를 구하는 문제이다. 항상 도화지의 아래 변에 붙여서 사용하기 때문에 y 좌표는 생각하지 않아도 된다. 아래 붙여서 사용했을 때 x축에서 가장 멀리 떨어져있는 y좌표의 값만 넘긴다면 x 좌표만 생각하면 된다. 뭔가 이분 탐색하기엔 범위가 너무 좁아서 긴가민가했는데 다른 효율적인 풀이가 마땅히 생각나지 않아 이분 탐색으로 풀이했다. 탐색 조건은 종이의 크기이고 중앙값이 모든 좌표를 커버한다면 종이가 더..

문제 설명입출력 및 제한사항풀이 문제 요약은 다음과 같다. 건물은 1부터 N, 도로는 무가중치 양방향(이동 시간 = 1), 치킨집 두 곳을 정해 모든 건물에서 더 가까운 치킨집까지 이동하는 시간의 합(왕복)이 최소가 되게 하는 문제이다. 만약 합이 같은 후보가 여러 개면 건물 번호가 더 작은 쌍(A가 작을수록, 같다면 B가 작을수록)을 택한다. 모든 건물에 대해서 최단거리를 알아야하기 때문에 플로이드-워셜로 최단거리를 구하고 모든 쌍에 대한 최단거리의 왕복을 계산해주었다. 크게 알고리즘적으로 필요하다기보단 구현만 주의해서 해주면 될 것 같다! 코드를 확인해보자. 내 코드import sysinput = sys.stdin.readlinemis = lambda: map(int, input().split())I..

문제 설명 입출력 및 제한 사항풀이문제를 요약해보자면, 벽이 있는 위치에서 시작해서 시작 위치의 벽이 부숴졌을 때 이동할 수 있는 공간의 넓이를 계산하는 문제이다. 사실 별 생각 없이 n, m이 1000이라서 모든 위치를 start 배열에 넣고 bfs를 돌렸다가 시원하게 시간초과 받았다... 해당 풀이에서 시간 초과가 나는 경우는 다음과 같다111111...1111110000...000110000...0001.....111111...111111만약 이렇게 생긴 1000*1000 matrix가 있다고 치면 모든 벽(4000)에서 998*998인 영역에 대해 bfs탐색을 하게 되고 4000 * 1000*1000 이라는 O(n^3)의 시간 복잡도가 나오게 된다. 따라서 중복된 공간을 탐색할 땐 또 계산하지 않..

문제 설명제한사항 및 입출력풀이문제 요약은 다음과 같다. 각 도시에서 광고에 cost원을 쓰면 people명의 고객을 얻는다. 최소 C명 이상의 고객을 모으기 위해 써야 하는 최소 비용을 구하라. 같은 도시는 여러 번 사용할 수 있다.전형적인 배낭 문제이다. 핵심은 “같은 아이템(도시)을 무한히 쓸 수 있음” -> 완전 배낭 형태이다. 또한 “정확히 C명”이 아니라 “C명 이상”을 만족하면 된다.직관적으로 봤을 때 그리디로도 접근할 수 있을 것 같이 생겼지만 초과분의 존재 때문에 최적해를 보장할 수 없다. dp테이블의 정의는 다음과 같이 내렸다.dp[i] = i명을 모으는 데 드는 최소 비용또한 초과해서 모아도 되기 때문에 한 번에 모을 수 있는 최대 비용을 여유분으로 넉넉하게 지정해주었다.내 코드imp..