주의점 1. dp구성은 다음과 같다 dp[i][j] : 알고력이 i, 코딩력이 j를 얻기위해 걸리는 최소시간 2. 1시간 이후일 때 if now_alp != max_alp: dp[now_alp + 1][now_cop] = min(dp[now_alp][now_cop] + 1, dp[now_alp + 1][now_cop]) if now_cop != max_cop: dp[now_alp][now_cop + 1] = min(dp[now_alp][now_cop] + 1, dp[now_alp][now_cop + 1]) 3. 문제를 이용할 때 * 문제를 통해 개선된 알고력과 코딩력이 max를 넘어가면 안되는것에 주의 for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:..

풀이 https://sosoeasy.tistory.com/540 에서 숫자 두개의 특정합을 구했다면 이번문제는 세 숫자를 구한다. 풀이법은 다음과 같다. 1. 제일 왼쪽 숫자(first)를 잡는다 2. first 오른쪽 부분에서 투포인터를 적용한다 first left right -2 6 -97 -6 98 3. 1. first를 전체에 대해서 O(N)번, 2.투포인터 부분이 O(N)이므로 O(N^2)으로 풀린다. (N은 최대 5000이므로) 소스코드 import sys N=int(input()) L=list(map(int,sys.stdin.readline().split())) L.sort() min_sum = 9876543210 ans=[0,0,0] for i in range(N-2): first = ..

풀이 정렬되어 있는 수열에서 특정합을 구하는 문제류는 투포인터를 떠올리자 1. 숫자를 정렬한다. 2. 양쪽 끝에 숫자를 시작 left, right로 잡는다 3. 두 숫자의 합의 절댓값이 min보다 작으면 min을 갱신 4. 두 숫자의 합이 음수이면 left를 +1, 양수이면 right를 -1, 0이면 바로 종료 소스코드 import sys N=int(input()) L=list(map(int,sys.stdin.readline().split())) L.sort() left = 0 right = N-1 min_sum = 9876543210 ans=[0,N-1] while(left

upperbound, lowerbound 1. 정의 upperbound : 처음으로 target 초과의 값이 나오는 것! lowerbound : 처음으로 target 이상의 값이 나오는 것! 2. 예시 target이 3일때 lowerbound numbers upperbound 5 v 3 3 v 3 2 1 3. 문제에서의 활용 대부분의 lowerbound, upperbound 문제는 trade-off 관계에 있는 두 값(1.최소최대화 조건, 2.제한조건)이 주어진다. 이를 표로 정리하면 다음과 같다 lowerbound 1. 최소최대화 조건 2.제한 조건 upperbound c 5 v b 3 3 v a 3 2 1 제한조건=3에서 최솟값을 찾아야 하면 lowerbound를 사용하여 최솟값인 a를 찾고, 최..

풀이 일반적인 dfs문제인데 재귀를 타는 함수의 파라미터의 타입에 따라 시간초과가 발생하는 문제였다. 소스코드1 (시간초과) dfs로 재귀가 들어갈때, visited라는 리스트를 파라미터로 쓰면 함수를 호출할때 계속 리스트를 달고 다녀야 한다 이 부분이 시간이 오래 걸린것으로 보인다 import sys N,M = map(int,input().split()) graph={i:[] for i in range(N)} for i in range(M): a,b = map(int,sys.stdin.readline().rstrip().split()) graph[a].append(b) graph[b].append(a) ans=0 def dfs(node,visited): global ans # print(node,vis..

1. 풀이 visit 리스트를 갱신을 queue에서 pop된 다음 해주면 된다. 그렇게 하면 x위치까지 최단시간에 도착하는 경로의 수 만큼 큐에서 pop이 된다. 그러니까 임의의 위치까지 가는 최단경로(최단시간)는 q에 계속 보존이 된다. 일반적인 bfs문제처럼 조건확인후 아래와 같이 visited[loc]==-1일때 visited[loc]=visited[loc+x]+1 하면 처음으로 찾은 최단경로 외에 다른 최단경로는 q에 안들어간다. 2. 소스코드 from collections import deque maxNum=100000 N,K=map(int,input().split()) visited=[-1 for i in range(maxNum+1)] q=deque([(N,0)]) case=0 T=maxNum..

1. 풀이 (1) 시간복잡도 그냥 풀면 정말 간단한 백트래킹 문제이지만 시간이 O(2^(N*N)) 이므로 초과이다. 해법은 체스판의 특성을 생각하고 하얀색 체스판에 채울 수 있는 최대의 비숍과 검은색 체스판에 채울 수 있는 최대의 비숍을 각각 따로구해서 더해주는 것이다. 이렇게 하면 시간복잡도는 아래와 같이 된다. O(2^(N/2*N/2)+2^(N/2*N/2))=O(2^(N/2*N/2)) (2) N이 짝수일 때 주의사항 N이 홀수이면 확인할 블럭이 아래와 같이 2씩 증가하지만 0 3 5 7 9 N이 짝수이면 확인할 블럭이 마지막 or 마지막 바로앞 열에서 3 or 1씩 증가해야 한다 0 2 5 7 8 10 13 15 따라서 이를 유의해서 탐색을 해줘야한다! 2. 소스코드 dR=[-1,-1,1,1] dC=..

구글링 해보니 4차원 dp를 이용해서 푼사람들이 많았다. 나는 안똑똑해서 dfs를 이용하여 풀었다. 1. 풀이 [백준]4991 로봇청소기(https://sosoeasy.tistory.com/24) 문제와 유사하다. 아래의 순서를 따른다. (1) 현재위치에서 남아있는 모든 C까지의 거리를 bfs를 통해서 구한다. (2) (1)에서 구한 모든 경우에 대해서 해당 점을 시작위치로 하여 dfs를 한다. 2. 소스코드 INF=9876543210 from collections import deque dR=(-1,0,1,0) dC=(0,-1,0,1) N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) def bfs(case,q,vi..

1. 풀이 (1) 에라토스테네스의 체를 이용하여 모든 소수를 찾고 (2) 투포인터를 이용하여 합이 N이되는 경우의 수를 찾으면 된다. ​ * 투포인터 : 시작부분s와 끝부분e, [s,e)까지의 합 S라 할때, (시간복잡도는 O(n)) (이때 L의 각 원소는 양수이고, N도 양수여야 한다) i) S==N이면 cnt+=1, e+=1(e가 범위밖(==size+1)이면 끝내기), S+=L[e-1] ii) SN이면 S-=L[s], s+=1 ​ 2. 소스코드 N=int(input()) isPrime=[1 for i in range(N+1)] isPrime[0]=isPrime[1]=0 primeL=[] def aratos(): for i in range(2,N+1): if isPrime[i]: primeL.appen..

