야곰야곰's S/W 공부

연결 리스트는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 사용자가 어떤 애플리케이션에서 배열을 사용 중이라면 아마도 배열 대신 연결 리스트를 쓰고 있을 가능성이 크다. 연결 리스트는 나란히 이어진 메모리 셀 묶음이 아니다. 서로 인접하지 않음 메모리 셀 묶음으로 이뤄진다. 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다. 서로 인접하지 않은 이러한 셀을 노드라 부른다. 각 노드는 노드에 저장된 데이터뿐만 아니라 연결 리스트 내에 다음 노드의 메모리 주소도 저장해야 한다. 위 그림을 보면 연결 리스트에 "a", "b", "c", "d", 4개의 데이터가 있다. 하지만 데이터를 저장하는 데 각 노드마다 메모리 셀 두 개씩, 총 메모리 셀 여덟 개를 사용한다. 연결 리스트를 다루는 코드..

무작위로 정렬된 배열이 있을 때, 정렬은 안 해도 되지만 배열에서 열 번째로 작은 값 혹은 열다섯 번째로 큰 값을 알고 싶다고 하자. 가령 수많은 시험 점수가 있을 때 25번째 백분위수나 중간 점수를 알고 싶을 때 도움이 될 것이다. 전체 배열을 정렬한 후 적절한 셀을 바로 찾아보면 확실히 문제를 해결할 수 있지만 퀵 셀렉트라고 알려진 뛰어난 작은 알고리즘으로 훨씬 더 나은 성능을 낼 수 있다. 퀵 셀렉트도 퀵 정렬처럼 분할에 기반하며, 퀵 정렬과 이진 검색의 하이브리드 정도로 생각할 수 있다. 값이 8개인 배열이 있을 때 이 배열 내에서 두 번째로 작은 값을 찾고 싶다고 하자. 먼저 전체 배열을 분할한다. 분할 후 피벗은 배열의 중간 부분에 있을 것이다. 이제 피벗은 올바른 위치며, 다섯 번째 셀이므로..

퀵 정렬 알고리즘에서 분할은 매우 중요하다. 분할 배열을 분할한다는 것은 배열로부터 임의의 수를 가져와(이 수를 피벗이라고 부름) 피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다. 아래와 같은 stormpy.tistory.com 퀵 정렬 알고리즘은 아래와 같이 동작한다. 배열을 분할한다. 피벗은 이제 올바른 위치에 있다. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또 다른 배열로 보고 1단계와 2단계를 재귀적으로 반복한다. 하위 배열이 원소를 0개 또는 1개 포함하면 기저 조건이므로 아무것도 하지 않는다. #include #include using namespace std; class CSortArray { public: CSortArray() = defa..

배열을 분할한다는 것은 배열로부터 임의의 수를 가져와(이 수를 피벗이라고 부름) 피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다. 아래와 같은 배열이 있다고 하자. 일관된 설명을 위해 가장 오른쪽에 있는 값을 항상 피벗으로 하고 3을 이용해 분할해 보자. 두 개의 포인터를 사용해 하나는 배열 가장 왼쪽에 있는 값에, 다른 하나는 가장 오른쪽 있는 값에 할당한다. 분할은 다음의 단계를 따라 실제 분할한다. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다. 오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다. 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다. 두 포인터가 ..

재귀는 함수가 자기 자신을 호출할 때를 말하는 공식 명칭이다. 일반적으로 무한 함수 호출은 쓸모가 없고 위험하기까지 하지만 재귀는 활동 가능성이 큰 강력한 도구다. 10에서 0까지 카운트 다운하는 함수를 만들어 보자. #include using namespace std; void countdown(int number) { for (int i = number; i >= 0; i--) cout

