본문 바로가기
728x90
반응형

Algorithm & Data Structure

Heap 자료구조
Algorithm & Data Structure 2022. 2. 19. Heap 자료구조 힙 자료구조란 우선순위 큐를 위하여 만들어진 완전 이진트리의 일종이다. 큐는 선입선출 구조가 이루어지는 자료구조이다. 이에 데이터들에게 우선순위를 주는 것이다. 여러 값들 중 최댓값과 최솟값을 찾기 용이하고 느슨한 정렬 상태를 유지한다. 최대 힙의 경우에는 최상단 부모 노드에 최대값이, 최소힙의 경우에는 최상단 부모노드에 최솟값이 와야 한다. 최대 힙의 경우 자식 노드의 값들은 부모 노드보다 클 수 없고 최소 힙은 그 반대이다. 파이썬은 heapq를 import 해서 간편하게 사용이 가능하다. 원소를 삽입시) heapq.heappush(리스트 이름, value) 원소 제거 시 heapq.heappop(리스트 이름) : 가장 작은 값 출력 heap 자료구조로 변환) heapq/heapify(리스트 이름) ..
Algorithm & Data Structure 2022. 2. 6. 백준 - 10816번(이진탐색) import sys n = int(sys.stdin.readline()) key_arr = sys.stdin.readline().strip().split() m = int(sys.stdin.readline()) arr = sys.stdin.readline().strip().split() key_arr.sort() #기준 배열 정렬 def binary(a,k_arr,start,end): if start > end: return 0 m = (start + end) // 2 if a == k_arr[m]: cnt = 1 for i in range(1,m+1): try: if k_arr[m - i] == k_arr[m]: cnt = cnt + 1 else: break except IndexError: pass ..
Algorithm & Data Structure 2022. 2. 6. 백준 - 1920번(이진탐색) import sys n = int(sys.stdin.readline()) key_arr = sys.stdin.readline().strip().split() m = int(sys.stdin.readline()) arr = sys.stdin.readline().strip().split() for i in range(len(arr)): arr[i] = int(arr[i]) for i in range(len(key_arr)): key_arr[i] = int(key_arr[i]) key_arr.sort() #기준 배열 정렬 def binary(a,k_arr,start,end): if start > end: return 0 m = (start + end) // 2 if a == k_arr[m]: return 1 ..
백준 - 11401번(재귀,이항계수, 페르마 소정리)
Algorithm & Data Structure 2022. 2. 5. 백준 - 11401번(재귀,이항계수, 페르마 소정리) 이항 계수가 뭔지 기억이 안 나서 이것부터 찾아봤다. 페르마의 소정리 라는 공식을 사용하면 코딩에 용이한 식으로 바꾸는 것이 가능하다. 또한 함수로 팩토리얼 계산을 미리 해놓으면 시간 복잡도를 O(N+logN) 정도로 개선 가능하다/ import sys read = sys.stdin.readline def power(a, b): if b == 0: return 1 if b % 2: #홀수이면 return (power(a, b//2) ** 2 * a) % p else: return (power(a, b//2) ** 2) % p p = 1000000007 N, K = map(int, read().split()) fact = [1 for _ in range(N+1)] for i in range(2, N+1):..
Algorithm & Data Structure 2022. 2. 4. 백준 - 10830(재귀, 분할정복) import sys def f_gob(arr): ans = [0]*n temp = [0]*n for i in range(n): for j in range(n): t = 0 for k in range(n): t = t + int(arr[i][k]) * int(matrix[k][j]) temp[j] = int(t) ans[i] = temp temp = [0]*n global key_cnt key_cnt = key_cnt +1 s="" if key_cnt == key: for i in ans: for j in i: s = s + str(j % 1000) + ' ' s = s + '\n' print(s) else: f_gob(ans) def gob(arr): ans = [0]*n temp = [0]*n for ..
Algorithm & Data Structure 2022. 2. 3. 백준 - 1629번(분할정복, 분할곱) import sys a,b,c = sys.stdin.readline().split() a = int(a) b = int(b) c = int(c) def dac(a,b): if b ==1: return a % c temp = dac(a,b//2) if b%2 == 0: return temp*temp %c else: return temp*temp * a %c print(dac(a,b)) temp를 통해서 절반씩 반복해서 계산하게 재귀를 호출한다. 곱해지는 횟수가 홀수번이라면 한 번이 남기에 a를 곱해준다.
Algorithm & Data Structure 2022. 2. 3. 백준 - 1992번(재귀,분할정복,쿼드트리) 바로 이전에 풀었던 2630번과 거의 동일한 문제이다. 핵심 아이디어는 정말 같고 추가되는 핵심 아이디어가 몇 개 있다. 분할된 사각형 마다 괄호( )를 사용해서 감싸 줘야 한다. 분할된 사각형은 재귀를 기준으로 나눌수 있다. 즉 재귀 직전에 '(' 를 삽입하고 재귀 끝난 직후에 ')'를 삽입하면 사각형 별로 연산을 묶을 수 있다. 팁) 1. print에서 원소 뒤에 sep='\n' 을 입력하면 리스트를 한 줄씩 볼 수 있다. 확인하면서 문제풀면 훨씬 수월하다. 2. sum(리스트명, []) 연산을 수행하면 2차원 리스트를 1차원으로 만들 수 있다. 3. 원소가 전부 1이거나 전부 0 일 땐 (1)이나 (0)이 아니라 반드시 1 혹은 0을 출력한다. (문제 잘 읽을 것) 4. 전부 1이거나 0이 아니라면..
Algorithm & Data Structure 2022. 2. 3. 백준 - 2630번(재귀,분할정복) 핵심 아이디어는 다음과 같다. 1. 입력은 무조건 2^n개로 주어지기 때문에 처음 주어진 전체 길이에서 반씩 분할 정복해나가면 된다. 2. 분할은 무조건 4개로 하면된다. 가장 작은 경우인 길이가 2일 때도 원소 1개씩 해서 4개의 사각형으로 나눠 지기 때문 3. 4분할 기능을 하는 함수를 만들고 이를 조건에 맞게 재귀로 반복 호출하면 된다. 4. 우선 함수의 실행조건은 처음 사각형의 크기가 1보다 커야 하고 0과 1 둘 다 한 개 이상씩 포함해야 한다. 이 조건을 지키지 않아서 한번 실패를 했는데 예를들어 길이 2짜리 사각형(1,1,1,1) 이 주어지면 내 함수는 이거를 각 (1), (1), (1), (1) 이렇게 4개의 사각형으로 분해해 버린다. 따라서 위 조건을 추가했다. 5. 재귀를 호출하는 조건..
Algorithm & Data Structure 2022. 2. 2. 백준 - 5430번(덱,아이디어) 문제 내용 자체는 이해하기 어려운 문제가 아니라고 생각했고 이게 왜 골드 문제이지 싶었다. 하지만 개고생을 했다. 1. R을 받는 족족 reverse를 하게 되면 시간 초과가 난다. 2. 어떻게 하면 좋을까? 만약에 RR을 받는다고 가정해보자 이럴 경우 reverse를 하지 않아도 된다. 3. 그러나 이 문제를 reverse를 쓰려고 하는 순간 절대 못푼다. 4. D를 입력받으면 제일 앞의 원소를 제거한다는 것이 힌트이다. 5. 보통 D를 입력받으면 popleft()를 사용해서 원소를 제거할 것이다. 6. 생각해보면 reverse() 한 다음에 popleft()를 하는 것과 그냥 pop()을 쓰는 것과 동일한 효과라는 것이다. 7. 나는 그래서 key값이 홀수면 pop() 연산을 하고 짝수면 poplef..
728x90
반응형

티스토리툴바