1. 풀이 일반적엔 백트래킹문제. 아래 두가지만 주의하면 된다. (1) 영역확인 잡기술 dR=[-1,-1,-1,0,0,0,1,1,1] dC=[-1,0,1,-1,0,1,-1,0,1] #영역 확인 cR=(r//3)*3+1 cC=(c//3)*3+1 for i in range(9): tempR=cR+dR[i] tempC=cC+dC[i] if L[tempR][tempC]==num: return False (2) 해당 depth 모두 탐색후 해당위치 다시 0으로 만들어놓기 주의 for i in range(1,10): if isPossible(r,c,i): L[r][c]=i dfs(cnt+1) L[r][c]=0 *그런데 한가지 이상한점은 python3은 시간초과나서 pypy3으로 제출했는데, ​sys.setrecur..

1. 풀이 (1) bfs를 돌리려다 8자리 숫자를 visited처리해주기 위해서 100000000개의 리스트를 만들었다. 하지만 메모리초과. (4*100000000byte=390625KB=381MB) (2) 이후 수학&그리디로 풀려고 시도했지만 규칙 못찾음 (3) visited를 set으로 관리하면 됨. ​ * visited를 무조건(0 or 1) 값을 갖는 리스트로만 생각하지말고 set or dictionary도 생각해줄것! ​ 2. 소스코드 from collections import deque N,K=map(int,input().split()) L=list(input().split()) visitedS=set("".join(L)) q=deque([["".join(L),0]]) ans=-1 while(..

1. 풀이 원래 맞았던 문제가 재채점 된 이후 시간초과가 났다. (소스코드1) dfs로 탐색하며 파라미터로 위치와 현재까지의 word를 저장했다. 이후 새롭게 탐색하는 격자의 알파벳이 word에 있는 알파뱃이면 그자리에서 탐색을 종료했다. 풀이는 똑같지만 시간초과를 줄이기 위해 두가지를 바꿔주었다. (소스코드2) (1) 격자의 알파벳이 word에 있는지 확인해 주기 위해 (alpabet in word)를 사용했다. 하지만 이러면 word를 한바퀴 다돌아야 하기 때문에 시간이 오래걸린다. 알파벳은 총 26개이므로, 알파벳의 아스키코드를 인덱스로 하는 길이 26의 visited 리스트를 관리하여 특정 알파벳이 현재까지의 단어에 포함되어있는지를 즉시 알 수있도록 해주었다. ※ 이런류의 탐색에서 시간초과를 많이..

1. 풀이 모든 경우를 다 조사하면 된다. dfs(소스코드1)와 조합(소스코드2)으로 풀었다. 주의할 점은 "부분수열의 정의"와 "최대 경우의 수". (1) 부분수열의 정의 수학에서, 수열의 부분수열(部分數列) 또는 부분열(部分列, subsequence)은 그 수열의 일부 항을 원래 순서대로 나열해 얻을 수 있는 수열이다. 예를 들면 크기 순으로 나열된 양의 짝수 2, 4, 6, ...은 크기 순으로 나열된 자연수 1, 2, 3, 4, 5, 6, 7, ...의 부분수열이다. https://ko.wikipedia.org/wiki/%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4 (2) 최대 경우의 수 최대 경우의 수는 N=20일때, 20C1+20C2+20C3+...20C19+20C20 이 ..

1.풀이 N이 40이기 때문에 완전탐색으로는 시간초과가 난다. (N=20일때 문제 1182 부분수열의 합 (sosoeasy.tistory.com/30) ) 따라서 N을 반으로 쪼개고 각각(왼쪽절반과 오른쪽 절반)이 가질 수 있는 합을 구해서 경우의 수를 구해준다. ​ (1) 절반을 잘라서 왼쪽숫자들로 만들 수 있는 모든 숫자의 합(leftsum)을 구하고 그 개수(cnt)를 dictionary형태로 저장한다 ( leftDict[leftsum]=cnt ) (2) 오른쪽 절반에서 rightsum을 구하고, leftDict[S-rightsum]이 있으면 해당 숫자만큼을 ans에 더해준다. (3) 왼쪽의 합 만으로 S를 만드는 경우의 수, 오른쪽의 합 만으로 S를 만드는 경우의 수는 (2)에서 더해지지 않는다...

1.풀이 처음에 이진탐색을 해서 숫자x가 있는지 확인한 이후, 있다면 해당 위치에서 앞뒤로 이동하며 몇개있는지 세는 식으로 문제를 풀었다. 하지만 이런 방법은 숫자 x가 500,000개 있다면, 50만번을 수행해야 하므로 시간초과가 걸린다.(소스코드1) 따라서 숫자 x

1. 풀이 일반적인 많이풀던 (grid) bfs문제와 비슷한데 index처리를 너무못해서 너무 오래 걸렸다. 처음에는 visited를 고려해주지 않아서 메모리초과(시간초과)가 났다 ((1)메모리초과, visited사용x) 모든 경우의 수를 다 따져주어야 한다고 생각했지만, a=acs , b=acbs , c=acacbss 일때 아래의 두 경우는 같은 경우이기 때문에 visited로 관리해줘서 한가지 경우만 탐색해 주어야 시간을 줄일 수 있다. ((2)통과) a c s 1 2 a c b s 3 4 a c s 3 4 a c b s 1 2 이후 vistied를 사용해서 큐를 구성할 때 인덱스 에러가 많이 났다. (1) 다음 방문지를 기준으로 q에 넣을 수 있는지 검사하고(aIndx+1

1. 풀이 (1) L의 길이는 최대 2000. 두개씩 모든경우를 합쳐야 하므로 2000C2번의 반복이 필요하다. (2) sort된 L리스트에서 중복된 좋은수의 가장 앞부분을 찾아서 isGoodNumL에 표시한다. - L리스트에 모든 숫자가 서로 다르다면 그냥 이분탐색을 하면 되지만, 같은 숫자가 있을수도 있기 때문에 lower bound를 찾아주고(가장 앞에있는 위치), 다음단계에서 중복된 "좋은수"를 찾아준다. - 처음엔 upperbound와 lowerbound를 모두 찾은 뒤 lowerbound에서 upperbound까지 모두 isGOodNumL에 1로 표시해 주려고 했지만, 만약 최악의경우 upperbound-lowerbound가 2000이 되면 시간초과가 발생할 수 있기 때문에 조합 반복문을 벗어..

0. 풀이 원칙 ※ dfs,dp류의 문제는 아래와 같은 원칙을 기본적으로 따른다. (1) dp 리스트를 -1로 초기화 한다. (2) 처음방문했을 때 0으로 바꿔준다 (3) 끝까지 간 다음 리턴값을 적절히 조정한다. 이때 리턴은 현재 depth에서 r,c의 상태를 판단하는 방식으로 아래와 같이 구성한다. (bfs를 수행할 때 queue에 넣기위해 미리 tempR,tempC를 검사하는것과 다르다. 일딴 재귀를 돌돌리고 검사한다.) if not (0 -1출력 - 이전경로에서 방문 -> dp 리턴 - 방문한적없음 -> 4방향조사 ​ 2. 소스코드 (1) 방문했을때 0으로 바뀌는걸 이용하여 사이클판단, 틀림 처음에 방문했을 때 dp가 -1에서 0으로 바뀌는것을 이용하여 사이클이 있는지 확인하려고 했다. dp는 끝..