baekjoon 16236 아기 상어 16236번 아기 상어 접근 bfs돌리는건데 좀 까다로운 규칙이 있는 정도이다. 같은 거리 애들 중 가장 위, 가장 왼쪽에 있는 물고기를 먹어야하니 k level나눠서 도는 bfs구현해야한다. 코드 #include <iostream> #include <vector> #include &l...

baekjoon 1865 웜홀 1865번 웜홀 접근 negCycle을 찾아야하는 문제이다. negCycle을 찾는 알고리즘은 벨만포드 알고리즘이 있다. negCycle은 무한정 reweighting되는 문제가 있다. 그래서 벨만포드는 v-1번 돌면 모든 최단 거리를 찾아야 정상이다. 그런데 1번 더 돌았을 때 reweighting이 되면 negCy...

baekjoon 1238 파티 1238번 파티 접근 돌아가는 접근은 x에서 다익스트라 돌리고, 들어가는 접근은 x제외한 vertex에서 다익스트라 돌리고 x.d추가하면 됨. 코드 #include <iostream> #include <vector> #include <array> #include <queue&g...

baekjoon 30805 사전 순 최대 공통 부분 수열 30805번 사전 순 최대 공통 부분 수열 접근 이 문제는 나름 쉽다. 가장 큰 수를 찾아서 그 수 부터 양 수열에서 찾아나가면 된다. 그 다음부턴 그 뒤부터 탐색한다. 탐색 대상은 그전 탐색과 같은 수부터 1씩 줄여나가면 된다. 왜그러냐면 탐색대상보다 큰 수는 이미 전 탐색에서 없다고 나왔...

최단거리 알고리즘 one source shortest path bfs 가중치 없는 그래프에서 넓이 우선 탐색은 최단거리를 만들어 낸다. 최단거리가 k인 vertex를 모두 탐색한 뒤 k+1탐색을 시작한다. dijkstra 다익스트라 알고리즘 지금부터는 가중치 그래프다. nonnegative directed greedy vertex다 ...

baekjoon 1918 후위 표기식 1918번 후위 표기식 접근 stack안의 우선순위가 항상 오름차순으로 유지된다. 그럼 pop할때는 우선순위가 높은 애들 먼저 pop이 된다. a*b/c 이런거도 *들어가있다가 먼저 pop되고 /들어가게 된다. 그러면 어 나랑 우선순위 같은 애들있으면 먼저 pop해서 계산하라는 것이다. 왜? 같이 있으면 우선순...

baekjoon 11444 피보나치 수 6 11444번 피보나치 수 6 접근 피보나치를 행렬로 구하는 방법을 알고 있어야 풀 수 있는 문제이다. /\(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n}=\begin{pmatrix} fib(n+1)&fib(n) \\ fib(n)&f...

baekjoon 9251 LCS 9251번 LCS 접근 대표적인 dp문제인 LCS이다. 앞에서 부터 비교해서 같으면 +1하고 둘다 index+1 다르면 각각 index+1해보고 max찾기 코드 #include <iostream> #include <string.h> using namespace std; string s1, ...

baekjoon 11404 플로이드 11404번 플로이드 접근 플로이드 워셜 알고리즘 쓰는 문제이다. 원래는 3차원으로 만드는 거지만 2차원으로 해도 문제없다. 코드에서 더 자세히 설명하겠다. 코드 #include <iostream> #include <vector> #define INF 100000000 using name...

baekjoon 15650 N과 M (2) 15650번 N과 M (2) 접근 백트레킹 문제를 좀 풀어보고 싶어서 골랐다. 백트레킹은 완전 탐색의 한 방식이다. 막히면 돌아간다는 의미이다. 코드 #include <iostream> #include <vector> using namespace std; void backtrac...