baekjoon 1005 ACM Craft 1005번 ACM Craft 접근 첫번째 풀이는 주어진 그래프를 역방향으로 구해서 앞 vertex의 건설이 끝나는 시간 중 최대를 구하여 현재 vertex의 건설이 끝나는 시간을 구하는 방식이다. cache[i]는 i번째 건물이 건설 완료 되는 시간이다. 그런데 위상정렬을 이용한 접근이 있다고 해서 2번째...

baekjoon 2252 줄 세우기 2252번 줄 세우기 접근 전형적인 위상정렬 문제이다. CLRS책에서 본 기억을 되살려서 dfs end 시간으로 정렬하면 위상정렬이 된다는 것을 기억해내서 첫번째 방식에서는 그렇게 풀었다. 하지만 찾아보니 2번째 방식, indegree = 0인 vertex를 넣는 방식으로 위상정렬을 할 수 있다는 것을 알았다. ...

baekjoon 13549 숨바꼭질 3 13549번 숨바꼭질 3 접근 저번에 숨바꼭질 1을 풀었을 땐 단순 bfs로 풀어냈다. 그리고 visited를 이용해서 이미 방문한 것들은 방문하지 않았다. 이렇게 할 수 있었던 이유는 queue순서가 시간 순서였다. 하지만 이번에는 순간이동 때문이 그렇지 않다. 일단 pair을 priority_queue에...

baekjoon 12865 평범한 배낭 12865번 평범한 배낭 접근 쪼갤 수 없는 평범한 배낭은 dp 문제이다. dp(i, j) = i번째부터 n번째까지 물건을 이용해서 j의 용량을 가지고 있는 가방을 싸는 최대 가치 i번째 물건을 넣는지 말지에 따라서 계속 뒤로 i+1 i+2따지면서 max하면됨. 코드 #include <iostream...

baekjoon 14938 서강그라운드 14938번 서강그라운드 접근 dijkstra쓰면 바로 풀릴 문제이다. dijkstra는 queue에 .d값들 다 넣어두고 최솟값들 뽑아내면서 그 점의 adj을 relax시키면 된다. 원래는 S라는 집합에 queue에서 뽑은 점을 하나씩 넣고 없는 점 중에 min d를 찾는 것인데 이를 구현할 때 distan...

baekjoon 1167 트리의 지름 1167번 트리의 지름 접근 핵심은 1967번과 같다. 단지 크기가 늘어나서 long long int로 바꿔줘야할 뿐이다. 코드 #include <iostream> #include <vector> #include <array> using namespace std; void d...

baekjoon 1967 트리의 지름 1967번 트리의 지름 접근 처음엔 dp로 풀까도 생각 했는데 너무 경우의 수가 많아진다. 그래서 결국 찾아보니 dfs두번 돌아서 푸는 문제라고 한다. 임의의 루트노드에서 가장 먼 점을 찾는다. 그 점이 트리의 지름의 한점에 들어간다. 그 점에서 다시 dfs를 돌려서 그 점에서 가장 먼 점을 찾는다. 두 점이 ...

baekjoon 11053 가장 긴 증가하는 부분 수열 11053번 가장 긴 증가하는 부분 수열 접근 간단한 well-known dp 문제이다. lis문제. 코드 #include <iostream> #include <vector> #include <array> using namespace std; array&lt...

baekjoon 2638 치즈 2638번 치즈 접근 map[0][0]은 무조건 공기가 있는 위치이니 여기서 처음에 bfs를 돌리면 외부 공기 위치를 표시할 수 있다. 공기는 -1, 치즈는 1로 표시했다. 이때 매번 공기랑 2면 이상 접하고 있는 치즈의 위치를 저장해놓고, 각 치즈를 녹인(0으로 만듦)다음 각 치즈의 위치에서 bfs를 돌리면(공기 채...

baekjoon 9663 N-Queen 9663번 N-Queen 접근 backtracking으로 푸는 문제이다. n*n판에 n개가 들어가야 하니 1row에 1개 들어가야한다. 위에서부터 하나씩 채워나가는 걸 depth로 생각하면 된다. check함수가 둘 수 있는 곳인지 확인해준다. 코드 #include <iostream> #inclu...