kicker1979

삽입정렬은 특별한 경우, 즉 정렬되어있는 리스트가 입력값으로 전달되는 경우 O(n)이고, 일반적으로는 선택정렬과 같이 O(n^2)이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def ins_sort(a): #오름차순 n=len(a) for i in range(1, n): #idx:1~n-1(끝) key=a[i] j=i-1 while j>=0 and a[j]>key: a[j+1]=a[j] j-=1 print(a, key) a[j+1]=key d=[2, 4, 5, 1, 3] ins_sort(d) print(d) Colored by Color Scripter cs 이해를 돕기위해 9번째줄에 print(a, key)로 출력을 했다. 그 결과값은 아래와 같다. key가 1일때와..

선택정렬의 계산복잡도는 O(n^2)으로 입력크기가 커질수록 정렬하는데 시간이 매우 오래걸린다. 1 2 3 4 5 6 7 8 9 10 11 12 def sel_sort(a): n=len(a) for i in range(0,n-1): #0~n-2 min_idx=i for j in range(i+1, n): if a[j]a[min_idx]:

연결되는 방향에 따라 singly linked list, doubly linked list, circular linked list가 있다. CS에서 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형(ADT)구현의 기반이 된다. 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하다. 그래서 동적인 메모리 할당으로 메모리 관리에 용이하다. 연결구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽다. 또한 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러가지 방법으로 다양하게 활용이 가능하다. 데이터를 노드의 형태로 저장 노드에는 데이터와 다음 노드를 가리키는 포인터를 담은 구조로 이루어져 있다. 연결리스트는 데이터 요소의 선형집합으로, 데이터의..

나는 입력값을 받을 때 보통 input을 사용했는데 더 빠른 방법이 있는 것을 알았다. import sys를 한 후, sys.stdin.readline()을 하면 된다. int를 입력받을 때에는 똑같이, int(sys.stdin.readline()). 이와 관련된 백준 문제는 www.acmicpc.net/problem/15552 15552번: 빠른 A+B 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다. www.acmicpc.net 자세한 예시와 그 외 사용방법은 아래 사이트로 가자. velog.io/@tbnsok40/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%8B%A4..

데이터의 개수를 계산하는데 유용한 collections 모듈의 Counter 클래스 파이썬이 설치가 되어있다면 사용이 가능하다. 단 from collections import Counter 을 해야한다. Counter클래스는 리스트나 문자열의 요소의 개수를 세어 딕셔너리 형태로 리턴한다. (요소key:개수value) ▷문자열 1 2 3 4 collections import Counter print(Counter('HAHAha')) #Counter({'H': 2, 'A': 2, 'h': 1, 'a': 1}) 대소문자 구분 print(sorted(Counter('HAHAha').elements())) #['A', 'A', 'H', 'H', 'a', 'h'] cs 대소문자를 구분한다. ▷리스트 1 2 3 4 ..