https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. Preview 시간 복잡도 : O(N^2 * 2^N) N * 2^N : 비트마스킹과 각 노드에 대한 연산 (=현재 위치한 도시의 수 * 방문 도시의 경우의 수) N : 다음 도시 경우의 수 공간 복잡도 : O(N * 2^N) 참고 - https://withhamit.tistory.com/246 (이론) - https://velog.io/@dltmdrl12..

[초기 접근 방법] '애니팡' 같은 느낌의 문제 4개 이상이 인접한 구역이 있는지를 체크해서 폭탄을 터트린다. 이 때 일단 모든 맵에서 bfs()로 인접 지역을 체크하고 터트릴 폭탄이 있는 경우 터트리고 맵을 내려, 다시 인접한 구역이 있는지 확인한다. [생각] 폭탄이 터트리고, 공백의 칸을 어떻게 내리는지 고민했던 문제 1) 일단 '.'으로 초기화하자 2) 그리고 각 플로우마다 맨 아랫줄부터 . 그리고 그 윗줄에 색깔이 있으면 교환하는 형식으로 내려오는 걸 구현하자 for i in range(11, -1, -1): for j in range(6): if board[i][j] != '.': # 아래에 빈 칸이 있는지 확인하고, 있으면 전부 내려버려 for k in range(11, i, -1): if b..

[초기 접근 방법] 어떻게 풀어야 될 지 감이 잡히지 않아, O(N^4)으로 시간초과를 예상했지만 누적합도 복습할 겸 일단 누적합으로 제출했다. 누적합 → https://www.acmicpc.net/source/66884805 → https://nahwasa.com/entry/%EB%88%84%EC%A0%81-%ED%95%A9prefix-sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9prefix-sum-of-matrix-with-java [생각] 처음부터 dp를 고려해야 겠다는 생각을 못한 문제.. 1. dp[i][j] : (i, j)에서 지을 수 있는 가장 큰 정사각형 목장 크기 2. 점화식 dp[i][j] = min(dp[i-1][j], dp[i][j-1]..

[초기 접근 방법] 일단 '마피아'가 '나'라고 생각하자. 만약 dp로 푼다면 dp[i] : i번째 밤에 유진이의 유죄지수 값을 저장 꼭 유죄지수가 가장 낮게 유지할 필요는 없지 않을까? 그 다음 날 낮에 본인이 안 죽을 정도에서 밤에 죽이면 된다. 그럼 백트래킹? 본인이 유죄지수가 가장 높으면 리셋하고, 안 높으면 계속 진행 그렇게 완전 탐색을 해서 제일 긴 밤 출력하자 [생각] 우선 "낮"과 "밤" 코드를 분리하지 않고, 한 로직 내에서 같이 구현하려고 했던 것이 초기 구현의 복잡도를 높였던 것 같다. 그리고 낮에 마피아(나)가 죽지 않게끔 조건 처리를 해주었는데, 이 또한 일단 dfs() 재귀를 거치고 dfs() 내 조건 처리에서 제할 수 있었던 부분이었다. 음.. 백트래킹을 할 때 조건에 따라 분..

[초기 접근 방법] 1) 구현 박스와 크레인을 내림차순 정렬을 한다. 무거운 박스부터 무거운 크레인을 배정한다. 배정을 못할 시, 크레인 순환을 +1 한다. → 무거운 박스는 옮기지 못하지만 작은 박스는 옮길 수 있음 2) 이분 탐색 현재 박스 무게에 맞는 크레인을 이분 탐색으로 배정한다. 이 때 박스 무게 초과인 upper_bound가 아닌 이상인 lower_bound로 탐색을 해야 한다. 모든 박스를 효율적으로 이동하기 위해, 무거운 박스부터 크레인으로 옮긴다. → ? [생각] 이분 탐색으로 풀리지 않자 검색하여 코드를 참고했다. 그리디로 푸는 것..😂 그리디 문제인지 알고 접근하면, 바로 그리디적으로 생각하게 되는데 유형을 모르고 푸니 완전탐색, 백트래킹, 이분탐색, dp 여러 측면에서 생각하게 되..

[초기 접근 방법] 스도쿠의 조건 : 행, 열, 네모칸 모두 1가지 숫자만 있는 것 기본적으로 완전탐색 - 백트래킹으로 넣었다 뺐다 하면 단축되지 않을까? - k 값은 스도쿠 값으로, range(1, 10)으로 설정해줘야 함 - 백트래킹의 종료 조건 → 스도쿠의 마지막 빈 칸이 채워졌을 때 종료한다. [생각] 1) 인덱스 3*3 구역의 스도쿠 구역 체크할 때 인덱스 설정이 틀려서 20분을 썼다.. 2) 그리고 한 가지 유의할 점이 스도쿠의 빈 칸의 값이 1~9 모두 유효하지 않을 때는, 이전 값이 틀린 것이므로 빠르게 return을 하여 해당 스도쿠의 빈 칸 dfs()를 끝내준다. 3) 아니면 스도쿠 빈 칸에 대한 1~9 check()를 반복문 안에서 하는 것이 아니라 dfs() 함수 첫번째에서 chec..