-
[C] 포인터와 문자열
문자열을 선언하는 3가지 방법 문자열 리터럴 풀(Pool) 문자열 초기화 1. char배열로 문자열 초기화 배열의 크기를 지정하지 않은 방식이다 배열은 널문자를 포함하여 13byte할당되고 “Awesome day!” 문자열 리터럴이 배열에 복사된다. 배열 크기를 지정한 방식이다. 배열 크기를 널문자를 포함하여 문자열 리터럴의 문자개수보다 1개 더 많은 13개로 지정한 후 strcpy함수를 사용해 배열에 복사한다. 주의! 배열명에 문자열 리터럴을 대입할 수 없다. 왜냐하면…
-
[C] 포인터와 배열
배열과 포인터 차이 1차원 배열을 함수로 넘기기 2차원 배열 의미 2차원 배열이 다음과 같이 선언되었다고 했을때, 아래 3가지 표현이 의미하는 바는 무엇일까? int (*pmatrix)[5] = matrix는 무엇을 의미할까? 2차원 배열인 matrix를 가리키는 포인터 배열을 의미한다.
-
[C] 비트조작
비트 컴퓨터에선 보통 8비트 바이트가 사용된다. 8개의 비트들이 왼쪽부터 오른쪽으로 0에서 7까지의 번호가 매겨져 있다고 생각할 수 있다. 비트 7번을 최상위 비트, 비트 0번을 최하위 비트라 한다. 각각의 비트 번호는 하나씩 증가되는 2의 거듭제곱에 대응한다. 비트 단위 논리연산자 NOT(부정) 연산자: ~ 단항 연산자이다. 각 비트에 대해 1은 0으로, 0은 1로 바꾼다. AND(논리곱) 연산자: & 이항 연산자이다. 피연산자들의 대응하는 두 비트가 모두 1일 때에만 결과 비트가 1이다. 즉, 피연산자들의 대응하는 두 비트가 모두 참일 때에만 결과 비트가 참이다. OR(논리합) 연산자: | 이항 연산자이다. 피연산자들의 대응하는 두 비트 중 어느 하나라도 1이면 결과 비트가 1이다. 즉, 피연산자들의 대응하는 두 비트 중 어느 하나가 참이면, 또는 둘 다 참이면, 결과 비트가 참이다. XOR(배타적논리합) 연산자: ^ 이항 연산자이다. 피연산자들의 대응하는 두 비트 중 어느 하나가 (둘 다가 아닌) 1이면 결과…
-
빅 오로 코드 속도 올리기(feat.버블정렬)
버블 정렬의 효율성 버블 정렬은 정렬 알고리즘의 가장 기본이다. 버블 정렬으로 오름차순으로 정렬할 경우, 인접한 두 요소를 비교하여 왼쪽값이 더 크면 두 요소를 교환함으로써, 가장 큰 값부터 맨 오른쪽으로 옮기는 과정을 반복한다. 교환이 반복적으로 일어남에 따라 값이 오른쪽으로 이동하는 모습이 마치 버블같다고 하여 버블정렬이라 불린다. 버블 정렬의 주요 단계는 비교와 교환이다. 정렬되지 않은 배열에서 버블 정렬을 할 경우 비교가 몇 번 이루어지는지 알아보자. 예를 들어 요소가 5개인 배열이 있을 때 첫 번째 패스, 즉 첫 순회에서는 4번의 비교가 이루어진다. 4번의 비교 또는 교환으로 마지막 요소가 정렬되면 다음 패스에서는 비교할 범위가 1만큼 줄어든다. 마지막 요소는 이미…
-
빅 오 표기법이란?
빅 오 표기법이란? 알고리즘의 효율성을 결정하는 주요 요인은 알고리즘 수행에 필요한 단계 수이다. 이를 시간 복잡도라 부른다. 빅 오 표기법은 자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용한 것이다. 빅 오 표기법의 목적은 시간 복잡도를 보다 더 쉽게 소통하기 위함이다. 알고리즘에 필요한 단계 수를 빅 오로 표현하는 방법 최악의 경우 즉, 찾고자 하는 데이터가 맨 마지막에 있거나 배열에 없을 경우, 선형 검색에 필요한 단계 수는 배열의 원소 수만큼이다. 이를 빅 오 표기법으로 표현한다면 다음과 같다. O(N) 이를 “빅 오 N” 또는 “차수 N”라고 부른다. 의미는 알고리즘에 N단계가 필요하다는 것이다. 시간 복잡도가 O(N)인 알고리즘을 선형 시간을 갖는 알고리즘이라고도 한다. 1장에서 배열 읽기 연산에 필요한 단계 수를 살펴본 바 있다. 컴퓨터는 메모리 주소와 간단한 덧셈을 통해 인덱스에 한번에 접근할 수 있기 때문에 읽기 연산에 필요한 단계 수는 1단계라 했다. 이를 빅 오로 표현하면 다음과 같다. O(1) 배열에 원소가 몇 개이든 읽기는 항상 한 단계면 된다. 데이터가 아무리 많이 늘어나도 O(1)의 시간복잡도를 가진 알고리즘의 단계 수는 증가하지 않는다. 이러한 이유로 O(1)은 가장 빠른 알고리즘 유형으로 분류되며, 상수 시간을 갖는 알고리즘이라고도 불린다. 그렇다면 데이터가 몇 개든 항상 3단계가 걸리는 알고리즘은 O(3)으로 표현될까? 답은 ‘아니오’다. 위의 경우도 O(1)로 표현된다. 왜냐하면 사실 빅 오가 진짜로 의미하는 바는 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는가이기 때문이다.…