1. 풀이 처음엔 dfs로 완전탐색했고 시간초과가 발생했다. (소스코드1) 규칙을 찾아서 풀어야 한다. 처음에 같은모양을 갖고 있지 않는 행은 열 단위로 스위치를 누를 때 절대 같아질 수 없다. 즉 (1) 동시에 켜져있는 행이 될 수 있는 행들 시작할 때 같은 모양을 갖는 행들 (union find로 찾았다) (2) 해당 집합이(같은 모양을 갖는 행들) k번째에 켜져있는상태가 될 수 있는가? 시작할때 0의 개수와 k를 2로 나눈 나머지가 같다 ​ 2. 소스코드1 (시간초과,dfs 완전탐색) N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) k=int(input()) def push(j): for i in range(N..

1. 풀이 처음엔 dfs만으로 완전탐색으로 문제를 풀었지만 시간초과. (소스코드1) 정답은 dp+dfs였다. 몇번을 풀었지만 어려운 dp & dfs문제.. ​ [원리] (1) 조건에 맞지 않으면 i. return 0으로 가지치기 (2) 조건에 맞으면 i. 끝까지가면 : return 1 ii. 방문한적이 있으면 return dp iii. 방문한적이 없으면 재귀후 저장 dp저장. 핵심은 바로 ii.방문한적이 있으면 return dp를 하는것! ​ ex) 4일동안 지각을 한번, 결석을 연속1번 한 경우를 생각해보자. 만약 이를 DFS+DP(소스코드1)로 푼다면, 해당 경우를 만족하는 모든 경우(OLOA,LOOA,OOLA)에 대해서 한번만 끝까지 계산을 해주고 DP에 저장해놓은다음, 다음에 만났을때 DP값을 반..

1.풀이 처음에는 0부터 N까지 올라가는 bottom up 방식으로 쉽게 풀려고 했다. 하지만 N의 범위가 최대 10^12 이기 때문에 P,Q와 관계없이 무조건 시간초과 메모리초과다. ​(소스코드1) ​ 올바른 풀이는 다음과 같다. (소스코드2) (1) top down방식으로 dp를 풀어야 한다. N에서 시작하여 P,Q로 쪼개가면서 탐색한다. (2) 이때 한번 탐색한 곳은 저장해놓는다 (dp) (3) 하지만 N의 범위가 10^12 이기 때문에 배열로는 메모리 초과가 난다. 따라서 dictionary 자료형을 써야한다. 새로운 유형의 dp였다. ​ 2. 소스코드1 (1) 소스코드1 (bottom up, 메모리초과, 시간초과) N,P,Q=map(int,input().split()) dp=[1 for i in..

1. 풀이 이분그래프를 확인하는 방법은 다음과 같다. (1) 2개의 색깔을 가지고 dfs를 통해 인접한 노드에 다른 색깔을 칠하며 전체를 다 칠하기. (2) 2중 포문을 통해 인접한 노드에 다른색이 칠해져 있는지 확인. -> 다른색이 칠해져 있으면 이분그래프 될 수 없음. (3) 이분그래프 2. 소스코드 import sys sys.setrecursionlimit(10 ** 7) k = int(input()) turn = [1, 0] def cheak(): for v in range(1, V + 1): nowColor = colorV[v] for conNode in graph[v]: if colorV[conNode] == nowColor: print("NO") return print("YES") def d..

1. 최단거리 2. 최소스패닝 트리(MST)

1.풀이 [백준]1035 조각움직이기 (https://sosoeasy.tistory.com/39) 와 비슷한 문제이다. (1) 모든 경우의 수를 조합으로 구한다 (2) (1)에서 구한 경우가 임도연파(Y)가 4명이상인지 확인한다. (3) 4명이상이면 bfs를 통해서 연결되어있는지 확인한다. - 소스코드1 : dfs를 이용하여 연결여부 확인 - 소스코드2 : bfs를 이용하여 연결여부 확인 -> 내생각엔 이게 더 쉽다. * 이런류의 문제를 백트래킹으로 생각하면 조건 처리가 힘들어지는 경우가 많다. 완전탐색으로 보이는 문제는 깔끔하게 순열, 조합으로 풀 수 없을까 고민하는 자세가 필요하다. 2. 소스코드 (1) 소스코드1 (dfs를 이용) from itertools import combinations dR=..

구글링 해보니 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) dfs,dp문제의 정석 (2) 사이클x (3) 가능한 경로의 개수(최단경로 아니다!) 2. 풀이 (1). 일단 가능한 경로를 모두 찾아야 하기 때문에 dfs로 모두 찾는다. (2). 초기값은 -1로 지정해준 후, 이때 한번 지나간 곳은 다시갈 필요가 없으므로 0으로 바꿔준다. (3). 이후 리턴을 받을때 +1씩 해준다 * 설명이 잘되어있는 블로그(단, 초기값이 0으로 되어있어서 시간초과가 난다) https://wootool.tistory.com/83 [백준][1520번][DP] 내리막길 내리막길 https://www.acmicpc.net/problem/1520 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

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) 영역확인 잡기술 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) 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)에서 더해지지 않는다...

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.풀이 (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..

1. 문제 키를 비교하는 몇가지의 조건들이 주어졌을 때, 키 순서를 정확히 알수있는 학생이 몇명되는가? ​ 2. 해결 1~N학생이 있을 때 각 학생별로 1. 키가 작은쪽으로 탐색(bfs or dfs)한번, 2. 키가 큰쪽으로 탐색한번을 해서 1 + 2 = N-1이 되는지 확인하고, 되면 그 학생은 정확한 순위를 알 수 있다고 판단. ​ 3. 소스코드 #include #include #include #include using namespace std; vector to[501]; vector reversedTo[501]; int main() { int ans = 0; int N, M; cin >> N >> M; int a, b; for (int i = 0; i > a >> b..