To Be myself

최소 신장 트리(minimum spanning tree)- 신장 트리: 가중 무방향 그래프에서 모든 정점을 포함하는 연결된 부분 그래프 중에서 트리인 것- 최소 신장 트리: 신장 트리 중에서 간선의 가중치의 합이 가장 작은 것 크루스칼 알고리즘(Kruskal algorithm)- 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 골라서 사이클을 형성하지 않는 간선을 추가하는 방식으로 최소 신장 트리를 만들어가는 알고리즘- 욕심쟁이(Greedy) 방법이 적용- 간선 (u,v)의 두 정점 u,v가 서로 다른 연결 성분에 속하면 해당 간선은 사이클을 형성하지 않음- |V|=n개의 정점이 각각의 서로 다른 연결 성분으로 구성된 상태에서 시작해서 간선을 추가할 때마다 연결 성분들이 하나씩 ..

그래프(graph)연결할 객체를 나타내는 정점(vertex)의 집합과 정점을 연결하는 간선(edge)의 집합으로 구성된 비선형 자료구조그래프 G=(V, E) → 연결할 객체는 나타내는 정점의 집합 V와 정점을 연결하는 간선의 집합 E의 집합 - 종류 → 무방향 그래프 vs 방향 그래프, 가중 그래프 - 주요 용어 → 인접, 부수, 부분 그래프, 경로, 경로의 길이, 차수(진입차수, 진출차수), 단순 경로, 사이클, 루프, 연결, 강하게 연결, 약하게 연결 그래프의 구현 방법정점들의 관계를 나타내는 간선의 집합 E를 표현하는 것인접 행렬(adjacency matrix)- 정점의 집합 V={1,2,…,n}인 그래프 G에 대해서 2차원 배열 A=(n×n)으로 표현하는 방법- |V|*|V| 행렬 사용- 조밀한(..

레드-블랙 트리(red-black tree)2-3-4 트리를 이진 탐색 트리 형태로 구현한 것으로서, 검정 노드와 빨강 노드로 구성된 균형 탐색 트리 ⦁ 이진 탐색 트리로서 다음의 성질을 추가로 만족하는 균형 탐색 트리 ① 모든 노드는 검정이거나 빨강 ② 루트 노드와 리프 노드는 검정(단, 모든 리프 노드는 NULL 노드) ③ 빨강 노드의 부모 노드는 항상 검정 → 빨강 노드가 연달아 나타나지 않음 ④ 임의의 노드로부터 리프 노드까지의 경로상에는 동일한 개수의 검정 노드가 존재 ⦁ 탐색 연산 → 이진 탐색 트리의 탐색 방법과 동일 ⦁ 삽입 연산 → 탐색이 실패한 NULL 노드에 빨강 노드로 추가하고 두 자식 노드를 NULL 노드로 만듦 - 이때 빨강 노드가 연달아 나타나면 레드-블랙 트리의 성질을 만족..

순차 탐색(sequential search)- 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법 ⦁ 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법 ⦁ 성능 → O(n) ⦁ 모든 리스트 형태의 입력에 적용 가능 → 특히 비정렬 데이터 탐색에 적합 ⦁ 데이터가 큰 경우에는 부적합이진 탐색(binary search)- 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법- 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법 → 분할정복 방법 적용 ⦁ 성능 → 탐색 O(logn), 초기화 O(nlogn), 삽입/삭제 O(..

데이터 분포 기반 정렬제한된 조건에서 알고리즘 성능 (시간 복잡도) 가 O(n)공통적으로 안정적, 제자리 정렬 X 계수 정렬(counting sort)자기보다 작거나 같은 값의 개수를 계산해 정렬 위치를 정하는 방식입력 값 범위가 데이터 개수보다 작거나 비례하면 O(n)안정적 정렬, 제자리 정렬 X, 보편성 떨어짐 기수 정렬(radix sort)자릿수별로 구분하고 계수 정렬같은 안정적인 정렬 알고리즘을 적용입력 데이터 자릿수가 상수 일때 O(n안정적, 제자리 정렬 X 버킷 정렬(bucket sort)값의 범위를 균등하게 나누고 여러개 버킷을 만든 다음 해당하는 버킷에 데이터를 넣고나서 버킷에 삽입 정렬 같은 안정적인 정렬을 수행한 후 버킷 순으로 데이터 나열하는 방식입력 데이터 값이 확률적으로 균등..

정렬내부 정렬모든 데이터를 주기억장치에 저장하고 정렬 비교 기반 정렬 - 두 데이터를 직접 비교하여 정렬, 키 값의 비교 횟수로 알고리즘 성능 나타냄ex. 선택 정렬, 버블 정렬, 삽입 정렬, 셀 정렬, 합병 정렬, 퀵 정렬, 힙 정렬vs데이터 분포 기반 정렬- 데이터의 분포 정보를 활용해 정렬,   데이터 이동 횟수로 알고리즘  성능 나타냄ex. 계수 정렬, 기수 정렬, 버킷 정렬 안정적 정렬동일한 값을 가진 데이터들이 정렬을 하고 나서도 상대적인 위치가 같게 유지되는 정렬 제자리 정렬입력 배열의 데이터 개수와 관계없이 일정한 상수개 외에 별도로 저장 공간이 필요하지 않은 정렬  선택 정렬 (Selection Sort)- 가장 작은 값부터 순서대로 선택해서 정렬 -> 정렬 안 된 부분에서 최솟값 찾고 ..

알고리즘알고리즘 분석정확성 분석: 유한한 시간내에 얼마나 정확한 결과를 내는지 수학적으로 증명 효율성 분석: 수행에 필요한 자원의 양을 측정 - 공간 복잡도: 메모리 양 (정적 + 동적)- 시간 복잡도: 수행 시간 (입력 크기의 함수와 최악의 수행시간) *(실용적) 모든 연산이 아닌 루프반복 횟수만 조사하고 최고 차수로 정함 점근 성능무한한 입력 크기에 따라 결정되는 성능실용적으로는 최고차수만으로 시간 복잡도를 표현 Big O (빅오) 점근적 상한, 최악의 수행시간 Big Ω (빅 오메가)점근적 하한, 최선의 수행시간 Big θ (빅 세타)점근적 상하한 O-표기 함수 간의 크기 관계상수     로그       선형        로그 선형      제곱      세제곱      지수O(1)   순환 알고..

알고리즘알고리즘을 왜 배우는가?알고리즘을 설계하고 분석하는 방법을 배우면, 컴퓨터로 문제를 해결하는 방법을 체계적으로 생각하면서 지적 추상화 및 통찰력이 향상될 수 있다.기본 개념문제를 풀기 위한 절차/방법의 명령어 들을 단계적으로 나열 정의한 개 이상의 출력을 만들기 위해 (입출력), 컴퓨터에서 수행 가능한 (유효성) 단순하고 명확한 (명확성) 명령들의 유한한 단계(유한성)를 거쳐 종료해야 한다. + (효율성) 설계욕심쟁이 방법 (Greedy Method, 탐욕 알고리즘)각 단계에서 가장 최선이라고 생각되는 국부적인 최적의 해를 선택해나가면서 전체의 최적해를 찾는 전략간단하면서 효율적인 알고리즘을 만들 수 있음최솟값/최댓값 구하는 최적화 문제 ► 거스름돈 문제동전의 개수를 최소화하면서 거스름돈을 돌려주..

구문론- 의미(의도)가 애매모호하지 않고 명확하게 정의되어야 한다 의미론- 언제나 의미가 동일하게 해석되어야 한다. 기계어- 0과 1로 이루어진 2진수 언어로 컴퓨터 하드웨어를 직접 제어할 수 있는 수준. 사람이 이해하거나 프로그램 작성이 어려워 범용성이 낮음 어셈블리어- 기계어의 명령어를 사람 언어와 유사한 알파벳 형태로 바꾼 언어. 기계어보단 읽기 쉽지만 논리 순서가 컴퓨터에 초점을 둠

중앙처리장치(CPU)- 제어장치, 산술논리연산장치(ALU), 레지스터로 구성- 처리장치 : ALU + fpwltmxj 제어신호: 데이터 처리 연산을 실행시키는 이진신호, 제어장치가 처리장치에 제공상태신호: 처리장치의 상태를 나타내는 상태비트로 연산의 순서 정함, 처리장치로부터 제어장치가 전송받음 기억장치주기억장치: 연산에 필요한 프로그램, 데이터, 중간 결과, 연산 결과 등 저장캐시보조기억장치 입출력장치- 입력장치: 사용자의 입력 값을 컴퓨터 알 수 있는 형태로 변환- 출력장치: 연산 겨로가를 사람이 알 수 있는 형태로 변환해서 내보냄 시스템버스버스: 2개 이상의 장치를연결해주는 통신 선로시스템버스: 중앙처리장치, 기억장치, 입출력장치의 연결 및 데이터 통로 역할 - 주소버스 / 데이터 버스 / 제어버스..