[백준] 22944번 죽음의 비 _ Python
·
Algorithms/Brute Fource
[초기 접근 방법] 현재 위치에서 골로 이동할 수 있는지 판단한다. 현재 거리와 가장 가까운 우산 u를 찾아 이동한다. 1~2 과정을 반복한다. [틀린 이유] 가장 가까운 우산으로 가는 것이 효율적이 아니다(?) [생각] bfs 문제라고 생각하지 못했다. 접근 방법이 틀린 것 같아서, 풀이를 검색하다 bfs 키워드만 보고 곰곰히 생각하다가 bfs로 다시 풀어보았다. visited[i][j] = Boolean 으로 코드를 제출했는데 '틀렸습니다.' "왜? 최소 경로는 bfs 맞는데??" 하고 다른 블로그를 찾아 들어가 정독해봤더니 visited[i][j]에 '남은 체력'을 저장하고 풀었어야 했다. "맞다. bfs이므로 한쪽이 우선으로 탐색되어, 우산을 사용하는 효율적인 경로를 찾지 못한다!" visited..
[백준] 12919번 A와 B 2 _ Python
·
Algorithms/Brute Fource
[초기 접근 방법] - 처음에 A-B를 추가하면서 start를 end로 만드는 방법으로 풀었다. - 풀면서, 최대 시간복잡도가 O(2^50)인데 시간초과 나지 않을까? → 역시 시간초과 - 정답은 start를 end로 바꾸는 것이 아니라, end를 start로 바꾼다. - 이는 end의 상태에 따라, 2가지 방식을 적용할 수 있다. ex. end가 A로만 이루어져 있다면, B를 추가하는 연산을 사용하지 않는다. [생각] - A-B를 실제로 제거하고 뒤집는 e를 재귀 돌리는 것이 아니라, 백트래킹이 될 수 있도록 제거를 가정한 e를 재귀해야 한다. (10분동안 가만히 고민함) [코드] # 풀이 시간 : 15+40분 # 시간복잡도 : - # 공간복잡도 : O(n) # 참고 : https://bio-info...
[백준] 14620번 꽃길 _ Python
·
Algorithms/Brute Fource
[초기 접근 방법] - 처음에 '꽃들의 거리 > 2'를 생각하며 기하적으로 접근했다. 삼각형의 모든 변의 길이가 2 이상.. (오히려 더 복잡함) [생각] 1. 오랜만에 풀어보는 완전 탐색 문제. 생각보다 오래 걸렸다.. 2. 첫 코드에서 통과했지만 난잡하게 작성했던 코드를, 아래 블로그를 보면서 리팩토링을 했다. [코드] # 풀이 시간 : 1시간 30분 # 시간복잡도 : O(n^3) # 공간복잡도 : O(n^2) # 참고 : https://amor-fati.tistory.com/120 import sys input = sys.stdin.readline # 인근 5평 대여 비용 구하기 def calFive(): for i in range(1, N - 1): for j in range(1, N - 1): ..
블로그 이전
·
Algorithms/Brute Fource
https://wch-m.tistory.com/