파티에 진실을 아는사람이 있으면 진실만을 말해야 한다. 새롭게 진실을 알게 된 사람을 고려해야한다(그사람이 참석하는 다른 파티에서도 진실을 말해야한다) ​ 1. 풀이 (1) 그래프 연결 1) 파티를 하나의 노드로 본다. 2) 파티를 두개씩 짝지어서 비교하면서, 한사람 이상을 공유하면 연결한다. (파티1과 파티2를 비교하여 둘다 참여하는사람이 있으면 연결한다.) 3) 연결이 완료되면 탐색을 시작한다. (2) 탐색 1) 연결된 노드(파티)들을 탐색한다 2) 연결된 파티들 중 하나의 파티에서라도 진실을 아는사람이 있다면, 연결된 모든 파티에는 진실을 말해야한다 3) 한명도 진실을 아는사람이 없다면 연결된 모든 파티에는 과장을 해도된다. ​ 2. 소스코드 from collections import deque N..

1. 풀이 (1) 설치횟수의 최솟값을 구한다. 설치할때만 이동거리를 +1해주고, 그렇지 않은 노드간의 연결은 +0 (2) 즉 간선간의 가중치가 다르므로(1 or 0) bfs가 아닌 다익스트라를 이용한다. (bfs로 탐색하면, 처음으로 다른문(#)을 찾은 경우가 거울의 최소설치가 아닌, 거울설치에 제약이 없을 때 최소이동 경로가 된다. 따라서 모든경우를 다 탐색한 후 그 중 최소설치횟수를 찾아야함.) (3) 이 문제는 특히 이동방향 상의 제약(빛은 직진만함)이 있기 때문에 한 노드(r,c)에 총 4번까지 방문이 가능하다. 따라서 한 노드 nodeDist[r][c]에 4방향의 저장소를 만든다 즉 nodeDist[r][c][k] : r,c에 k방향일때의 최소 설치횟수 ​ 2. 소스코드 import heapq ..

1. 풀이 최소스패닝트리(MST)문제. 크루스칼 알고리즘을 사용한다. 사이클을 확인하기 위해 유니온파인드를 이용해아햐며, 이때 dfs(or bfs)를 사용하면 시간초과가 난다. ​ 2. 소스코드 (1) dfs,시간초과 import heapq from collections import deque def isCycle(L): visited=[-1 for i in range(V+1)] stack=deque([L[0][0]]) while(stack): temp=stack.pop() # 스택에 있으면 싸이클 if temp in stack: return True visited[temp]=1 for n1,n2 in L: if n1==temp and visited[n2]==-1: stack.append(n2) elif..

어떤노드에 처음으로 방문한 순간이 최단거리임이 보장된다(bfs와 비슷). 따라서 주어진 끝노드에 도달하면 해당 비용을 출력한 후 종료한다. import heapq N=int(input()) M=int(input()) graph={} for i in range(N): graph[i+1]=[] for i in range(M): a,b,c=map(int,input().split()) graph[a].append([b,c]) start,end=map(int,input().split()) maxNum=9876543210 nodeDist=[maxNum for i in range(N+1)] dij=[[0,start]] heapq.heapify(dij) while(dij): temp=heapq.heappop(dij) ..

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

1. 풀이 1) 다음의 두가지 거리가 필요하다. (파티장 x에서 a까지의 최단거리) + (a에서 파티장x까지 최단거리) 2) (파티장 x에서 a까지의 최단거리) : X를 시작점으로 다익스트라를 이용해서 구한다 3) (a에서 파티장x까지 최단거리) : edge를 모두 반대방향으로 바꾼 후(cost는 그대로) 다익스트라. 위가 성립하는 이유는 (graph에서 a->b 까지의 최단거리) == (edge의 방향을 바꾼 graph에서 b->a까지의 최단거리) 이기 때문에 자명하다. 2. 소스코드 import heapq #input N,M,X=map(int,input().split()) graph={} graphR={} for i in range(1,N+1): graph[i]=[] graphR[i]=[] for i..

모든 노드들을 최소한의 비용으로 연결한 트리를 최소신장트리(mst)라고 한다. 최소신장 트리를 만드는 방법은 여러가지가 있다. ​ 1. 크루스칼 알고리즘 1) 모든 간선들을 오름차순으로 정렬한다. 2) 가중치가 작은 간선부터 하나씩 연결한다. 3) 간선을 연결했을 때 사이클이 생기면 해당 간선은 제거하고 다음 간선을 붙인다. 4) 간선의 개수가 (node개수 - 1)이 될때까지 간선을 이어붙인다. ​ https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https%3A%2F%2Fwww.google.com%2F 18. 크루스칼 알고리즘(Kruskal Algorithm) 이번 시간에 다루어 볼 내용은 바로 크루스..

