jenlog

🚩 브루트포스(완전탐색) thinking 가능한 모든 경우를 구한다음, 최소값을 구하면 시간초과가 뜬다. 최악의 경우 (2N!/N!*N!)*T = 10,400,600*50 = 520,030,000 번의 연산을 해서 그런것 같다. 그래서 애초에 부분합이 결과값보다 크면 함수가 끝나도록 처리해줬다. 현재 좌표를 함수의 인자로 받아, 방문한적이 없다면 방문체크 후 합을 더하며 재귀적으로 함수가 돌아가도록 구성했다. 코드 T = int(input()) dx = [0, 1] dy = [1, 0] def dfs(x, y): global res, tmp if res 제한시간때문에 가지치기 해야함 return if x == N-1 and y == N-1: re..

🚩 동적프로그래밍(DP) thinking 1. 규칙을 찾아보려 했으나 실패 -> 규칙 없음 ! 2. DP 접근 인풋숫자의 크기만큼 배열을 만들고, 계산횟수를 해당 인덱스에 입력 & 비교하면서 최소 연산값을 구하는 것이다. 앞에서 부터 계산을 해가면서 카운팅을 늘려나가는 것이 핵심이다 ! ◾ 점화식 : dp(N) = min ( dp(N//3)+1, dp(N//2)+1 , dp(N-1)+1 ) ◾ 시간복잡도 : {배열의 크기 x O(1)} => O(N) 코드 N = int(input()) dp = [0 for _ in range(N+1)] # 인덱스가 N이 되도록 N+1 크기의 배열을 만듦 for i in range(2, N+1): dp[i] = dp[i-1] + 1 # dp(N-1)+1 계산먼저 해주고 i..

🚩 수학, 그리디 알고리즘, 문자열, 파싱 thinking - 기준으로 쪼갠 후, 리스트의 첫번째 요소만 더하고 그 이후 요소는 다 빼면 된다. ex. 50+32-48+72-145+32-5-3 이라면 50+32-(48+72)-(145+32)-5-3 이 가장 최소가 되는 방법이다. 1. - 기준으로 쪼갠다 -> ['50+32', '48+72', '145+32', '5', '3'] 2. 첫번째 요소는 + 기준으로 쪼갠 후 더한다 -> 50+32 3. 나머지 요소는 + 기준으로 쪼갠 후 다 뺀다 -> -48-72-145-32-5-3 코드 input_lst = input().split('-') tmp = input_lst[0].split('+') res = 0 for ele in tmp: res += int(e..

🚩 자료구조, 문자열, 해시를 이용한 집합과 맵 1. 시간초과 (fail) 문제보자마자 바로 enumerate으로 index랑 value 출력했는데 시간초과가 났다. N, M = map(int, input().split()) lst = [input() for _ in range(N)] quest = [input() for _ in range(M)] for j in range(M): for i, v in enumerate(lst): # print(i, type(i), v, type(v)) # 0 Bulbasaur if quest[j] == v: print(i+1) if quest[j] == str(i+1): print(v) 혹시몰라 sys.stdin.readline() 도 추가해줬는데 이건 의미가 없었다...

🚩 트리(tree) 풀이 1 왼쪽 자식, 오른쪽 자식을 세트로 같이 더해주는 방식 T = int(input()) for tc in range(1, T+1): N, M, L = map(int, input().split()) # N:노드개수, M:리드노프개수, L:출력할 노드번호 tree = [0 for _ in range(N + 1)] for i in range(M): n, v = map(int, input().split()) tree[n] = v # 방법1 if N % 2 == 0: # 노드개수가 짝수인 경우를 위해 설정 tree.append(0) for i in range((N//2)*2, 1, -2): tree[i // 2] = tree[i] + tree[i + 1] print("#{} {}".for..