DevKim

www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net sorted 를 이용해서 쉽게해결 import sys n=int(sys.stdin.readline()) List=[] for i in range(n): List.append(int(sys.stdin.readline())) List=sorted(List) for i in range(n): print(List[i])

www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제 이름을 보면 알겠지만.. 같은 문제가 메모리와 시간초과 제한만 다르게 출제되어있다. 1과 2는 sorted 내장 함수와 다른 정렬 알고리즘을 이용하여 쉽게 풀었지만, 이번 문제는 시간제한과 메모리 제한이 다음과 같다. 3 초 (하단 참고) 8 MB (하단 참고) 입력개수 N(1 ≤ N ≤ 10,000,000)로 주어져있고, 입력 수는 10,000보다 작거나 같은 자연수인 것에 비해 메모리 제한이 너무 작아서 4번이나 메..

[1] 하드웨어의 구성 - CPU,메인 메모리 - 출력장치,입력장치,저장장치 [2] 용어 간단 정리 1) CPU - 명령어를 해석하여 실행하는 장치 2) 메모리 - 프로그램&데이터 저장하는 장소 3) 입력장치 - 마우스,터치스크린..등 4) 출력장치 - 모니터, 스피커..등 *최근에는 그래픽 카드에 GPU (그래픽용 CPU) 달아서 직접 계산함 5) 저장장치 - USB,하드디스크..등 6) 메인보드 - 다양한 부품들 연결하는 커다란 판 *가는 선은 버스가 이동하는 경로. 전력이 공급되면 버스로 연결된 부품이 작동함 (+) 폰노이만 구조 - 모든 프로그램은 메모리에 올라와야만 실행할 수 있다!!!! * 요리사 : CPU -> 요리사가 요리방법 결정 = 프로세스 관리 -> 도마위의 재료정리 = 메모리 관리 ..

[1] 용어 정리 1. kernel 커널 "자동차의 엔진"에 해당한다고 생각하면 된다. :프로세스 관리, 메모리 관리..등 OS의 핵심적인 기능을 모아놓은 것이다. 2. interface 인터페이스 "핸들,브레이크.. 여러 정보 알려주는 자동차 계기판" : kernel에 사용자 명령을 전달하고, 실행 결과를 알려주는 역할. (ex) 유닉스의 사용자 인터페이스 : 셸 shell (명령어 기반) 3. system call 시스템 호출 : system call은 커널이 자기 자신을 보호하기 위해 만든 interface이다. 시스템 호출을 통해서만, 커널에 접근할 수 있다. 사용자가 직접 자원에 접근하는 것을 차단한다. *응용 프로그램 입장에서의 system call* :응용 프로그램이 어떠한 위치에 정보를 저..

운영체제의 역사 중에 최근 사용되고 있는 system에 대해서만 정리해보려고한다. 1.Client/Server system [1990~] : client가 server에 요청하면 server가 client에게 응답하는 구조 -> 최근의 웹 시스템 구조가 이렇다.. *문제점* 흔히 말하는 서버 터졌다..가 여기서 나온다. 너무 많은 사용자가 웹에 접속해서 server에게 한꺼번에 많은 요청을 하니, 요청이 몰려 서버가 과부하되어 다운되어버린다. 2.P2P 시스템 : server를 거치지 않고 사용자사용자 간의 직접 연결된 구조이다. ->p2p서비스 하면 뭔가 불법의 냄새가 나는 느낌적인 느낌이 든다..ㅋㅋ *장점* 서버의 부하를 줄일 수 있다 [ex1] 메신저 : 매일같이 쓰는 카카오톡 같은 사용자간 직접..

[1] 합병 정렬 merge sort *서로 떨어져있는 원소를 교환하는 것이 아니므로, 안정적임 *merge : 정렬을 마친 두 배열을 비교하여 합침 O(n) *전체 시간 복잡도 = O(n log n) (1) sorted 함수 사용하기 -> 정렬을 마친 상태가 아니더라도 적용가능하지만, 빠르지 않음 c=list(sorted(a+b)) (2) heapq 모듈의 merge() 함수 사용하기 ->속도가 빠름 c=list(heapq.merge(a,b)) [2] 퀵 정렬 quick sort 퀵 정렬은 가장 잘 알려진 빠른 정렬 알고리즘이다. pivot을 이용하여 분할 정복 해나가는 알고리즘으로, pivot을 어떤 식으로 정할지가 성능에 크게 영향을 미친다. 평균 시간 복잡도는 O(NlogN) 이며, 만약 매번 1..

1> 단순 선택 정렬 O(n^2) : 말그대로 가장 작은 애 부터 선택해서 순서에 맞는 위치로 옮기며 작업 반복 def select_sort(List): n=len(List) for i in range(n-1 ): min=i for j in range(i,n): if List[min] > List[j]: min=j List[i],List[min]=List[min],List[i] return List List=list(map(int,input().split())) print(*select_sort(List)) 2> 단순 삽입 정렬 O(n^2) : 노드를 하나씩 선택해서 알맞은 위치에 삽입함 def insert_sort(List): k=0 n=len(List) for i in range(1,n): k=i f..

버블정렬은 단순 교환 정렬이다. 1. 일반적인 버블정렬 2. 교환이 한번도 일어나지 않은 경우 stop하는 개선 1 3. 교환이 일어나지 않는 부분을 마지막 지점으로 두는 개선 2 이렇게 3가지로 정리해봤다. 셰이커 정렬(양방향 버블정렬)은 이런경우에 이렇게 사용되는 알고리즘이다. 9 1 3 4 6 7 8 처럼 정렬이 거의 완료되었지만 9가 맨앞에 있으므로 버블 정렬로는 오래걸림 홀수 패스에서는 가장 작은 원소를 맨 앞으로 (뒤에서 앞으로 확인 후 정렬) , 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동 (앞에서 뒤로 확인 후 정렬) 오름차순임 import time def bubble_sort(List): n=len(List) cnt=0 for i in range(n-1): for j in range(n..