탐색

탐색 = 특정값을 찾는 로직

ㄱ.순차탐색
순차적으로 처음부터 끝까지 보면서 원하는 값을 찾는것

int seq_search(int list[], int n, int key);

int main(void)
{
int key;
int grade[SIZE] = { 10, 20, 30, 40, 50, 60 };

printf("탐색할 값을 입력하시오:");
scanf("%d", &key);
printf("탐색 결과 = %d\n", seq_search(grade, SIZE, key));
return 0;
}

int seq_search(int list[], int n, int key)
{
int i;
for(i = 0; i < SIZE; i++)
if(list[i] == key)
return i; // 탐색이 성공하면 인덱스 반환

return -1; // 탐색이 실패하면 -1 반환
}

printf 함수 호출문을 보면 인자로 함수호출문을 쓴걸 볼 수 있는데 이건 함수호출문의 결과값이 들어간 것이며,반환값이 int형이여야한다는걸 의미함

순차탐색 함수 정의문에선 매개변수로 배열(int list[]), 사이즈(int n), 찾을려고하는 키값(int key) 3가지를 받는다.이걸로 체크하고자하는것은 "이 배열의 i번째 원소가 Key값과 같냐?"임.

for문이 끝났는데 리턴값이 안나왔다면 그것은 key값을 못찾았단 뜻.그러면 return -1;을 하겠단 소리임.

순차탐색은 시간복잡도가 안좋게나온다.

• 시간복잡도 : 코드를 얼마나 효율적으로 짰냐를 정량적으로 표시,코드를 한바퀴 실행하는데 시간이 얼마나 걸리냐 측정을 한다.

ㄴ.이진탐색
이진(=2개의 선택지) 즉 두 개의 선택지로 나눠서 계속 특정값을 찾아가는것.
순차탐색보다 효율이 좋다. 단, 정렬되어있다는 가정하에 가능하다 = 단점

low, middle, high를 가지고 찾는데 중간값이 middle을 기준값으로 갖는다.

전체 인덱스 크기(low 인덱스 + high 인덱스)를 반으로 나눈 그 지점의 인덱스 값을 middle로 잡고 내가 원하는 key 값이 middle보다 큰 값이면 middle 오른쪽 값들만 보면된다.(작다면 왼쪽 값들만)

그렇게 미들값을 제외하고(이 숫자는 아니니깐) 다음숫자부터 오른쪽 끝 숫자만 두고 봤을때 다시 그 중간 인덱스의 값을 middle값으로 잡고 범위 이동해 key값을 찾는다.없으면 또 다시 비교해서 범위를 좁혀나간다.

코드예시
int binary_search(int list[], int n, int key)
{
int low, high, middle;
low = 0;
high = n - 1;

while (low <= high){ // 아직 숫자들이 남아있으면
middle = (low + high) / 2; // 중간 요소 결정
if (key[] == list[middle] ) // 일치하면 탐색 성공
return middle;
else if (key > list[middle]) // 중간 원소보다 크다면
low = middle + 1; // 새로운 값으로 low 설정
else
high = middle - 1; // 새로운 값으로 high 설정
}
return -1;
}

코드는 위와 같으며

while (low <= high)
-> while 반복문은 조건이 true일때는 계속 돈다.false가 되어야 탈출이 가능함.
-> (low <= high)라는 조건식은 low 인덱스와 high 인덱스 간에 역전(low와 high가 서로 타고타고 서로를 지나쳐 위치가 바뀌어버린 것,역전이 곧 false)이 일어날때까지 해준건데 큰 의미가 있는 조건식은 아니고 key[] == list[middle] 이 조건식이 핵심이다.

만약 찾고자하는 값이 없다면 이 값이 마지막 middle값보다 크다고 가정할 때, else if (key > list[middle])를 거쳐 low가 middle 인덱스를 넘어가 역행하게된다. 여기서 조건을 설정해주지않으면 컴퓨터는 low랑 high를 무한으로 이동시키게됨.

2차원 배열

2차원 배열을 일반적인 행렬 모양과는 달리 실제 메모리에선 행 단위의 메모리가 수평적으로 붙어서 일렬로 나열되어있다.

2차원 배열을 다룰땐 항상 2중 for문을 써야한다.

int s[ ][ ]는 배열 인덱스끼리 곱한만큼 돌리는 것이다.(3,5면 15번임)

#include <stdio.h>

int main(void)
{
int s[3][5]; // 2차원 배열 선언
int i, j; // 2개의 인덱스 변수
int value = 0; // 배열 원소에 저장되는 값

for(i=0;i<3;i++)
for(j=0;j<5;j++)
s[i][j] = value++;

for(i=0;i<3;i++)
for(j=0;j<5;j++)
printf("%d\n", s[i][j]);
return 0;
}

예시로 위와 같은 코드가 있는데, 3행 5열의 2차원 배열을 선언했으면 이말은 for문을 총 15번 돈다는 소리다.돌면서 배열의 각 인덱스에 value가 하나씩 쌓이는 것임.

