Algorithm/etc111 [파이썬] 백준 12919 : A와 B 2 (골드5) [파이썬] 백준 12919 : A와 B 2 (골드5)백준 12919 : A와 B 2풀이방향성 생각target 문자열에서 역으로 접근한다.정방향으로 접근하는 경우 경우의 수가 2배씩 늘어난다.DFS, BFS 둘 다 가능하다.전체코드1. DFSstart = input()end = input()find = 0def dfs(x): global find if find or not x: return if x==start: find = 1 if x[-1] == 'A': dfs(x[:-1]) if x[0] == 'B': nx = x[1:] dfs(nx[::-1])dfs(end)print(find)2. BFSfrom collecti.. 2025. 5. 11. [파이썬] 백준 1300 : K번째 수 (골드1) [파이썬] 백준 1300 : K번째 수 (골드1)백준 1300 : K번째 수 (골드1)풀이방향성 생각이분탐색각 row가 정렬되있음을 바로 확인할 수 있다.각 row에서는 이분탐색으로 진행할 수 있고, 등차수열이라 나눗셈으로 바로 몫을 구할 수 있다.min value, max value는 구간에 포함되지 않도록 잡아주고, while문 조건을 min_val+1 전체코드N = int(input())K = int(input())min_val,max_val = 0,N**2+1while min_val+1 코멘트규칙성이 있는 array에서는 굳이 이분탐색을 사용하지 않아도 된다는 점 생각하기. 2025. 4. 21. [파이썬] 백준 1253 : 좋다 (골드4) [파이썬] 백준 1253 : 좋다 (골드4)백준 1253 : 좋다 (골드4)풀이방향성 생각3개의 수를 고르는 방식으로 풀면 $O(N^3)$으로 터진다.투포인터나, 이분 탐색을 이용해서 풀이.정렬 이후 이분 탐색을 이용해서 풀기.2중 for문으로 두 개의 값을 선택한 후(arr[i] + arr[j] = val), 전체 구간에서 val이 처음 나오는 구간과 끝나는 구간을 찾는다.구간 내에 인덱스 i와 j는 포함하면 안되니 처리를 해준다.숫자들을 선택할 때, N^2 내 iteration마다 set으로 관리를 해주면 터져서 차분 배열을 사용한다.구간의 시작과 끝에서만 이벤트 처리를 하고, 인덱스 i와 j가 내부에 있을 때, 각각 역으로 이벤트 처리를 해준다.전체코드N = int(input())arr = sort.. 2025. 4. 21. [파이썬] 백준 1038 : 감소하는 수 (골드5) [파이썬] 백준 1038 : 감소하는 수 (골드5)https://www.acmicpc.net/problem/1038풀이방향성 생각재귀 기본문자열을 계속 붙여서 끝에 0이 나오는 경우, 감소수열을 더 만들지 못하므로 리턴으로 탈출하기. 전체코드N = int(input())if N nx: dfs(x+nx) dfs('') # 정렬 기준은 문자열이 아닌 숫자로 arr.sort(key = lambda x : int(x)) try: print(arr[N]) except: print(-1)코멘트문자열로 풀었으면 정렬 기준만 다시 생각해주기. 2025. 4. 15. 이전 1 2 3 4 ··· 28 다음
