Algorithms/Brute Fource

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

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

[초기 접근 방법] 1. 모든 땅을 고르게 한다. min ~ max 까지 땅의 높이를 고르게 했을 때, 소요 시간을 파악한다. 이전 소요 시간보다 크면 멈추고 출력 (최적화) 2. 시간을 계산한다. if n > k (목표 높이가 높을 때) n의 높이로 설정했을 때, n-k 쌓을 블록이 필요 → 1 elif n < k (목표 높이가 낮을 때) k-n 블록을 제거 → 2 3. B + push < need n 높이로 고르게 만드는 건 불가능 [생각] - 완전 탐색 문제 - 파이썬으로 제출할 때, elif로 조건 처리하게 되면 시간초과가 난다. else 로 256MN 처리를 줄여줘야 통과할 수 있다. [코드] # 풀이 시간 : 30분 # 시간복잡도 : O(256MN) # 공간복잡도 : O(MN) # 참고 : -..

https://www.acmicpc.net/problem/2422 [초기 접근 방법(X)] 1. 주어진 아이스크림에서 3가지 조합을 모두 구한다. 2. 모든 조합 경우에서, 금지된 조합(x, y)가 포함될 시 총 count(nC3)에서 -1을 한다. 3. 가능한 조합 count를 출력한다. [생각] 위 접근 방법대로 풀면 시간복잡도가 O(M * nC3)이다. (M : 금지된 조합, N : 아이스크림 갯수) 금지된 조합에 대해 (x, y) (y, x) 에 대한 boolean 처리를 해주고, nC3 조합에 대해 금지된 조합이 있는지 여부를 판단하는 것이 효율적이다.. *어려운 문제는 아니였지만, 시간복잡도의 최적화에 대해서 고민한 문제였다. [코드] # 풀이 시간 : 20분 + 10분 # 시간복잡도 : O(..

https://www.acmicpc.net/problem/15721 [초기 접근 방법] T번째 '뻔' or '데기'의 위치를 구해야 한다. 1. "뻔" or "데기"의 개수(degiCnt)가 T 이상이 때까지, lst를 늘려준다. 2. 뒤에서 x = (degiCnt - T) 번째 인덱스를 %A(사람 수) 출력 → 원탁에서 몇 번째에 있는지 출력 [생각] 일반적인 구현 문제였다. [코드] # 풀이 시간 : 20분 # 시간복잡도 : O(T^2) # 공간복잡도 : O(T) # 참고 : - A = int(input()) T = int(input()) what = int(input()) result = [] n = 0 degiCnt = 0 while True: n += 1 # n회차 lst = [0, 1, 0, ..

[초기 접근 방법] core : 제일 작은 2개가, 제일 큰 것보다 커야 함 1. 그러면 제일 작은 2개의 숫자를 먼저 선택하자. (연속된 수) 2. 삼각형 조건을 만족하는 수를 count [생각] 맞았다! 그런데 더 효율적으로 풀 수 있었다!! 기준이 되는 start 인덱스와, end(=start+2)를 매개변수로 던져준다. 그리고 함수 내에서 end 인덱스부터 탐색을 하면서 end+=1 로 범위를 넓혀주며 카운트를 한다. 기존 코드와 개선된 코드 모두 첨부하겠다 [기존 코드] # 풀이 시간 : 1시간 # 시간복잡도 : O(n^2) # 공간복잡도 : O(n) # 참고 : - # core : 제일 작은 2개가, 제일 큰 것보다 커야 함 # 1. 그러면 제일 작은 2개의 숫자를 먼저 선택하자. (연속된 수..