1 2 3 4 5
5 6 7 8 9 -> 이런식으로
10 11 12 13 14

중첩 for문에서 항상 밖의 for문 i는 행의 배열을 의미하고, 내부의 for문 i는 열의 배열을 의미한다.

2차원배열의 초기화는
int s[3][5] = {;

int s[3][5] = {
{ 0, 1, 2, 3, 4 }, // 첫 번째 행의 원소들의 초기값
{ 10, 11, 12, 13, 14 }, // 두 번째 행의 원소들의 초기값
{ 20, 21, 22, 23, 24 }, // 세 번째 행의 원소들의 초기값
};
이런식으로 중괄호를 한번 더 묶어서 초기화한다.

또한
int s[ ][5] = {
{ 0, 1, 2, 3, 4 }, // 첫 번째 행의 원소들의 초기값
{ 10, 11, 12, 13, 14 }, // 두 번째 행의 원소들의 초기값
{ 20, 21, 22, 23, 24 }, // 세 번째 행의 원소들의 초기값
};

이런식으로 앞 행 배열의 인덱스 크기가 안잡혀있는채로 초기화해도 가능하다.
단,열의 배열의 인덱스가 공란일때는 불가능(-> 이경우는 복잡해져 컴파일러가 해주기 힘들기에 안된다생각하자)

int s[ ][5] = {
0, 1, 2, 3, 4, // 첫 번째 행의 원소들의 초기값
5, 6, 7, 8, 9, // 두 번째 행의 원소들의 초기값
};

보통은 초기화 안해준 부분은 '0'으로 채워주는데,이 경우는 내부에 중괄호가 없는 경우의 초기화식인데 이렇게 { }안에 한꺼번에 원소를 다넣을시 그냥 열 배열 인덱스 단위로 끊어서 초기화 시켜버린다.컴퓨터 입장에선 저렇게 한번에 넣으면 나머지 인덱스를 다 0으로 채울 생각도 하고 0을 1부터 9사이에 넣을 생각도 하는데 그냥 1부터 9를 넣고 그 이후에 다 0으로 채워넣어서 초기화하는 한가지 방식으로 생각해서 저렇게 한다.

포인터 변수

1.개념

=주소값을 저장한 변수
=주소값을 가지고있는 변수
=변수를 가리키는 변수

주소값을 다룬다 = 메모리에 직접 접근이 가능함 = 메모리를 읽거나 변경하는게 가능함

일반 변수와 포인트 변수의 차이는 가지고 있는 값이 자료형 값이냐 주소값이냐의 차이다.
일반 변수는 이름으로 불려서 운영체제의 도움으로 메모리에 간접 접근하는것으로 운영체제가 메모리를 할당해줄때 주소값이랑 이 변수의 이름을 일대일로 매핑을 해놓고 기록해놔서 그것을 다시 찾아서 접근이 가능한것이다.한마디로 이름을 통한 접근은 운영체제에 도움으로 접근하는것이다.
(포인트 변수도 운영체제의 개입이 없는건 아니지만 지금 시점에선 이렇게 이해하기)

*메모리 구조
메모리는 1바이트 씩 관리를 한다.(도식화하면 바이트 한 칸당 1바이트라고 생각하면됨)
왜 비트 단위가 아닌가? 가장 작은 자료형인 불리언도 1바이트로 1비트로 쓰는 경우는 잘 없어서그렇다.비트에 대한 개념은 추후에 정리

*보통 int형 4바이트에는 +- 21억대까지 숫자가 표현 가능한데 변수에선 값을 표현할때 2진수로 표현하는건지 10진수로 표현하는건지?

-> 컴퓨터는 이진수로 32비트에 표현하는거임(21억은 사람입장에서 10진수로 표현했을때 나온 수)

2. 포인트 변수 관련 용어
   엔드연산자(&) : 변수의 주소를 계산하는 연산자
   여기서 말하는 변수의 주소는 주소값 즉 첫번째로 시작하는 주소를 의미함.시작만 알면 크기를 알면 끝을 알 수 있음.

ex) 변수가 i라면 i의 주소값을 &i라고 표현

주소값의 형식지정자는 별도로 있는게 아니라 이것 역시 자료형에 따라 형식지정자 쓰면된다.다만 주소값이 부호없는 10진수이기에 보통은 다음과 같은 자료형을 쓴다.

%u -> 부호없는 10진수 (4바이트) -> unsigned int
%lu -> 부호없는 10진수 (8바이트) -> unsigned long

• 주소값은 어디에서나 같은 정형화된 값이 아니다.단지 메모리에 접근하기위한 값인데 주소값은 자리수도 다를 수도 있고, 컴퓨터를 킬 때마다 다를 수도, 컴퓨터의 종류, 사용자에 따라 다를 수도 있다.

3.포인트 변수의 구조