1. 위상정렬? 2. 방법 어떠한 노드의 관점에서 그 노드로 들어오는 간선의 수를 진입차수라고 한다. 그리고 이러한 진입 차수가 0인 노드가 항상 시작 노드가 된다. 기본적인 알고리즘은 이러한 시작노드들을 큐에 넣고, 시작노드들과 연결되어 있는 다음 순서의 노드들 사이에 간선들을 없애며, 그 과정에서 새롭게 진입차수가 0이된 노드들을 다시 큐에 넣는 방식으로 진행된다. 3. 소스코드 #include #include #include #include using namespace std; // 부무노드 개수 저장 int parent[32001]; // togo[i]에는 i가 향하는 정점들을 저장 vector togo[32001]; queue q; int main() { int N, M; cin >> N >> ..

*다익스트라의 정석 문제 #include #include #include #include #include #define INF 987654321 #define max_v 20001 #define max_e 300001 using namespace std; int V, E; // graph[i]={j,w} : i 에서 j노드로 가는 가중치 w vector graph[max_v]; int dist[max_v]; // distance[j] : 출발노드에서 j노드까지의 거리, 초기엔 모두 INF void dijst(int start) { for (int i = 1; i w) { dist[toNode] = w; pq.push({ w, toNode }); } } } return; } int main() { cin...

1. 풀이 (1) 각 성별을 정렬한다. 남자성격과 여자성격을 정렬했을 때 총 차이의 합이 최소가 되기위해선 항상 아래의 조건이 만족한다. (n번째남자와 매칭된 여자의 성격수치) j이면 j여자에게 잘맞는 여러명의 남자중 하나를 고른다 dp[i][j]=min(dp[i][j],d[i-1][j]) - ij: d[i][j]=min(d[i][j],d[i-1][j]) ..

1.풀이 (1) 25개의 위치에 n개의 조각을 둘 수 있는 모든 경우의 수를 구한다 (조합을 이용, n은 최대 5이므로 총 횟수는 최대 25C5=53130) (2) (1)에서 구한 모든 경우에 대해 해당경우가 연결되어 있는 상태인지 구한다 (BFS를 이용한다) (3) 연결되어 있다면 원래상태에서 해당경우를 만들 수 있는 최소상태를 구한다. (각 조각에 고유번호를 매기고, 순열을 이용하여 모든 경우를 확인한다.) 2. 소스코드 from itertools import combinations,permutations from collections import deque dR=[0,0,-1,1] dC=[1,-1,0,0] INF=9876543210 def calDist(A,B): return abs(A[0]-B[0..

트리순회 트리를 순회할 때 어떤 노드를 먼저 탐색하느냐에 따라 전위,중위,후위로 나눌 수 있다. 각각의 순회를 알아 본다. 전위순회 부모 -> 왼쪽자식 -> 오른쪽자식 더이상 부모노드가 없을때 그 다음 노드(왼쪽자식)을 탐색한다 중위순회 왼쪽자식 -> 부모 -> 오른쪽자식 더이상 왼쪽자식이 없을때 그다음 노드(부모)를 탐색한다 후위순회 왼쪽자식 -> 오른쪽자식 -> 부모 그다음 왼쪽자식이 없을때 그다음 노드(오른쪽자식)을 탐색한다 *출처 : https://hongku.tistory.com/160 예시코드 (백준 1991 트리순회) def preorder(N): global graph if N in graph: print(N, end="") preorder(graph[N][0]) preorder(graph..

1. 풀이 (1) 입력이 하나의 그래프임이 보장될때 트리일 조건은 (노드개수-1)==(간선개수)가 된다. (2) 간선개수가 0인것은 빈트리이므로 이것역시 트리이다. 2. 소스코드 #include #include #include #include using namespace std; int main() { int num1, num2; string ans; int t = 1; while (1) { cin >> num1 >> num2; if (num1 < 0) { break; } // test case else { vector graph; set s; // 입력 while (1) { if (num1 == 0 and num2 == 0) { break; } else { graph.push_back(make_pair..

1. 함수의 구성 유니온 파인드는 find와 union 두가지 함수로 구성이 된다. (1) find는 그래프에서 루트노드를 찾아주는 함수이다. int find(int x) { if (parent[x] == x) { return x; } else { return parent[x] = find(parent[x]); } } (2) union은 서로 연결되어 있지 않은 그래프를 연결시키는 함수이다. void Union(int x, int y){ x = find(x); y = find(y); if(x!=y){ parent[y] = x; } } 2. 함수의 사용 유니온 파인드는 아래의 두가지 경우에 사용할 수 있다. (1) 그래프가 연결되어 있는지 확인할 때 (ex [boj]1717_집합의 표현) 어떤 두 노드의 ..

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