가지를 끊어버리는 백 트래킹에 대해 알아보자.
분기 한정법에 대해 알아보자. 분기 한정법 Branch : 이전 상태 공간 트리에서 다음 가지로 넘어가는 경우를 말함 Bound : 한계 이전의 백 트레킹과 크게 다르지 않다. 그 부분 집합의 합을 구하는 문제와 크게 다르지는 않다.
실버1 : DFS 문제이다. 풀이 DFS와 동적계획법이 섞인 문제이다. 일단, 특정 위치까지 갈 수 있는 모든 경우의 수를 구해야 하는데, 그냥 방문할 때마다 count를 늘려준다면, 중복해서 방문하는 곳이 너무 많아 비효율 적이다.
골드4 : dp & DFS 문제이다. 풀이 이게. 접근 방식을 약간 반대로해서 오래걸렸다. 바텀 업 방식으로 사고를 하여, 마지막 지점까지 가는데 있어 4방향의 경로를 더해주어야 한다고 생각했다. 그런데 그렇게 생각을 하니 쉽게 점화식이 떠오르지 않았다.
실버1 : DFS 문제이다.
골드3 : 완전탐색 문제이다. 삼성 A형 기출이다. 생각 시간이 1초라, 제한 시간에 들어올 수 있는지 시간 복잡도 계산부터 진행했다. 최악의 경우 100개의 공간에 모두 1이 차있는 경우 한 개의 공간에서 색종이를 5번 검사해야 한다.
실버2 : DFS 문제이다. 풀이 그냥 구현하라는 대로 탐색해서 answer를 늘려주면 된다.
실버3 : dfs 문제이다. 생각 기본적인 dfs 문제이다. 반으로 나눈 팀에 대한 점수를 더하는 것이므로, true false를 통해 구현할 수 있다.
골드4 : 완전 탐색 문제이다. 풀이 이게 전날에 급하게 짜다가 조건을 놓친 문제인데, 오늘의 첫문제로 도전해보았다. 난 BFS로 문제 풀이방향을 정했는데, 문제가 방문이 중복으로 일어난다는 것이다.
실버1 : 완전 탐색 문제이다. 풀이 그냥 가능성을 다 구한다. 그런데 시간 초과가 날수도 있다. 왜냐하면 +-*/가 중복될 수 있으니까 그래서 set으로 이런 중복을 제거한후 주르륵 계산해서 답.
실버2 : 완전 탐색 문제이다. 풀이 기존 것에 비해 연산자 개수가 늘어난 문제. 단순한 순열로 풀면 44P10의 연산 결과라 못푼다. 그냥 완전탐색으로 풀면되긴한데, 백준에서 pypy로 제출했더니 틀렸다고 해서 당황했다.
실버1 : DFS 문제이다. 풀이 기본적인 DFS 문제이다. DFS를 사용할 때는 dp적 사고를 기반으로 코드를 짜는 것이 좋다. 즉, 현재 상태는 다음 상태들의 연산으로 구해진다는 것.
실버1 : dfs를 사용하는 기초적인 문제이다. 이런 문제를 풀 때, 생각보다 실수를 많이하는 부분은, testcase가 있을 때, 초기화를 하지 않는 것이다. 항상 testcase가 있는 문제는, 이 부분을 유념해야 한다.
DFS graph 골드4 : 그래프 문제이다. 생각 이분 그래프란 무엇인가? 문제를 읽고는 파악하는 게 힘들었다. 차라리 그림으로 보는 것이 좋다. {:.center-text} 왼쪽과 같은 그래프가 있을 이걸 오른쪽 그림처럼 바꿀 수 있느냐의 문제이다.
실버1 : 완전 탐색 문제이다. 풀이 매우 막 푼 풀이. 좋지 않다.
골드3 : dfs 문제이다. 풀이 트리 = 사이클이 없는 무방향 그래프. 어떠한 두 노드를 선택해도 경로는 하나이다. 즉 무조건 연결되어 있다. 쉽게 생각하기 위해서 이미 두 지름인 점을 알고 있다고 가정하자.
실버2 : 그래프 문제이다. 생각 아. 정말 쉽겠지 했는데, 되지도 않는 시간 복잡도 줄여보겠다고 확인 되지 않는 것 썼다가 하루 다 날린 문제이다. 문제는 상당히 간단하게 DFS로 풀 수 있다.
풀이 일단 DFS로 풀었다. 근데 풀이를 보니 다 BFS로 풀었더라. 그래서 다음날 다시 도전할 거다.