본문 바로가기

전체 글

Language, Instruction 1. 고급언어/저급언어, 기계어, 어셈블리어, 컴파일 언어, 인터프리터 언어High-Level Language; 고급언어: 사람을 위한 언어(C, C++, Java...)Low-Level Language; 저급언어: 컴퓨터가 직접 이해하고 실행할 수 있는 언어(기계어, 어셈블리어...)컴파일 언어: 컴파일 방식으로 작동하는 프로그래밍 언어컴파일러에 의해 소스 코드 전체가 저급 언어로 변환되어 실행되는 고급 언어 (C언어가 대표적)컴파일 언어로 작성된 소스 코드는 컴파일(코드 전체가 저급 언어로 변환되는 과정)을 컴파일러(컴파일을 수행해 주는 도구) 가 진행함컴파일이 성공적으로 수행되면, 개발자가 작성한 소스 코드는 컴퓨터가 이해할 수 있는 저급 언어로 변환된다. 이렇게 컴파일러를 통해 저급 언어로 변환된.. 더보기
Data 1. 데이터 단위와 2의 보수컴퓨터는 이진법 체계로 정보를 해석한다. 이때, 비트 단위로 정보를 해석한다.1Byte8bit1kB1.000byte1MB1.000kb1GB1.000MB1TB1.000GB2의 보수어떤 수를 그보다 큰 2^n에서 뺸 값2. 문자집합, 아스키 코드, 유니코드문자집합컴퓨터가 인식하고 표현할 수 있는 문자의 모음문자 인코딩문자를 0과 1로 변환하는 과정문자 디코딩0과 1로 이루어진 문자 코드를 문자로 변환하는 과정아스키 코드초창기 문자 집합으로, 7비트로 표현된 문자 집합EUC-KR한글 인코딩을 위한 표완성형 인코딩: 초성, 중성, 종성의 조합으로 이루어진 완성된 하나의 글자에 고유한 코드를 부여하는 인코딩 방식조합형 인코딩: 초성을 위한 비트열, 중성을 위한 비트열, 종성을 위한 비.. 더보기
Computer Structure 1. 컴퓨터 구조를 이해해야하는 이유문제 해결 능력의 향상성능/용량/비용을 고려한 개발능력 상승2. 컴퓨터의 구조Main Memory현재 실행되는 프로그램의 명령어와 데이터를 저장하는 부품메모리에는 저장된 값에 빠르고 효율적으로 접근하기 위해 주소(Address) 개념이 사용프로그램이 실행되기 위해서는 반드시 메모리에 적재되어 있어야 한다.메모리는 현재 실행되는 프로그램의 명령어와 데이터를 저장한다.메모리에 저장된 값의 위치는 주소로 알수있다.CPU메모리에 저장된 명령어를 읽어들이고, 읽어들인 명령어를 해석하여, 실행한다.ALU;산술논리연산장치: 계산만을 위해 존재하는 장치Register: CPU내의 작은 임시저장 장치Control Unit; CU: 제어신호(Control Signal)라는 전기신호를 이.. 더보기
B_10989 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제가 주어졌을 때, 이전 문제(수 정렬하기 2)의 결과가 시간 초과였다. (Sort를 사용해도 괜찮았겠지만, 뭔가 배운 내용을 응용하고 싶었다.) 해서, 자연스럽게 모든 테스트케이스에서 nlogn의 시간을 보장하는 mergeSort를 이용하여 풀고자 했지만 메모리 초과가 나왔다. 합병 정렬의 공간 복잡도는 n이다. 그렇다면 n보다 작은 공간 복잡도를 만든느 방법이 필요하다. [에러가 발생한 C++ 코드] #incl.. 더보기
Sort 종류 특징 시간복잡도 선택정렬 가장 작은 값을 앞으로 버블정렬 앞부분 두개씩 비교 삽입정렬 필요할 때만 위치 변경 퀵정렬 분할정복 Pivot을 기준으로 Divide low와 high가 엇가리면 위치를 변경 Pivot에 따라 편향 가능성이 존재 C++의 sort가 이 방법을 사용, sort의 경우 시간복잡도가 최악의 경우가 되는 경우를 방지 최선 최악 병합정렬 분할정복 나누고 합치기 합칠때는 2의 배수씩 합친다 nlogn의 시간복잡도를 보장 힙정렬 Heap Tree Node 구조 힙정렬 -> 힙구조 반복 maxHeap - parentNode > child Node - minHeap - child Node > parentNode - 계수정렬 (Counting Sort) 범위조건이 존재할 때만 사용 중복되는 .. 더보기
B_24313 https://www.acmicpc.net/problem/24313 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net #include #define fn(a1, a0, n) a1 *n + a0 #define gn(n) n using namespace std; int main() { int a1, a0, n, c; cin >> a1 >> a0; cin >> n; cin >> c; if (fn(a1, a0, n) 더보기
B_24267 https://www.acmicpc.net/problem/24267 24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 2가지 방법으로 수행시간을 측정할 수 있다. 1. 수열의 합으로 생각 수열 합 계산을 통해, HTML 삽입 미리보기할 수 없는 소스 의 값을 얻을 수 있다. 이 값을 유심히 살펴본 결과, nC3, n개의 숫자 중 3개를 선택하는 경우의 수와 동일하다. 위 수열의 결과와 조합을 이용한 결과는 다음과 같다. #include using namespace std;.. 더보기
B_10814 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net #include #include #include #include #include #include using namespace std; typedef tuple T; bool cmp(T &v1, T &v2) { if (get(v1) == get(v2)) return get(v1) .. 더보기

티스토리툴바