jenlog

문제 thinking 아주 전형적인 백트래킹 & dfs 문제이다 ! 모든 경우를 전부 따져보되, 이미 답이 안되는 경우(값이 기존 결과값보다 큰 경우)는 바로 중단하면 된다. 열과 행이 겹치면 안되므로 dfs라는 함수의 인자로 행(i)을 넣어, 행을 증가시키며 경우를 체킹했고, visited 라는 리스트를 만들어 열의 방문여부를 확인하도록 코드를 구성했다. 코드 def dfs(i, tmp): # 행, 현재 타임 합 global res if tmp >= res: return if i == N: res = min(tmp, res) return for j in range(N): if not visited[j]: visited[j] = 1 dfs(i+1, tmp+a[i][j]) visited[j] = 0 T =..

문제 thinking 정류장별 배터리 용량을 리스트로 만든 후, 1번 정류장부터 돌면서 교환횟수를 구해 비교했다. 최소한의 교체횟수를 묻고 있으므로 이전횟차까지의 결과값보다 같거나 크면 return 시키도록 함수를 구성했다. 함수의 인자로 현재위치(i), 최대로 갈 수 있는 범위(max_i), 해당타임 교환횟수(cnt)를 두어 일단 갈 수 있는 만큼 최대로 가보면서 cnt 값을 비교했다. + 교환횟수처럼 계속 변하는 값을 함수의 인자로 두면 코드짜는게 더 쉽다. 굿 ! ! ! 코드 def dfs(i, max_i, cnt): # 현재위치(인덱스), 최대로 갈 수 있는 범위, 해당타임 교환횟수 global res if cnt >= res: return if max_i >= N: res = min(cnt, r..

💡 How Quicksort Works ? 퀵정렬은 피봇(pivot)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 다음 배열을 반으로 나눈다. 즉, 피봇보다 작은 숫자는 피봇 왼쪽으로, 큰 숫자는 오른쪽으로 분할한다. 이런식으로 쭉 내려가면 정렬이 되고, 이를 결합하면 정렬된 리스트를 얻을 수 있다. 👍 분할 정복 알고리즘으로 평균적으로 매우 빠른 수행 속도를 나타내는 것이 특징이다. 코드 def quick_sort(left, right): if left >= right: return pivot = left i = left+1 j = right-1 while i

🚩 그리디 thinking player1과 player2의 카드 결과를 카운팅할 cnt_1, cnt_2 이라는 리스트를 만들고 input 데이터를 하나씩 할당해주면서 babygin 함수로 run과 triplet을 체크해주었다. 코드 T = int(input()) def babygin(num, cnt_lst): # 카드숫자, 카운팅리스트 cnt_lst[num] += 1 flag = 0 i = 0 while i = 3: # triplet check flag = 1 break if cnt_lst[i] and cnt_lst[i + 1] and cnt_lst[i + 2]: # run check flag = 1 break i += 1 if flag == 1: return True..

🚩 그리디 thinking 맨 처음 구간을 기준점으로 시작시간과 끝 시간을 비교하면서 8처럼 현재 시작시간이 전회차의 종료시간(14)보다 작으면(겹치면) 카운팅하지 않고, 17, 20, 23처럼 시작시간이 전회차의 끝시간(14, 20, 23) 보다 같거나 큰 경우에만 카운팅을 해주었다. 시간복잡도를 줄이기위해 pop(0) 대신 pop()을 사용할 수 있도록 input 리스트를 1.작업완료시간 - 2.작업시작시간 순으로 내림차순으로 정렬했다. # testcase `.sort(key=lambda x: (-x[1], -x[0])` 소팅결과 # testcase 1 [[23, 24], [20, 23], [17, 20], [8, 18], [4, 14]] # testcase 2 [[20, 24], [12, 24], ..