일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
- 파이썬
- 큐
- programable switch
- non-nullable
- Unity Editor
- BFS
- LU분해
- Tikz
- 수치미분
- 시간복잡도
- APIE
- 보간탐색
- 백준
- [Required]
- naive sort
- C#
- 알고리즘
- Merge Sort
- 수학문서
- dfs
- 탐색
- 실수자료형
- C++
- 재귀
- quick sort
- 정수자료형
- 스택
- 정렬
- 자료구조
- PGF
- Today
- Total
목록전체 글 (38)
코젤브
- 알고리즘의 분석 시간복잡도 분석: 입력 크기에 따라 단위연산이 몇번 수행되는지 결정하는 절차 표현 척도 - 단위연산: 비교, 지정 … - 입력 크기: 배열 크기, 리스트의 길이, 행렬에서 행과 열의 크기 … - 알고리즘 분석 방법의 종류 모든 경우 분석: (입력 크기에만 종속) 입력값과 무관하게 결과값 일정 => 적용 한정적 최악 경우 분석: (입력 크기와 입력 값에 종속) 단위연산의 수행횟수 최대 평균 경우 분석: (입력 크기와 입력 값에 종속) 평균 최선 경우 분석: (입력 크기와 입력 값에 종속) 단위연산의 수행횟수 최소 - [예시] 배열 덧셈 알고리즘 : 배열에 있는 모든 수를 더해라 case1) 단위연산: 덧셈 입력 크기: 배열의 크기 n 모든 경우 분석: 루프가 n번 반복, 따라서 T(n)..
- 순차검색 알고리즘 위치에 따라 검색 양이 다름. 최악의 경우: n -> 그렇지만 순차 검색이 비효율적인 알고리즘(본 내용을 또 보는 알고리즘)은 아니다. - 이분검색 알고리즘 (정렬된 배열에서 찾는) while문을 수행할 때 마다 검색 대상 크기가 반으로 감소하기 때문에 최악의 경우: lg n + 1 - 피보나치 수열 재귀적 방법 -> 중복 계산 문제 - 수행 속도가 매우 느림 (중복 계산 문제) - fib(n)의 호출 횟수 = 재귀 트리의 노드 개수 = T(n) > 2n/2 반복적 방법 -> 속도 훨 빠름 - 수행 속도가 훨씬 빠름 (중복 계산 X) - 계산하는 항의 총 개수 T(n) = n+1 두 알고리즘의 비교
- 강좌의 목표 : 설계, 분석, 계산적 복잡도(문제 자체의 복잡도) - 알고리즘 : 각 단계가 명확하게 정의되고 실행이 가능한 유한 시간대에 종료되는 어느정도의 일반성을 가진 일련의 절차 - 알고리즘의 요구조건 유한시간 내 종료 termination 명확성 definiteness 실행 가능성 executableness 기타: 일반성 generality - 프로그램 설계 과정 - 문제의 표기 방법 - 문제: 답을 찾고자 던지는 질문 - 파라미터(parameter): 문제에서 특정값이 주어지지 않은 변수 - 문제의 사례(입력): 파라미터에 특정 값을 지정한 것 - 사례에 대한 해답(출력): 주어진 사례에 관한 질문에 대한 값 - 알고리즘의 표기 : C++에 가까운 의사코드 사용 (자연어, 프로그래밍 언어 ..
백준 2750번 문제를 합병 정렬과 퀵 정렬로 각각 풀어보자. * 재귀 알고리즘: 큰 문제를 작은 문제로 쪼개고 작은 문제의 해답을 return하면서 큰 문제의 답에 접근하는 알고리즘 백준 2750번: 수 정렬하기 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 합병 정렬 : 리스트를 분할하여 정렬하고 합병 // 합병 정렬 알고리즘 코드 void merge(int list[], int left, int mid, int right) { int i, ..
운영체제 : 하드웨어 리소스를 응용프로그램이 사용할 수 있는 형태로 변환/제공 해주는 소프트웨어 운영체제의 역할 추상화 제공 일반적으로 사용하는 공통적인 기능 재활용 가능 하드웨어 종속성 제거 * 하드웨어 종속성: 하드웨어에 의존하는 / 하드웨어 업그레이드 시 애플리케이션에 영향 받는 경우 리소스 관리 애플리케이션 간의 영향 제거 리소스에 대한 효율적인 활용/ 공평한 접근 운영체제의 기능 프로세스 관리 메모리 관리 파일시스템 관리 프로세스 사이의 통신 시스템 프로그래밍 : 유닉스 환경에서 시스템 콜을 이용하는 프로그래밍 - 파일 시스템과 관련된 처리가 필요한 경우 - 프로세스와 관련된 처리가 필요한 경우 - 프로세스 사이의 통신이 필요한 경우 시스템 콜 vs 라이브러리 함수 시스템 콜 : 시스템(OS)이..
백준 1991번 문제: 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 3주차 트리 자료구조 교육에서 배운 것처럼, 구조체를 통해 이진 트리를 구현하고 각 정의에 맞게 코드를 구성하면 된다. 전위 순위 : 루트 노드 방문 -> 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 중위 순위 : 왼쪽 서브트리 방문 -> 루트 노드 방문 -> 오른쪽 서브트리 방문 후위 순위 : 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 -> 루트..
그래프 "정점(V, Vertex node)과 그 정점을 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조" 그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다. 정점(V): 어떤 자료나 개념을 표현하는 정점(노드) 간선(E): 정점을 연결 그래프 G(V, E): 정점들의 집합 V와 간선들의 집합 E로 구성된 그래프 경로: 한 정점인 시작점에서 다른 정점인 도착점으로 가는 간선이 연속되게 연결된 것 순환: 경로의 시작점과 도착점이 동일 인접(Adjacent): 간선 (U, V)에서, 두 정점 U와 V는 인접한다. 부속(Incident): 간선 (U, V)는 정점 U, 정점 V에 부속된다. 그래프의 종류 방향과 가중치에 따라 그래프의 종류를 구분할 수 있다. 그래프: 구현방법 ..
스택(stack) 후입선출(LIFO: Last-In First-Out) :가장 최근에 들어온 데이터가 가장 위에 있게 되고, 또 가장 먼저 나간다. 연산 create(size) : 크기가 size인 스택을 생성함 push(element) : 스택에 새로운 원소를 삽입함 top을 먼저 증가시키고 그 위치에 원소를 삽입함 is_full() : 스택이 가득 채워져 있는지 검사함 가득 채워져 있으면 true, 하나라도 비어 있다면 false를 return pop() : 스택에서 원소 하나를 없앰 top이 가리키는 원소를 가져오고 top을 하나 감소시킴 is_empty() : 스택이 비어 있는지 검사함 스택이 비어 있으면 true, 비어 있지 않으면 false를 return 배열로 구현한 소스코드 #include..