ex)
int i = 10; // 정수형 변수 i 선언
int * p = &i; // 변수 i의 주소가 포인터 p로 대입

-> int형 포인트변수 p는 i의 주소값을 가리키고있다.

포인터 변수 선언할 때는 * 을 써준다.

• 포인터변수에는 일반값을 넣으면 안된다.
  왜냐면 우리가 넣은 값이 일반값인지 주소값인지 컴퓨터가 구분을 할 순 없는데, 일반값을 입력하면 자체를 주소값으로 인식해서 입력하면 그 주소값을 건드리게되는데 그 공간이 운영체제를 건드릴 수도 있기에 넣으면안된다.
  출처를 알수 없는 숫자값은 확인 똑바로 하자.
  앞서 말한것처럼 여러 환경에 따라 주소값이 달라지기에 다른 프로그램을 건드릴 수도 있다.(주소값은 내가 가지고있는 메모리 내부에만 있으며, 명확한 컨트롤이 어렵다.)

• 포인터 변수에 자료형을 붙여주는 이유
  포인터변수가 가리키는 변수들이 다양한 자료형을 가지는데 하나의 포인터로 다 가리키게되면 너무 무분별하게된다.이 말은 곧 아무 변수에나 다 접근이 가능하다는 소리인데 어떤 메모리에라도 어떤값들을 써 넣을 수 있다는 것이다.

예로 들어 포인터변수가 4바이트의 float형의 변수의 주소값을 가지고 있는데 여기에다가 1바이트의 char형 값을 넣어버릴수도 있다는 뜻이다.1바이트만 덮어씌워지고 나머지 3바이트는 공란이 되는것이다. 이때 변수는 할당된 바이트를 다 써야 값이 유효하기에 컴퓨터는 공란까지 인식해서 제대로 된 결과를 볼 수 없다.

그런고로 무분별한 데이터 입력을 막기위해 담을 변수의 자료형과 포인트 변수의 자료형을 맞춰줘야한다.

4.포인터 변수의 사용법(=간접 참조 연산자)

포인터변수로 어떻게 메모리에 직접 접근할까?

내가 포인트변수 p를 가지고 i의 값을 출력하고싶을때는
p는 첫번째 주소값을 가지고있다는것을 이용하면된다.(메모리에 접근한다는 것은 두 가지를 의미하는데 그 중 하나가 데이터를 읽을 수 있다는 것이다.)즉 읽은 데이터를 출력하는것이 가능함!

• 의 해석 두 가지
  int p = &i;의

printf("%d\n", p)의

이 두 는 서로 다른 로 봐야된다. 전자의 즉, 자료형과 변수 사이의 는 포인터변수라고 선언해주는 표시다.
후자의 * 는 내가 가리키는 곳에 있는 데이터값을 의미한다.

변수별 출력법
일반 변수 -> 변수를 찍는다.
포인터 변수 -> 포인터 변수로 가리키는 곳의 값을 찍는다.

변수별 값 변경법
일반 변수 -> =로 대입 i = 20;
포인터 변수 -> * 과 = 을 이용해서 대입

• p = 20; : p가 가르키는 변수의 값에다가(주소값x) 20을 넣어줘

5. 포인터 변수의 자체 값도 존재한다!(물론 그 값이 가리키는 변수의 주소값이다.)
   포인터 변수도 변수이기에 운영체제로부터 메모리를 할당받는다.그 안에 가리키는 변수의 주소값이 들어가게되는것이다. 그래서 p를 printf 해보면 주소값이 그대로 출력된다.

• p의 * 은 선언할때만 필요한거지 이후엔 p로만 써도된다.그리고 포인터 변수는 레이저포인터처럼 한 대상에만 직선으로 빛을 쏜다.이 말은 포인터 변수는 하나의 변수만 가리킬 수 있으며 다른 변수를 가리키면 주소값이 덮어씌워진다.

• 포인터 변수의 주소값은 어떤 변수의 주소값이라고하는걸 메모리 공유한다는것과 햇갈리지말자!!!!!
  메모리는 각 변수들이 각 할당된 곳에 위치하게되며 포인터 변수도 애초에 변수여서 운영체제로부터 할당받은 자체 메모리 공간이 존재한다.그 주소와 가리키는 변수의 주소는 다르다.

포인터 변수의 값 = 다른 변수의 주소값, 주소 = 자체 할당받은 주소

• scanf는 호출할 때 인자로 &를 써서 변수의 주소값을 계산해서 정의문으로 받아오는데
  받아온 주소값이 어디에 저장되냐면 정의된 함수 내 포인터 변수에 저장된다.

• int * p = NULL;(c++에선 NULLptr;)

NULL은 '없다'라는 유일한 단어로 '0'이 아니다.포인터 변수 및 주소값 용도 목적으로 만들어진 단어로 아직 가리킬 것이 없을때 쓰인다.용도에 맞게 만들어진것이다보니 &필요x