[GeeksforGeeks: 알고리즘 기초 1편] 선형탐색(Linear Search)

접어두었던 개발 블로그에서 초심을 찾기 위해 공부하는 내용들을 완전히 제 멋대로 강의노트 필기하듯이 써봤어요.

3년 차 자바 JS 2툴 반쪽짜리 개발자의 C, C++, C# 형제들과, 파이썬, PHP 등 힙한 언어도 공부할 겸해서 포스팅 시작합니다.

 

생 초짜들이 공부할 개념들을 제가 알아보는 기준으로 막 쓴 거라 읽어 보시고 공부하시던지,  아니면 던져드린 링크를 읽고 하시던지 선택은 자유~

 

[내 멋대로 풀이 및 학습]

선형 검색(Linear Search)

-명제
arr [] 안에 있는 arr [i] 값 중에 x값이 어디에 있는지 체크하고 리턴하는 문제
-풀이[psuedo code]
hash, list, array 모두 length 또는 Size 반복문으로 1:1 비교를 시키고 index로 리턴한다.

https://www.geeksforgeeks.org/linear-search/

솔직히 1번 문제라 너무 간단하다.

 

Linear Search - GeeksforGeeks

링크 참고

[언어별 짤지식 배우기]
1. C++

// C++ code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
 
#include <iostream>
using namespace std;
 
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
 
// Driver code
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
   
    // Function call
    int result = search(arr, n, x);
    (result == -1)
        ? cout << "Element is not present in array"
        : cout << "Element is present at index " << result;
    return 0;
}

a) #include<iostream>
 : io를 C++ 방식으로 하겠다는 뜻 C++ 내장 라이브러리 추가
b) namespace 
 : C++의 특정 영역에 함수와 변수명을 독립적으로 선언하는 법 
namespace 안에 있는 요소는 :: 스코프 분석 연산자로 표기 가능 (자료형, 함수 모두 가능)
ex) using namespace std
// namespace std { cout, cin 등등이 들어있다. }

c) 3항식
: (result == -1)? cout << "Element is not present in array"   : cout << "Element is present at index " << result;
(문제) ? false : true

그냥 쫄지 말고, if else를 대체하는 방법이라고만 생각하자.

 

d) length처리 

sizeof 비트 값으로 배열 전체를 배열 0번 값의 크기 한 개로 나눈다.

(모든 배열 사이즈가 동등하다는 전제하에, 배열 자료형 차원 관리를 그지 같이 하면 아닌 경우도 종종 있음, List나 Map을 씁시다)

2. C

// C code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1

#include <stdio.h>

int search(int arr[], int n, int x)
{
	int i;
	for (i = 0; i < n; i++)
		if (arr[i] == x)
			return i;
	return -1;
}

// Driver code
int main(void)
{
	int arr[] = { 2, 3, 4, 10, 40 };
	int x = 10;
	int n = sizeof(arr) / sizeof(arr[0]);

	// Function call
	int result = search(arr, n, x);
	(result == -1)
		? printf("Element is not present in array")
		: printf("Element is present at index %d", result);
	return 0;
}

a) #include<stdio.h>

: C++에서 namespace std의 cout << 대신, stdio.h안의  printf("")로 대체

헤더 파일 문법과 include 자체가 C에서 고안된 듯싶다. (아마도 비전공자들이 아는 언어 중에서도 가장 가장 오래된 언어이니 그럴 듯 한 추론이군... 코볼과 파스칼 펄 같은 건 그냥 넘어갑시다!) OOP의 Object를 대체하는 모듈화를 헤더 파일로 한다고 생각하면 맞으려나 틀리려나..., 순수 자료형인 Structure가 있는데, 아직 그 개념은 안 나오는구먼

저도, C알못이니 일단은 그리 알고 나중에 오개념이면 수정하겠음

b) 마찬가지로 3항식을 쓰는군 ㅇㅋㄷㅋ

 

3. java

// Java code for linearly searching x in arr[]. If x
// is present then return its location, otherwise
// return -1

class GFG 
{
	public static int search(int arr[], int x)
	{
		int n = arr.length;
		for (int i = 0; i < n; i++) 
		{
			if (arr[i] == x)
				return i;
		}
		return -1;
	}

	// Driver code
	public static void main(String args[])
	{
		int arr[] = { 2, 3, 4, 10, 40 };
		int x = 10;

		// Function call
		int result = search(arr, x);
		if (result == -1)
			System.out.print(
				"Element is not present in array");
		else
			System.out.print("Element is present at index "
							+ result);
	}
}

a) 반갑다...

: 필자가 자바/JS 투툴이고 필자는 매우 이기적이기 때문에 앞으로 다른 언어도 마찬가지로 필자가 확실히 아는 개념은 풀이를 생략하겠습니다. (뭐 사실 필자가 개발 지식이 거의 바닥 수준이기 때문에 필자가 아는 내용은 제군들 모두 아시리라고 판단해도 될 수준이라 사료되는군요 흠흠)

 

4. 파이썬

# Python3 code to linearly search x in arr[].
# If x is present then return its location,
# otherwise return -1


