속도 < 방향

edwith CS50강의를 보며 정리했습니다. 합병정렬 합병정렬은 원소가 한개가 될 때까지 계속 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다. 합병 정렬은 버블 정렬, 선택 정렬, 삽입 정렬보다 훨씬 빠르고 간결하고 깔끔하게 표현할 수 있다. 합병정렬의 시간복잡도 상한선은 $nlogn$이다. 다른 정렬의 최소 상한선은 $n^2$이고, 이는 $nlogn$보다 크다. 합병정렬은 시간적으로 빠르지만 단점도 존재한다. 합병 정렬은 더 많은 공간(메모리)을 사용한다. 8개의 자료가 있다고 하면, 세 번을 나눈다. $log28$은 3이다. 그리고 그 한번을 실행할 때마다 자료를 n번씩 봐야했기 때문에 $nlogn$으로 표현할 수 있다. 합병 정렬은 병합하는 알고리즘을 포함한다. 실행시간으로 표현을 한다면,..

edwith CS50강의를 보며 정리했습니다. 시간복잡도 앞서 배운 정렬을 진행할 때마다 시간이 소요되는데, 어떤 알고리즘을 수행하는 데 걸리는 시간을 시간복잡도라고 한다. 물리적인 시간이 아닌, 주어진 n개의 값을 활용하여 일반화한 복잡도를 의미한다. 일반적으로, 연산 횟수를 세며 이것이 측정 단위가 된다. 알고리즘을 수행할 때 걸리는 시간을 기준으로 효율성을 분석하는 것이다. 시간의 효율성이란 결국 알고리즘에서 비교와 교환 등이 일어날 때 연산자의 처리 횟수가 적다는 의미이며, 연산자의 처리 횟수가 적다는 건 시간의 복잡도가 낮다는 의미이다. 따라서 시간 복잡도가 낮을수록, 연산자의 사용 횟수가 적을수록 효율성이 높은 알고리즘이 된다. 예를 들어 버블 정렬이라면, 총 n개의 물체를 정렬할 때라고 가정..

edwith CS50강의를 보며 정리했습니다. 선형탐색 우리가 원하는 자료를 탐색할 때 사용되는 알고리즘 중 선형 탐색(linear search)은 자료를 찾을 때까지 모든 자료를 탐색해야 하는 방법이다. 선형(linear)이라는 단어의 뜻 그대로, 선의 모양처럼 일직선을 그대로 따라 탐색하는 방법이다. 만약 리스트의 길이가 n이라면, 가장 최악의 경우에는 가장 마지막에 찾고자 하는 숫자가 있을 때, n-1번만큼 자료를 탐색해야한다. 보통 어떠한 정보도 없거나 자료가 정렬되어 있지 않을 때 사용하는 방법이다. 보통 가장 왼쪽부터 오른쪽으로 하나씩 이동하며 탐색을 한다. 이런식의 무작위 탐색은 굉장히 비효율적이기 때문에, 탐색을 하기 전에 정렬이 필수적인 이유를 알 수 있다. 버블정렬 어릴 때 했던 게임 ..

edwith CS50강의를 보며 정리했습니다. ● 알고리즘 컴퓨터는 우리가 컴퓨터에 입력한 자료를 컴퓨터의 처리과정을 통해 출력 형태로 만든다. 즉 명령어들의 순서상 처리가 필요한데 이를 알고리즘이라고 한다. 마치 우리가 아침에 일어나서 양치하고, 밥을 먹고 옷을 입고 외출하는 과정처럼 순서대로 행동이 이루어지는 것과 비슷하다. 어떤 문제를 단계적으로 풀어가는 명령어의 집합이다. 하지만 순서를 잘못 놓는다든가, 비효율적으로 한다면 준비하는 데 시간이 오래 걸릴 것이다. 그래서 효율적으로 움직이기 위해 외출 경로를 바꾼다든가 하는 선택을 하는데, 알고리즘도 마찬가지이다. 알고리즘이 효율적으로 작동하도록 배열한다면 시간과 공간적으로 훨씬 여유있게 명령어가 작동될 수 있을 것이다. 좋은 알고리즘은 효율성이 좋..

edwith CS50강의를 보며 정리했습니다. ● 인공지능 (자연어처리) 우리는 소프트웨어를 작동하거나 컴퓨터 언어(프로그래밍 언어) 를 통해 컴퓨터와 상호작용을 하지만, 인간은 일상에서 컴퓨터 언어가 아닌 언어를 사용한다. 이것을 자연어 라고 부르는데, 컴퓨터가 이를 이해하도록 만들려면 자연어를 이해할 수 있도록 처리해야 한다. 가장 최초의 자연어 처리 프로그램은 1966년 조셉이 만든 ELIZA 라는 소프트웨어이다. ELIZA에서 사용하는 시스템을 패턴 매칭 (pattern matching) 이라고 하는데, 입력 받은 문자의 일부를 활용해 다시 사용자에게 반환해주는 시스템을 의미한다. 요즘은 이러한 시스템을 활용하여 구현된 챗봇을 쉽게 만날 수 있다. 사람의 언어를 기계적으로 분석하여 컴퓨터가 이해할..