큐는 간결하게 임시 데이터를 다루며 제약이 있는 배열이라는 점에서 스택과 비슷하다. 다만 데이터를 처리하는 순서가 다르므로 작업 중인 애플리케이션의 요구에 따라 선택한다. 극장에 줄 서 있는 사람들을 큐처럼 생각할 수 있다. 줄 맨 앞에 있는 사람이 그 줄을 떠나 가장 먼저 극장에 들어간다. 큐 역시 큐에 첫 번째로 추가된 항목이 가장 먼저 제거된다. 그래서 컴퓨터 과학자는 큐를 FIFO(first in, first out)이라 한다. 큐는 다음과 같은 제약을 포함한다. 데이터는 큐의 끝에만 삽입할 수 있다. 데이터는 큐의 앞에서만 읽을 수 있다. 데이터는 큐의 앞에서만 삭제할 수 있다. 빈 큐로 시작해서 큐의 동작을 알아보자. 먼저 5를 삽입하자. ( 스택 삽입은 push라고 하지만 큐 삽입은 put,..

스택이 데이터를 저장하는 방법은 배열과 같다. 단순하게 얘기하면 원소들의 리스트다. 다만 스택에는 다음과 같은 제약이 있다. 데이터는 스택의 끝에만 삽입할 수 있다. 데이터는 스택의 끝에서만 읽을 수 있다. 데이터는 스택의 끝에서만 삭제할 수 있다. 접시를 스택이라고 생각해 보면 가장 위에 있는 접시를 제외하고는 다른 접시의 윗면을 볼 수 있다. 비슷하게 가장 위를 제외하고는 접시를 추가할 수도, 제거할 수도 없다(끼워넣기 안돼요). 실제로 대부분의 컴퓨터 과학책에서 스택의 끝을 top, 스택의 시작을 bottom이라고 부른다. 빈 스택부터 시작해서 스택의 동작을 알아보자. 스택에 새 값을 삽입하는 것을 스택에 푸시한다고 한다. 스택에 5를 푸시하자. 특별할 것은 없다. 그저 배열 끝에 데이터를 삽입하는..

대부분의 프로그래밍 언어는 해시 테이블(hash table)이라는 자료 구조를 포함하며, 해시 테이블에는 빠른 읽기라는 놀랍고 엄청난 능력이 있다. 해시 테이블은 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다. 해시 테이블은 쌍으로 이뤄진 값들의 리스트다. 첫 번째 항목을 키라 부르고, 두 번째 항목을 값이라 부른다. 해시 테이블에서 키와 값은 서로 중요한 관계다. 해시 테이블의 값 룩업은 딱 한 단계만 걸리므로 평균적으로 효율성이 O(1)이다. 해싱 문자를 가져와 숫자로 변환하는 이러한 과정을 해싱이라고 부른다. 또한, 글자를 특정 숫자로 변환하는 데 사용한 코드를 해시 함수라 부른다. 이밖에도 해시 함수는 많다. 또 다른 해시 ..

삽입 정렬의 수행 순서는 다음과 같다. 1. 첫 번째 패스스루에서 임시로 인덱스 1(두 번째 셀)의 값을 삭제하고 이 값을 임시 변수에 저장한다. 인덱스 1에 값이 없으므로 공백이 생긴다. 이후 각 패스스루마다 다음 인덱스의 값을 삭제한다. 2. 다음으로 공백 왼쪽에 있는 각 값을 가져와 임시 변수에 있는 값과 비교하는 시프트 단계를 시작한다. 공백 왼쪽에 있는 값이 임시 변수에 있는 값보다 크면 그 값을 오른쪽으로 시프트 한다. 값을 오른쪽으로 시프트 했으므로 자연히 공백이 왼쪽으로 옮겨진다. 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 시프트 단계가 끝난다. 3. 이제 임시로 제거한 값을 현재 공백에 삽입한다. 4. 배열이 완전히 정렬될 때까지 1단계부터 3단계를 반복한다. #..

선택 정렬은 다음과 같은 단계를 따른다. 1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정한다. 한 셀씩 이동하면서 현재까지 가장 작은 값을 변수에 저장한다. 변수에 들어 있는 값보다 작은 값이 들어 있는 셀을 만나면 변수가 새 인덱스를 가리키도록 값을 대체한다. 2. 이제 최솟값이 어느 인덱스에 들어 있는지 알았으므로 그 인덱스의 값과 패스스루를 처음 시작했을 때의 값을 교환한다. 패스스루를 시작했을 때 인덱스는 첫 패스스루에서 인덱스 0일 것이고, 두 번째 패스스루에서는 인덱스 1일 것이다. 3. 데이터가 모두 정렬될 때까지 1, 2단계를 반복한다. #include using namespace std; void selectionSort(vector& array) { ..

배열의 중복 값이 있는지 확인하는 함수를 만든다고 해보자. 가장 먼저 떠오리는 방법은 중첩 for문을 이용하는 것이 아닐까 싶다. bool hasDuplicateVal(int* list, unsigned int len) { for (int i=0; i

버블 정렬이란? 매우 기본적인 정렬 알고리즘인 버블 정렬(Bubble sort)은 이해하기 쉽기 때문에 단순 정렬(simple sort)이라 불린다. 다만 빠르다고 알려진 정렬 알고리즘보다는 비효율적이다. 버블 정렬은 다음과 같은 단계를 따른다. 1. 배열 내에서 연속된 두 항목을 가리킨다. 첫 번째 항목과 두 번째 항목을 비교한다. 2. 두 항목의 순서가 뒤바뀌어 있으면 (왼쪽 값이 오른쪽 값보다 크면) 두 항목을 교환(swap)한다. 순서가 올바르다면 아무것도 하지 않는다. 3. 비교 위치(포인터)를 오른쪽으로 한 셀씩 옮긴다. 4. 더 이상 교환하지 않을 때까지 1단계부터 3단계까지 반복한다. 더는 교환을 하지 않는다는 것은 배열이 정될된 상태라는 뜻이며 1 ~ 3 단계를 반복하는 것을 패스스루(p..

단계적 통합 단계적 통합 과정은 다음과 같다. 각 루틴에 대해 설계, 코딩, 테스트, 디버그를 한다. 이 단계는 "단위 개발"이라 부른다. 루틴들을 하나의 거대한 시스템으로 묶는다. 이것은 "시스템 통합"이라 부른다. 전체 시스템을 테스트하고 디버그 한다. 이것은 "시스템 분해"라고 부른다. 단계적 통합의 한 가지 문제는, 시스템의 루틴들이 처음에 합쳐질 때, 새로운 문제가 필연적으로 드러나고, 그 문제의 원인은 어디에나 있을 수 있다는 것이다. 특정 문제의 위치에 대한 불확실성은 모든 문제들이 갑자기 정체를 드러낸다는 사실에 의해 복잡해진다. 단계적 통합은 모든 루틴들이 단위 검사된 후, 프로젝트의 후반부까지는 시작될 수 없다. 루틴들이 최종적으로 결합되고 오류가 행운에 의해 드러날 때, 프로그래머들은..

베르누이 시행 어떤 사건이 '일어난다'와 '일어나지 않는다'의 두 가지 결과만을 가지는 시행을 베르누이 시행이라고 한다. 예를 들어, 제비뽑기에서 '당첨'과 '꽝', 아기가 '배가 고프다'와 '고프지 않다'와 같은 경우 등이다. 베르누이 확률변수 아기가 우는 시행에서 배가 고픈 사건의 확률을 p라고 하면, 배가 고프지 않은 사건의 확률은 1 - p 일 것이다. 이때 배가 고픈 사건을 1, 배가 고프지 않은 사건을 0에 각각 대응시킨 확률변수를 베르누이 확률변수라고 한다. 베르누이 확률분포 베르누이 확률변수가 따르는 확률분포를 베르누이 확률분포라 하고, 베르누이 확률분포의 확률 질량 함수는 다음과 같다.

통계학에서 선형 회귀(linear regression)는 종속 변수 y와 한 개 이상의 독립 변수 (또는 설명 변수) x와의 선형 상관관계를 모델링하는 회귀분석 기법이다. 한 개의 설명 변수에 기반한 경우에는 단순 선형 회귀(simple linear regression), 둘 이상의 설명 변수에 기반한 경우에는 다중 선형 회귀라고 한다. 선형 회귀는 선형 예측 함수를 사용해 회귀식을 모델링하며, 알려지지 않은 파라미터는 데이터로부터 추정한다. 이렇게 만들어진 회귀식을 선형 모델이라고 한다. 선형 회귀 모델 이해 데이터의 개수가 많아지면 모든 점을 동시에 지나가는 직선을 하나로 정하기는 어려워진다. 이 경우, 좌표평면 위에 표현된 데이터를 바탕으로 데이터 간의 관계를 가장 잘 대표할 수 있는 직선의 함수를..

상관 분석(Correlation analysis, 상관관계, 상관)은 확률론과 통계학에서 두 변수 간에 어떤 선형적 또는 비선형적 관계를 갖고 있는지를 분석하는 방법이다. 두 변수는 서로 독립적인 관계이거나 상관된 관계일 수 있으며 이때 두 변수 간의 관계의 강도를 상관관계(Correlation analysis)라고 한다. (위키백과) 상관관계 상관관계는 일정한 수치로 계산되어 두 대상이 서로 관련성이 있다고 추측되는 관계를 말한다. '상관 연구'는 연구 대상 간의 상호 관련성을 알아보는 데 사용된다. 관계성의 정도는 상관계수(correlation coefficient)라고 불리는 수치로 표시된다. 상관 계수는 양(+)의 값 혹은 음(-)의 값을 가진다. 상관 계수가 0일 때는 대상 간에 아무 관련성이 ..

K-NN 알고리즘이란 새로운 데이터가 들어왔을 때 특성 공간 내에 데이터 간의 거리가 가까운 데이터를 찾아서 그것의 레이블의 값으로 분류하는 알고리즘이다. 이때 K는 특성 값을 기준으로 가장 거리가 가까운 데이터의 개수를 의미한다. 그림에서 초록색으로 표시된 새로운 데이터를 노란색으로 분류할지 파란색으로 분류할지를 결정하는 문제를 가정해 보자. K-NN 알고리즘으로 분류한다면, 입력된 데이터의 특성 공간에서 가장 가까운 거리의 데이터가 어떤 색인지 확인한다. 만약 K가 1인 경우, 다음 그림과 같이 새로 입력된 초록색 데이터에서 가장 가까운 거리에는 주황색 데이터가 있다. 그러므로 새로 입력된 데이터는 주황색 데이터로 분류된다. K가 3인 경우를 보면 새로 입력된 초록색 데이터를 중심으로 가장 거리가 가..

서로 간에 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했는데 이 개념을 형식화한 것이 빅 오 표기법이다. 빅 오 표기법은 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있는 장점이 있다. 빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다. 1 단계만 필요한 알고리즘은 다음과 같이 표기한다. O (1) 일반적으로 "빅 오 1"이라고 발음한다. "차수 1"이라고도 한다. O (1)은 데이터의 크기에 상관없이 알고리즘에 필요한 단계 수가 일정하다는 의미다. 배열에 N개의 원소가 있을 때 선형 검색은 최대 N단계가 걸리는데 빅 오 표기법으로는 다음과 같다. O (N) 상수 시간과 선형 시간 O(..