def search(arr, n, x):

	for i in range(0, n):
		if (arr[i] == x):
			return i
	return -1


# Driver Code
arr = [2, 3, 4, 10, 40]
x = 10
n = len(arr)

# Function call
result = search(arr, n, x)
if(result == -1):
	print("Element is not present in array")
else:
	print("Element is present at index", result)

a) 너무 반갑다

: 필자가 제일 모르는 언어 (사실상 지식 0에 가까운 수준) 부끄럽지만 그러하다. 앞으로 미친 듯이 팔 예정 [먼 훗날 kaggle 도장을 깨러 가는 그날까지]

b) 이 넘도 객체지향이네? interpretor라던데... 일단 코드레 벨로 보면 이해하겠지

c) 다행히 개행을 세미콜론으로는 하는군

d) #주석 화긴

e) 코드 블록 bracket {}을 쓰지 않는군, 들여 쓰기 표준은 4개(or 2, tab이지만 4개로 엄격할 필욘 없다곤 하지만 난 지키자, 그리고 같은 블록은 같은 인덴트로 맞춰야 한다고 합니다!

이런 애매한 개념들 묵시적 타입 캐스팅 등등 필자가 극혐 하는 부분들), 가독성과 버그 해결을 위해서라도 명시적 코딩을 생활화합시다. 

f) def function(), 함수 선언이며, 블록 단위가 들어갈 때마다 부모 블록에서 ":"가 생성이 되는구먼 반복, 조건문도 역시 마찬기지 신기방기

g) 그 밖에 아주 기본적인 함수는 시스템에 내장돼 있으며 타 언어를 안다면 더 부연을 안 해도 이해하리라 믿고 패스

 

5. C#

// C# code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
using System;

class GFG {
	public static int search(int[] arr, int x)
	{
		int n = arr.Length;
		for (int i = 0; i < n; i++) 
		{
			if (arr[i] == x)
				return i;
		}
		return -1;
	}

	// Driver code
	public static void Main()
	{
		int[] arr = { 2, 3, 4, 10, 40 };
		int x = 10;

		// Function call
		int result = search(arr, x);
		if (result == -1)
			Console.WriteLine(
				"Element is not present in array");
		else
			Console.WriteLine("Element is present at index "
							+ result);
	}
}

// This code is contributed by DrRoot_

 

a) 필자가 첫 공식적인 개발 인턴 할 때 배운 언어!

b) 하지만 놀랍게도 C# 알못이다.

c) 뭔가 length 필드를 받는 부분 등을 보면 묘하게 Java 스럽다 문법이.

d) using System (오호 라이브러리를 이런 식으로 호출하는구먼)

e) C, C++, Java를 섞은듯한 문법이므로 풀이는 패스!

 

6. PHP (죽은 언어로 많이들 오해하지만 의외로 핫한 언어)

<?php
// PHP code for linearly search x in arr[]. 
// If x is present then return its location, 
// otherwise return -1 

function search($arr, $x)
{
	$n = sizeof($arr);
	for($i = 0; $i < $n; $i++)
	{
		if($arr[$i] == $x)
			return $i;
	}
	return -1;
}

// Driver Code
$arr = array(2, 3, 4, 10, 40); 
$x = 10;

// Function call
$result = search($arr, $x);
if($result == -1)
	echo "Element is not present in array";
else
	echo "Element is present at index " ,
								$result;

// This code is contributed
// by jit_t
?>

 

a) 동적, 정적 프로그래밍이 모두 가능한 원조 웹 언어 PHP 반갑다.

 

b) 형은 널 잘 모르지만, 앞으로 공부할까 한다. 하다 보면 맨날 싸우는

jQuery이 넘이랑도 친해지지 않을까 하는 바람 $의 압박

 

c) $arr은 js의 let 또는 var쯤 되겠구먼, 다만 선언과 재정의(override) 같은 것들이

무지 자유롭구먼 리턴할 때도 타입처럼 쓰는 $는 만능이구만

 

d) 코드 블록은 {}이니 비교적 수월하다. sizeof()는 비트단위가 아닌

실제 값 단위라 C, C++과 헷갈리지 말자

 

e) 문장 출력은 echo로 합니다.

 

f) 대체로 평이합니다.

 

비고)

C, C++, C# 우리 형제들은 아직은 동적 메모리 레벨인 포인터는 다루지 않는군, 다행히 아직은 easy 하다.

GeeksforGeeks 모든 문제를 다 풀이하고 난 다음에는 Effective 모든 책들을 다 도장깨기 할 예정

 

솔직히 풀이랍시고 쓰고 있지만 대충대충 콘셉트 충이며, 필자와 마찬가지로 java원툴이거나 개발을 애매하게 알아서 이제 겨우 걸음마하는 사람들을 수준으로 쓰고 있기 때문에,  완전 입문자들은 필자가 쓴 말 만으로는 이해가 힘드실 수도 있습니다. 귀차니즘 때문인지 필자가 필력이 부족해서 일지는 모르겠으나 잘 모르겠는 제군들은 중간중간에 용어 검색하면서 보충 학습하시길!

 

그럼 이만!