edwith CS50강의를 보며 정리했습니다. ● 가상 현실과 증강 현실 우리는 일상에서 쉽게 가상 현실(VR, Virtual Reality) 과 증강 현실(AR, Augmented Reality)을 접한다. VR은 가상의 환경이나 상황을 컴퓨터로 만들어서 사람들이 실제로 그 상황에 들어와있는 것 처럼 느끼고 상호 작용할 수 있도록 만들어 주는 인터페이스를 뜻한다. AR은 가상현실과 기본적으로 비슷한데, 사용자에게 기존의 주변환경과 분리된 전혀 다른 환경을 경험하게 하지 않고 현재의 환경 위에 영상, 게임 등의 효과를 입히는 기술이다. 간단한 형태로는 휴대폰을 통해 유튜브나 페이스북으로 3차원 공간을 둘러볼 수 있는데, 네모난 액정 안에 3차원 공간이 다 담긴다. 혹은 구글 카드보드나 삼성 기어, 오큘러..

edwith CS50강의를 보며 정리했습니다. ● 이미지 파일 추리물을 좋아하는 사람이라면, 혹은 소싯적 TV 프로그램을 많이 봤다면 누구나 아는 프로그램이 있다. 바로 CSI 프로그램이다. 해당 프로그램에서 자주 나오는 화면이 영상을 멈춰서 확대하는 장면이다. 위의 이미지를 확대하면,,? 현실은 다르다. 한정된 비트들로 이루어진 이미지를 확대하면 이렇게 이미지가 번지거나 깨지는 현상을 볼 수 있다. 이런 현상이 발생하는 이유는 무엇일까? 우리가 컴퓨터와 해온 상호작용들은 대체로 모니터, 키보드, 마우스 등으로 이루어졌다. (물론 사람마다 다르겠지만) 하드디스크나 파일과 상호작용을 하는 빈도는 비교적 적다. '파일'은 무엇일까? 위의 사진은 'JPEG'의 확장명을 가지고 있는데, 이러한 파일들은 특정 비..

edwith CS50강의를 보며 정리했습니다. ● 16진수 사진 파일의 확장명인 jpg(jpeg)를 아는가? 모든 JPEG 파일의 첫 3byte는 이렇게 시작한다. 하지만 이렇게 10진수, 2진수만 사용하지는 않고 대체로 16진수 (hexadecimal) 를 사용한다. 0~9 다음부터 10~15의 숫자는 a,b,c,...f 등 알파벳으로 표현한다. 위의 숫자들을 2진수, 16진수로 나타내면 8bit 였던 걸 2bit로 구현할 수 있다. 하지만 ff, d8, ff 등으로 표현하지는 않고 16진수를 사용할 때는 관례적으로 빈 공간에 0x라는 것을 앞에 넣어서 위와 같은 표현으로 나타낸다. 16진수가 유용한 이유는 4bit 패턴과 완벽한 대응을 하기 때문이다. (2의 4제곱). 이를 활용하여 8bit나 1by..

edwith CS50강의를 보며 정리했습니다. ● ASCII 코드 컴퓨터가 숫자가 아니라 문자나 다른 것들을 나타내기 위해 하는 것이 있을까? 컴퓨터 업계에서는 숫자를 알파벳 문자에 대응시키는 표준 방법을 채택하였다. ASCII 는 아스키라고 읽으며 글자를 10진수로 대응하는 것이다. 우리가 '문자'를 표현하고 싶지만 컴퓨터는 '숫자'로만 언어를 처리하기 때문에 숫자를 글자로 변환하려면 비트 패턴으로 변환이 필요하다. 그럴 때 사용하는 것이 ASCII 코드이다. 알파벳 'A'는 65로 시작하는데, 2의 6제곱인 64까지 표기를 하고 그 이후에 시작하는 순서이다. 예를 들어 HI 라고 쓰고 싶다면, ASCII 코드로 숫자 72와 73을 나타내는 비트 패턴으로 전기신호를 보내 저장한다. 비단 문자뿐만 아니라..

edwith CS50강의를 보며 정리했습니다. ● 2진수 입력과 출력은 무엇일까? 우리는 컴퓨터가 0과 1만 사용하고 0,1로만 이해한다는 것을 안다. 하지만 과연 0,1 두 숫자로 노트북이나 pc가 어떻게 작동하는지 설명할 수 있을까? 일상생활에서는 일반적으로 10진수(decimal)를 사용한다. '10'이라고 하는 이유는 0에서 9까지의 숫자 10개를 사용하기 때문이다. 2진수(binary)는 0과 1까지의 숫자 2개만을 사용한다. 컴퓨터는 0과 1만으로도 어떤 데이터든 충분히 표현할 수 있다. 숫자, 문자, 그래픽, 영상 등 모든 정보가 가능하다. 우리가 위의 그림을 본다면 본능적으로 1,2,3 숫자 3개로 인식할 것이다. 왜냐하면 우리가 어릴 때 숫자를 배울 때 10 단위로 생각하도록 배웠기 때문..