dfs(stack)를 이용하여 그래프에서 사이클이 있는지 확인할 수 있다. 이때 그래프가 유향일때와 무향일때 방법이 각각 다르다. ​ 1. 무향그래프 (1) stack #싸이클인지 확인 def isCycle(L): visitedN=[] myL=list(L) stack=deque([myL[0][0]]) while stack: nowN=stack.pop() #싸이클인지 확인 if nowN in stack: #(if nowN in visitedN도 된다!) return True for i in myL: if nowN in i: if nowN==i[0]: other=i[1] else: other=i[0] if other not in visitedN: stack.append(other) visitedN.appen..

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는 끝..

1.풀이 처음에 생각한 방법은 가장 가까운 먼지부터 먼저 방문하고, 그러한 먼지가 여러개일 경우를 dfs로 탐색해주는 그리디한 방법을 생각했다. 하지만 이는 다다음 먼지의 위치에 따라 더 긴 경로가 될 수 있다. 아래의 경우가 그 반례이다. * . . . . . . . . . . . . . * . . . . . . o . . . . . . . . . . . . . * 그리디하게 접근한다면 시작점에서 왼쪽위 먼지로 가야하지만, 그러면 총 이동거리는 16이된다. 하지만 제일 오른쪽 아래에 있는 먼지부터 먼저 접근하면 총 이동거리는 14가 된다. 따라서 모든 경우를 탐색해 주어야 한다. (근데 2차원 평면이아닌, 1차원 직선에선 그리디하게 접근해도 되는거 같음..) ​ 올바른 접근방법은 (1) 시작점에서 모든..

1. 풀이 이진탐색의 기본구조는 아래와 같다. while(left

1. 풀이 풀이 방법은 아래와 같다. (1) 백조끼리 만날 수 있는지 확인 (2) 물에 닿는 빙판을 물로 녹이기 (3) 시간+=1 처음에 했던 단순한 풀이는 (1)을 항상 1번백조에서 2번백조로 bfs를 통해서 확인하고, (2)를 처음부터 끝까지 2중포문으로 돌면서 상하좌우에 물이 닿아있는것을 체크해준 뒤, 반복문이 끝나고 한꺼번에 녹여주는 방법을 썼다. 하지만 이것은 시간초과를 발생시켰다. 해결방법은 이전까지 확인해준 영역을 저장해 두었다가 다음 반복에서 생략해 주는 것이다. 즉 (1)에서는 1번백조에서 bfs를 통해 뻗어 나갈 수 있는 최대한으로 뻗어나가서 테두리를 저장해두고 해당 테두리만 q에 넣어서 다음반복에서 bfs를 돈다. 방문했던 곳은 다시 방문하지 않기위해 swanVisited리스트로 이를..

1. 풀이 일반적인 bfs를 사용하면 된다. 이때 주의할 점 세가지가 있다. (1) 방문된것을 확인해주는 visited 리스트로 중복방문 관리하기. -> visited로 중복방문을 관리해주지 않으면 방문한곳이 다시 방문되어 시간이 지수배로 증가한다. (2) 문자열 처리보다 숫자처리가 훨씬 빠르다. -> 몰랐어서 그냥 문자로 했다가 시간초과. (3) python으론 안된다. pypy로 돌릴것. ​ 2. 소스코드 (1) visited방문 처리x, 문자열로 순서처리, 시간초과 from collections import deque import sys d=["D","S","L","R"] def do(num,order): if order=="D": return str((int(num)*2)%10000) elif o..

1. 풀이 열쇠를 하나 획득하면, 이전에는 못갔던 길을 다시 가는것이 가능해질 수도 있다. 따라서 5개의 열쇠(a,b,c,d,e,f)를 갖는 경우의 수를 각각다 다르게 생각해주어야 한다. (1) 비트마스크 이때 경우의 수를 비트마스크로 처리해준다 => (a,b,c,d,e,f) 열쇠를 각각 갖고있으면 1, 아니면 0으로 나타내 줄 수 있는 2진수를 고려해 준다. ex) 모두 갖고있음 -> 111111 a,b,c,만 갖고있음 -> 111000 a,f만 갖고있음 -> 100001 모두 안갖고있음-> 000000 (2) bfs 열쇠를 하나 찾으면 지금까지 찾아진 열쇠에 해당하는 층으로 이동하여 (마치 벽부수고 이동하기처럼) 새로운 2차원 visited 리스트에서 탐색을 시작한다. (새로운 열쇠를 찾으면 이전에 ..

1.풀이 (1) L[r][c]==0인 숫자를 찾아서 1~9까지 중 넣을 수 있는 숫자를 넣는다 (2) num을 한칸 더가서 dfs를 돈다 (3) 다돌고 난 후엔 해당 위치 L[r][c]를 다시 0으로 돌려놓는다 ​ 2.소스코드 (1) sys.exit()으로 종료 import sys L=[] for i in range(9): L.append(list(map(int,input().split()))) #행, 열, 구역 검사 def cheak(L,r,c,num): #행검사 if num in L[r]: return False #열검사 for i in range(9): if L[i][c]==num: return False #영역검사 dR = [-1, -1, -1, 0, 0, 0, 1, 1, 1] dC = [-1, ..

1. 풀이 (1) 1이나오는 지점에서 가능한 색종이를 종류별(1~5)로 모두 붙여본다 (2) 크기가 현재 ans보다 크면 백트래킹 ​ 2. 소스코드 (1) 두번의 DEEPCOPY, 시간초과 안전한 코드를 위해 stack이 시작할때 리스트들을 copy해주었다. 하지만 스택에 넣을 때 copy를 해준 후 넣기 때문에 L에는 영향이 없다. 따라서 스택이 시작할 때 다시 copy를 해주지 않아도 된다. from collections import deque from copy import deepcopy L=[] for i in range(10): L.append(list(map(int,input().split()))) stack=deque([[[0 for i in range(5)],L,0]]) ans=26 def..