CS21 [알고리즘] 이진탐색이란? + 백준 2805번 나무 자르기 문제 이진탐색의 개념은 간단하다. what? 목적은 무엇인가이진탐색의 궁극적 목적은 탐색! 즉 내가 원하는 타겟을 찾는 것이다. why? 왜 쓰는가그렇다면 어떻게 찾을 것인가? 완전탐색처럼 모든 요소를 돌아볼 수도 있겠지만, (시간복잡도 O(n)임) 정렬이 되어 있다면 그럴 필요가 없다! 숫자 맞추기 up & down 게임을 하는 것처럼 일단 중간을 찍고 범위를 반씩 줄여나가면 된다. (시간복잡도 logN임)훨씬 빠르다 ! 결국 이진탐색은 정렬이 되어있는 경우에내가 원하는 타겟을 모두 순회하는 것보다 빠르게 찾을 수 있는 알고리즘이다. 결국 정렬된 상태에서 무언가를 찾기 위한 좋은 탐색 방법이라는 것! plus !내가 풀었던 이진탐색 문제 중에이진탐색을 어떻게 써야할지 몰랐던 문제가 있는데, 대표적인 이진.. 2024. 12. 19. [카테부] 코테스터디 2주차 - N과 M(7) (백준 15656) # 중복 순열n, m = map(int, input().split())arr = list(map(int, input().split()))arr.sort()ans = []def print_ans(): for i in ans: print(arr[i], end=" ") print()def choose(cnt): if cnt > m: print_ans() return for i in range(0, n): ans.append(i) choose(cnt+1) ans.pop() choose(1) https://alphaca202.tistory.com/11 [알고리즘] 백트래킹 - 경우의 수 문제원하는 조합과.. 2024. 8. 13. [카테부] 코테스터디 2주차 - N과 M(6) (백준 15655) 조합 문제 N개 중에 M개 뽑기!순서 X, 중복 Xn, m = map(int, input().split())arr = list(map(int, input().split()))arr.sort()ans = []def print_ans(): for i in range(n): if ans[i] == 1: print(arr[i], end=" ") print()def choose(curr, cnt): if cnt >= n: if curr == m: # print("cnt : {}, curr: {}".format(cnt, curr)) print_ans() return ans.append(1) c.. 2024. 8. 13. [카테부] 코테스터디 2주차 - N과 M(5) (백준 15654) 순열 문제다 ! n개 중에 m개 골라 나열하라 순서 O, 중복 X 문제임. # 순열 - n개 중에 m개 골라 나열하기n, m = map(int, input().split())arr = list(map(int, input().split()))visited = [0] * narr.sort()ans = []def print_ans(): for a in ans: print(arr[a], end=" ") print()def choose(cnt): if cnt > m: print_ans() return for i in range(0, n): if visited[i] == 0: ans.append(i) .. 2024. 8. 13. [카테부] 코테스터디 1주차 - 배열 합치기 (백준 11728) 정렬된 두 배열이기 때문에 앞에서 부터 포인터를 두개 잡고순차적으로 비교해 나가면 된다! 마지막에 i, j 인덱스 때문에 살짝 헷갈림!n, m = map(int, input().split())arr1 = list(map(int, input().split()))arr2 = list(map(int, input().split()))ans_arr = []i, j = 0, 0while i 2024. 8. 9. [카테부] 코테스터디 2주차 - 부분합 (백준 1806) 문제 유형 : 투포인터 투포인터 문제를 처음 풀어봤는데,, 이해하기 어려웠다.. ! ㅠㅠ i가 1씩 늘어날 때마다, 최대로 뻗어나갈 수 있는 j의 위치는 항상 같거나 증가하기 때문에! (i인덱스 값만큼 줄어드니까)이 문제는 한 방향으로 두 포인터가 진행되는 투포인터 문제인 것이다.. 하지만... 이해를 하는 것도 어려웠는데 구현은 또 다른 문제라.. 시간을 많이.. 썼다투포인터 문제를 몇개 더 풀어보면서 익숙해져야겠다. import sysINT_MAX = sys.maxsizen, s = tuple(map(int, input().split()))arr = [0] + list(map(int, input().split()))ans = INT_MAXsum_val = 0 # 더해줄 값j = 0 for i in .. 2024. 8. 7. 이전 1 2 3 4 다음
