17건의 항목
가지를 끊어버리는 백 트래킹에 대해 알아보자.
분기 한정법에 대해 알아보자. 분기 한정법 Branch : 이전 상태 공간 트리에서 다음 가지로 넘어가는 경우를 말함 Bound : 한계 이전의 백 트레킹과 크게 다르지 않다. 그 부분 집합의 합을 구하는 문제와 크게 다르지는 않다.
실버2 : BFS 문제이다.
골드4 : bfs 문제이다. 풀이 bfs는 가중치가 없는 그래프의 최단 거리 문제를 풀 때 사용하는 방법이다. 이 문제는 최단 거리 문제이므로 이 풀이를 선택하는 것은 맞다.
골드4 : bfs 문제이다. 생각 단순한 구현 문제이다. 이 때, 순서를 잘 파악하는 것이 중요하다. 먼저, 불을 번지게 한 상태에서, 사람의 현재 위치로 부터 어디로 가는 것이 좋은지를 판단해야 한다.
골드5 : bfs 문제이다. 생각 최소 경로를 묻는 문제로써, 완전 탐색으로 풀이할 수 있다. 이 때, 중요한 점은, 한번의 스텝을 넘어감에 있어서 소수여야 한다는 것, 그리고 불가능하다는 것을 알려주기 위한 visited를 만드는 것이다.
풀이1 실버1 : BFS 문제이다.
골드5 : BFS 문제이다.
골드5 : BFS 문제이다. 풀이 cost에 따라 탐색하지 않을 노드를 분명히 정해야 한다.
골드4 : BFS 문제이다. 풀이 아니 풀이방법을 아는데 왜 코드가 안돌아가는지 모르겠다. 계속해서 메모리 초과가 뜨는데 어떤 부분이 문제인지 아직도 못찾았다.
실버1 : BFS 문제이다. 풀이 물의 높이를 존재하는 min값에서 max로 잡아줬었는데, 이렇게 하지않고 0부터 하니 통과했다. 국어문제인듯한데. 아무래도 비가 안오는 것부터 체크해주는게 보다 맞는 것 같긴하다.
골드4 : 완전 탐색 문제이다. 풀이 이게 전날에 급하게 짜다가 조건을 놓친 문제인데, 오늘의 첫문제로 도전해보았다. 난 BFS로 문제 풀이방향을 정했는데, 문제가 방문이 중복으로 일어난다는 것이다.
실버1 : 완전 탐색 문제이다. 풀이 매우 막 푼 풀이. 좋지 않다.
실버2 : 그래프 문제이다. 생각 아. 정말 쉽겠지 했는데, 되지도 않는 시간 복잡도 줄여보겠다고 확인 되지 않는 것 썼다가 하루 다 날린 문제이다. 문제는 상당히 간단하게 DFS로 풀 수 있다.
풀이 일단 DFS로 풀었다. 근데 풀이를 보니 다 BFS로 풀었더라. 그래서 다음날 다시 도전할 거다.
풀이 BFS로 풀었는데, 배열이 reference로 전달되어 애먹었다.
문자열 처리는 파이썬으로 find() isalpha() isalnum() for ~ in list, string으로 하나씩 꺼낼 수 있다. ~ in list, string으로만 하면 t/f 반환한다.