본문 바로가기

알고리즘7

자료구조 알고리즘 요약 정리 동적 배열 첫 번째 인덱스 위치에 원소를 삭제하거나 삽입할 때, O(n)이 걸린다. 끝에 삽입하거나 삭제할 때는 상수시간 O(1)이 걸린다. 따라서 스택으로 사용하기 좋지만, 큐로 사용할 때는 복잡도를 고려해야 한다. 파이썬 list() or [ ] C++ std::vector 자바 ArrayList 자바스크립트 Array() or [ ] 파이썬 리스트는 연속된 공간에 원소를 배치하는 배열의 장점과 다양한 타입을 배치하는 연결 리스트의 장점을 같이 취한 형태이다. 사실상 연결 리스트에 대한 포인터 목록을 배열형태로 관리한다. 결국 포인터의 위치를 찾아가서 확인해야 하므로 속도를 희생한 측면이 있다. 대부분의 동적 프로그래밍 언어들은 정적 배열 자체가 없다. 파이썬은 초반에는 2배씩 크기를 늘려가지만, 전.. 2021. 8. 11.
BOJ 9095 1, 2, 3 더하기 BOJ 9095 https://www.acmicpc.net/problem/9095 #include int main() { int n, t; std::cin >> t; int result[11]; result[1] = 1; // 1 result[2] = 2; // 1+1, 2 result[3] = 4; // 1+1+1, 2+1, 1+2, 3 int i; for (i = 4; i > n; std::cout 2020. 6. 30.
BOJ 1463번 1로 만들기 BOJ 1463번 https://www.acmicpc.net/problem/1463 #include int min(int a, int b) { return (a > n; int result[1000001]; result[1] = 0; result[2] = result[3] = 1; int i; for (i = 4; i 2020. 6. 28.
BOJ 4673번 셀프 넘버 BOJ 4673번 셀프 넘버 풀이 소스코드 https://www.acmicpc.net/problem/4673 풀이 1 #include int _d(int n) { return (n == 0) ? 0 : (n%10 + _d(n/10)); } int d(int n) { return n + _d(n); } int main() { int constructor = -1; int upper_limit = 10000; bool is_self_number[upper_limit+1]; for (int i = 0; i 2020. 6. 27.
연결 리스트 연결 리스트(linked list) 파이썬 class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def print_list(self): temp = self.head while temp: print(temp.data, end=" ") temp = temp.next if __name__ == "__main__": linkedlist = LinkedList() linkedlist.head = Node(1) second = Node(2) third = Node(3) linkedlist.head.next = second second.next.. 2020. 6. 20.
순열 순열(permutation) 주어진 문자열에 대한 가능한 모든 조합, 즉 순열을 출력하는 방법을 알아본다. 재귀함수를 이용해 순열을 출력하는 방법 data = list("abc") def permute(data, left, right): """ data: character list return the permutation of the given string """ if left == right: print("".join(data)) else: for i in range(left, right+1): data[left], data[i] = data[i], data[left] permute(data, left+1, right) data[left], data[i] = data[i], data[left] # ba.. 2020. 6. 2.
합병 정렬 합병 정렬(merge sort) 시간 복잡도는 $\theta{(n \times logn)}$ 파이썬 소스코드 def merge(arr, l, m, r): i = 0 j = 0 k = l left_sub = arr[l:m+1] right_sub = arr[m+1:r+1] while i 2020. 6. 1.

티스토리툴바