컴퓨터 기초
-
알고리즘의 시간을 표현하기(시간복잡도 / Time Complexity)컴퓨터 기초/알고리즘&자료구조 2020. 7. 21. 05:25
알고리즘은 효율적으로 짤수록 시간과 자원이 굉장히 줄어드는 효과를 볼 수 있다. 그리고 이러한 알고리즘이 수행하는데 걸리는 시간의 상한선 하한선을 시간복잡도로 표현할 수 있다. 시간복잡도가 낮을수록 해당 알고리즘이 더욱 효율적이라고 볼 수 있다. 시간복잡도에서 알고리즘의 실행시간 상한선은 Big-O 표기법을 사용해 나타낸다. O(1) 상수의 형태 O(log n) 로그 형태 이진 탐색 O(n) 선형 형태 선형 탐색 O(n long n) 선형로그 형태 퀵정렬, 병합정렬(합병), 힙정렬 O(n^c) 다차 형태 선택정렬, 버블정렬, 삽입정렬 해당 표에서는 O(1)가 가장 빠르고 O(n^c)가 가장 오래 걸린다. 이러한 시간 복잡도는 대략적인 큰 숫자를 비교하는 것을 기본으로 한다. 이유는 작은 수를 하나하나 헤..
-
알고리즘 - merge sort (합병정렬)컴퓨터 기초/알고리즘&자료구조 2020. 7. 21. 04:53
합병 정렬(merge sort)란? 모여있는 데이터들을 요소가 단 1개가 될 때까지 계속 반으로 나누다가 1개로 나눠지면 그때부터 역으로 숫자를 1개씩 정렬하면서 올라가고 병합하는 방식 예를 들자면 다음과 같다. 7, 4, 5, 2, 6, 3, 8, 1 7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과 4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한 결과 2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한 결과 1 2 3 4 5 6 7 8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과 1. 우선적으로 숫자들을 각 요소가 1개가 될 때까지 계속 쪼갠다. 2. 2개의 데이터를 묶어서 비교해서 큰 수는 오른쪽, 작..
-
컴파일에 관해서(compile)컴퓨터 기초/컴퓨터 기초지식 2020. 7. 8. 00:39
1. 컴파일이란? 컴파일은 소스 코드를 오브젝트 코드로 변환시키는 과정으로, 간단히 말해서 우리가 프로그래밍 언어를 통해 쓴 언어를 기계어로 바꿔주는 역할을 하는 것이다. 2. 컴파일의 전체과정 컴파일의 전체 과정은 4단계로 이뤄진다. 프리 프로세서 - 컴파일 - 어셈블 - 링크 (1) 프리 프로세서(preprocessor, 전처리기) 실직적인 컴파일이 이뤄지기 전에하는 선행 과정. 헤더 부분에 해당하는 함수부를 해당 파일로 미리 불러오는 등의 역할을 하게 된다. (2) 컴파일(compile, 컴파일) 프리 프로세서 과정을 거친 소스코드를 어셈블리어로 변환한다. (3) 어셈블(assemble, 어셈블) 소스코드가 컴파일 과정을 거쳐 어셈블리어가 됐을 때, 어셈블리어를 cpu가 이해할 수 있도록 기계어로 ..
-
프로그래밍 관련 단어와 뜻컴퓨터 기초/컴퓨터 기초지식 2020. 6. 30. 02:33
프로그램 프로그램이란 입력을 받아서 출력을 내기 위한 순차적인 명령들의 집합을 말한다. 기계어 CPU가 직접 해독하고 실행할 수 있는 이해할 수 있는 비트 단위로 쓰인 컴퓨터 언어. 2진수인 0과 1로 나열되어 있어 해독하고 프로그래밍하기에는 힘들다. 기계어는 CPU제조사마다 다르며, 0과1을 이용해 만들어낸 명령어의 집합을 이야기한다. 어셈블리어와 어셈블러 어셈블리어는 기계어 한 단계 위의 언어로서 기계어와 함께 저급레벨의 언어다. 기계어의 숫자들을 문자로 바꿔서 이해하기 쉽게 만든 언어. 어셈블리어가 기계어와 가장 가깝다고 알려져있지만 그럼에도 CPU는 어셈블리어를 이해하지 못한다. 그렇기에 이를 이해하게 만든 것이 어셈블러다. 기계어와 마찬가지로 제조사에 따라 어셈블리어도 달라진다. 컴파일과 컴파일..
-
알고리즘 - selection sort (선택정렬)컴퓨터 기초/알고리즘&자료구조 2020. 6. 26. 03:45
선택정렬(selection sort)이란? 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수를 찾아) 첫 번째 위치 (혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬을 말한다. 선택은 교환 횟수를 최소화하지만, 반면에 각 자료를 비교하는 횟수는 증가한다. 간단히 말하면 1~10까지의 숫자가 뒤섞여 있으면, 가장 작은 숫자인 1을 찾아서 가장 왼쪽에 배열하고, 그 다음에는 1을 제외한 2~10이 뒤섞인 숫자에서 2를 찾아서 1 다음 배치하는 식으로 반복하여 정렬하는 방식을 말한다. list a = [3, 2, 5, 4, 1] 첫번째 리스트 a내의 n개의 숫자 중 가장 작은 숫자를 찾는다. 가장 작은 숫자 1을 가장 왼쪽에 놓는다. list a = [1, 3, 2, 5, 4] 이제 1을 제외한 n-..
-
알고리즘 - bubble sort(버블 정렬)컴퓨터 기초/알고리즘&자료구조 2020. 6. 26. 03:30
정렬의 필요성 정렬의 필요성은 간단하다. 원하는 자료를 더욱 빨리 찾을 수 있게 도와주기 때문이다. 어떤 수를 찾을 때 정렬이 되있지 않다면 장기적으로 보면 시간과 자원의 낭비가 적체되는 현상을 겪는다. 정렬이 되지 않으면 탐색 또한 효율적으로 진행될 수 없다. 버블 정렬(bubble sort) 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법. 첫번째 데이터부터 마지막 데이터까지 훑으면서 작은 값은 작은 값대로 큰 값은 큰 값대로 단 두개의 요소를 1대1로 교체해가면서 정렬하는 방식을 말한다. 즉 리스트 안에 있는 두 개의 인접한 수를 비교해서 순서에 맞지 않는다면 교환해주고 이를 계속 반복하는 방식. 예를 든다면 다음과 같다. #define _CRT_SECURE_NO_WAR..
-
알고리즘 - 선형탐색, 이진탐색컴퓨터 기초/알고리즘&자료구조 2020. 6. 26. 01:34
탐색이란? 특정 데이터의 모음에서 원하는 숫자를 찾아내는 것을 말한다. 탐색을 하는 알고리즘은 다양하게 있으며 그 중에서 현재 자료의 상태에 따라 가장 효율적인 알고리즘을 선택해서 사용할 수 있다. 선형 탐색 (linear search) inear는 직선모양의란 뜻을 가진 단어로서 순차 검색 (sequential search)이라고도 불리는 선형탐색은 원하는 데이터가 발견될 때까지 처음부터 마지막 자료까지 차례대로 탐색하는 것을 말한다. 선형 탐색 알고리즘은 정확하지만 아주 효율적이지 못한 방법이다. 운이 좋으면 금방 찾을 수 있지만 운이 나쁘다면 원하는 값을 얻어내기까지 오랜 시간이 걸린다. 그리고 이러한 선형탐색의 한계를 느끼면 오히려 자료의 정렬 등이 왜 중요한지 알 수 있다. 다만 정렬이 되어있지..
-
의사 코드컴퓨터 기초/컴퓨터 기초지식 2020. 6. 26. 01:21
의사코드(pseudo code)란? 의사코드란 알고리즘을 표현하는 하나의 방식으로 문법적 제약을 적게 받으며 자연어를 이용해 만든 문장을 프로그래밍 언어와 유사하게 배치한 코드를 뜻한다. 의사코드는 프로그래밍 언어가 아니다. 일반적으로 프로그램을 작성하기 전에 대략적으로 알고리즘의 작동을 알아보기 위해 시행하는 경우가 많다. 이를 통해 프로그램 작성 전 해당 알고리즘 모델을 더 쉽게 이해할 수 있는 효과가 있다. 다만 남들과 같이 보겠다면 어느 정도 규칙을 세워서 보기 좋게 만드는 것이 좋다.