on
일상생활의 알고리즘
일상생활의 알고리즘
반응형
알고리즘 이라는 단어를 들으면 무엇이 떠오르나요? 기술이나 코딩과 관련된 일종의 난해한 개념인가요? 어떤 의미에서는, 당신이 옳을 거예요. 알고리즘은 컴퓨터를 작동하게 만드는 것이다. 알고리즘이 없다면 컴퓨터는 쓸모없을 것이고, 어떤 작업도 완수할 수 없을 것이다. 그것들은 컴퓨터 시스템이 그 어떤 인간이 할 수 있는 것보다 더 빨리, 다양한 복잡한 문제들을 해결할 수 있도록 하는 지시사항들이다. 그리고 그것들은 넷플릭스의 제안부터 금융 시장에 이르기까지 현대 생활의 모든 곳에 있습니다.
그러나 가장 간단한 용어로, 알고리즘은 단지 한정된 시간 안에 어떤 작업을 수행하기 위한 간단한 명령의 집합일 뿐입니다. 알고리즘은 입력을 받아 입력을 수행하고 출력을 제공합니다. 우리는 초당 수십억 번의 연산을 수행할 수 있는 컴퓨터의 기능을 활용하여 번개 같은 속도로 알고리즘을 실행하지만, 알고리즘은 컴퓨터 코드와 관련이 없습니다. 사실, 알고리즘의 개념은 수 천 년 동안 존재해왔다; 최초의 알고리즘 중 일부는 기원전 1600년경 고대 바빌로니아인들이 제곱근을 찾고 복합적 이익을 계산하는 것과 같은 목적으로 사용했다.
사실, 알든 모르든 매일 알고리즘을 직접 사용합니다. 알고리즘에 대한 초기 정의를 생각해 보면 절차 또는 레시피 라고도 할 수 있습니다. 심지어 레시피에서 무언가를 요리하는 아주 평범한 작업도 알고리즘을 따르는 것이다. 재료(입력물)를 가져다가 지시에 따라 맛있는 식사(출력물)를 만듭니다! 요리 레시피는 구글이나 페이스북에 힘을 실어주는 복잡한 알고리즘만큼 복잡하지는 않지만 그래도 알고리즘이다.
이 글은 일상적인 문제에 대한 다양한 간단한 알고리즘을 소개함으로써 알고리즘적 사고를 익히는데 목적을 두고 있다. 도입될 알고리즘은 간단합니다. 어떤 알고리즘은 너무 직관적이어서 이미 사용하고 있을 수도 있습니다. 하지만 컴퓨터 시스템에서는 인터넷 액세스와 같이 두 번 다시 생각하지 않아도 되는 작업을 수행할 수 있도록 하는 것이 매우 중요합니다. 또한 동일한 작업에 접근하는 데 사용되는 서로 다른 알고리즘을 비교하여 서로에 대해 얼마나 효율적인지 확인할 수 있습니다. 결국 속도는 알고리즘을 구현할 때 고려해야 할 매우 중요한 요소입니다. 1분밖에 걸리지 않는 대안이 있다면 완료하는 데 1시간이 걸리는 알고리즘을 사용하는 것은 바람직하지 않을 것입니다.
시간 복잡성
시간 복잡성은 알고리즘을 실행하는 데 걸리는 시간을 나타냅니다. 하지만 우리가 관심 있는 것이 아니기 때문에 우리는 이것을 초 또는 분 단위로 측정하지 않습니다. 알고리즘의 실행 시간은 입력 크기에 따라 달라집니다. 예를 들어, 100만 개의 다른 항목보다 다른 항목 100개 중에서 항목을 찾는 데 시간이 더 적게 걸립니다. 우리가 관심 있는 것은 서로 다른 알고리즘 실행 시간이 어떻게 다른 속도로 증가하느냐입니다. 초 대신 입력 크기가 커질수록 알고리즘의 런타임이 얼마나 빨리 증가하는지를 보여주는 Big O 표기법을 사용하여 시간 복잡성을 측정합니다.
큰 O 표기법은 괄호 쌍 내에서 큰 O 와 n의 일부 함수(예: O(n²))로 작성됩니다.
검색 중
당신이 간단한 게임을 하고 있다고 상상해 보세요. 1부터 16까지의 정수를 무작위로 선택해서 어떤 숫자인지 알아맞혀야 합니다. 추측을 할 때마다 추측이 너무 높았는지, 낮았는지 등의 말을 듣게 됩니다. 어떻게 접근하시겠습니까?
아주 간단한 방법은 1, 2, 3 등을 추측하는 것입니다. 선형 검색으로 알려진 이 방법은 모든 숫자를 순서대로 추측하기만 하면 되므로 매우 사용하기 쉽습니다. 그러나 숫자가 16이면 추측을 16번 하는 것이 가장 최악의 시나리오이기 때문에 최선의 접근은 아님을 분명히 해야 한다.
다른 방법을 택했을 가능성이 가장 높은 방법은 중간 지점인 8을 추측하는 것입니다. 8이 너무 높으면 8에서 16 사이의 모든 숫자를 제거할 수 있으며, 8이 너무 낮으면 1에서 8 사이의 모든 숫자를 제거할 수 있습니다. 한 가지 추측으로, 여러분은 절반의 숫자를 제거할 수 있을 것입니다. 각 추측은 정확한 숫자를 얻을 때까지 나머지 숫자의 절반을 제거합니다. 이 때문에 최악의 시나리오를 찾으려면 16을 2로 나누면 됩니다. 1이 남으면 1이 됩니다. 따라서 최악의 시나리오에서는 log scape(16) = 4개의 추측만 필요합니다. 이진 검색이라고 불리는 이 방법은 모든 추측이 추가 추측 범위를 절반으로 줄여주기 때문에 이 문제를 해결하는 데 훨씬 더 효율적인 방법입니다.
이제 훨씬 더 많은 항목 목록에 이진 검색을 적용하는 것을 상상해 보십시오. 페이스북 사용자 23억 명 중 한 명의 사용자를 찾으려 한다고 상상해 보십시오(2018년 12월 기준). 선형 검색을 사용하면 23억 명의 사용자를 일일이 확인해야 하는 최악의 시나리오가 발생할 수 있습니다. 그러나 이진 검색을 사용한 경우 처음 확인하는 사용자는 이미 10억 명 이상의 다른 사용자를 검사할 필요가 없습니다. 따라서 최대 ⌈log((2.3 × 10 ⌉) = 32개의 추측만 하면 됩니다. 이는 목록의 항목 수가 증가할수록 이진 검색이 얼마나 더 효율적으로 진행되는지를 보여줍니다.
Big O 표기법으로 표현하면 선형 검색의 시간 복잡도는 선형 시간이라고도 하는 O(n)입니다. 이는 실행 시간이 입력 크기에 따라 선형적으로 증가함을 의미합니다. 즉, 런타임은 입력 크기에 정비례합니다. 운 좋게 첫 번째 시도에서 올바른 항목을 찾을 수 있습니다. 그러나 통계적으로 이러한 상황은 발생하지 않을 가능성이 높으며, 이것이 우리가 보통 최악의 경우 또는 평균적인 경우 런타임에 Big O를 사용하는 이유입니다.
우리는 이미 binary search는 log((n) 항목을 통해 n개 항목 목록을 검색해야 한다는 것을 확인했습니다. 따라서 이진 검색은 로그 시간으로 알려진 O(log n)의 시간 복잡성을 가집니다. O(log n) 알고리즘은 로그의 속성이 입력 수가 증가할수록 실행 시간이 증가하는 속도가 매우 빠르게 느려진다는 것을 의미하므로 매우 효율적입니다.
정렬
바이너리 검색의 한 가지 요구 사항이 있습니다. 즉, 목록을 정렬해야 합니다. 정렬되지 않은 목록에서 이진 검색을 실행할 수 없습니다. 정렬되지 않은 목록은 값이 대상 값보다 높은지 낮은지 여부에 의존하기 때문입니다. 정렬되지 않은 목록이 있는 경우 선형 검색을 사용해야 합니다. 즉, O(n) 시간으로 제한됩니다. 따라서 목록을 자주 검색해야 하는 경우에는 정렬 알고리즘을 사용하여 목록을 정렬하는 것이 훨씬 효율적인 이진 검색을 사용할 수 있습니다.
카드놀이의 한 패를 정리해야 한다고 상상해 보세요. 대부분의 사람들은 다음과 같은 접근 방식을 사용할 것입니다.
두 번째 카드를 가져가세요.
첫 번째 카드보다 작으면 처음 카드로 이동합니다.
세 번째 카드를 가져와서 첫 번째 및 두 번째 카드와 비교하고 필요한 경우 올바른 위치로 옮깁니다.
나머지 카드에 대해 반복합니다.
이 메서드를 삽입 정렬이라고 합니다. 다음 그림은 정렬되지 않은 목록에 적용되는 삽입 정렬의 시각화를 보여줍니다.
대체 정렬 알고리즘을 병합 정렬이라고 합니다. 문제를 여러 하위 문제로 분해해 풀어나가는 것을 분할 정복 알고리즘이라고 한다. 병합 정렬의 개념은 다음과 같습니다.
목록을 절반으로 분할하여 하위 목록 2개를 생성합니다.
하위 목록이 n개 있을 때까지 하위 목록을 절반씩 반복하고 각 항목에는 하나의 항목만 포함됩니다(결국 하나의 항목이 있는 목록은 정렬된 것으로 간주됨!).
각 하위 목록 쌍(이 때 크기가 1에 불과함)에 대해 더 작은 항목을 왼쪽에 배치하고 더 큰 항목을 오른쪽에 배치하여 크기 2의 하위 목록을 생성합니다.
각 하위 목록 쌍(현재 크기 2)에 대해 이 과정을 반복합니다.
하나의 목록만 남아 정렬될 때까지 하위 목록을 계속 병합 하여 새 정렬된 하위 목록을 생성합니다.
다음 그림은 정렬되지 않은 목록에 적용되는 병합 정렬의 시각화를 보여줍니다.
병합 분류는 불필요하게 복잡해 보일 수 있으며, 인간이 사용하기에는 비실용적일 수 있는 것이 사실입니다. 대신 삽입 정렬을 사용하는 것이 훨씬 직관적일 것입니다. 그러나 이것은 컴퓨터와는 다릅니다. 삽입 정렬의 시간 복잡도는 2차 시간이라고도 하는 O(n²)이며 병합 정렬은 O(n log n)입니다. 이는 특히 큰 목록에서 병합 정렬이 삽입 정렬보다 더 효율적이라는 것을 의미합니다. 프로그래밍은 쉽지만 삽입 정렬은 일반적으로 목록의 예상 크기가 작을 때만 실제 응용 프로그램에서 사용됩니다. 병합 정렬은 더 큰 목록을 훨씬 더 쉽게 처리하지만 구현하기가 훨씬 더 고급스럽고 복잡합니다.
미로 풀이
당신이 미로 안에 갇혀 있다고 상상해 보세요. 어떻게 빠져나갈 수 있을까요? 가장 하찮은(그리고 비효율적인) 방법은 출구를 찾을 때까지 무작위로 돌리면서 구절을 따라가는 것입니다. 당신은 결국 탈출하게 되겠지만, 당신은 이 접근법이 매우 느릴 수 있다고 상상할지도 모릅니다. 놀랍게도 이 비지능 알고리즘은 실제로 랜덤 마우스 알고리즘이라는 이름을 가지고 있습니다.
하지만 확실히 더 좋은 방법이 있다. 일반적으로 알려진 알고리즘 중 하나는 왼쪽 또는 오른쪽 규칙이라고도 하는 벽면 팔로워 알고리즘입니다. 한 손으로 벽을 따라가면 결국 미로를 빠져나갈 수 있을 거야 이 접근 방식은 미로의 벽을 재정렬하면 일반적으로 직선으로 끝날 수 있기 때문에 작동합니다. 그래서, 만약 당신이 미로를 끈 조각으로 생각한다면, 한쪽 끝에서 다른 쪽 끝으로 걸어갈 것이 분명합니다.
하지만 벽 팔로워 알고리즘의 결점은 모든 미로에서 작동하지 않는다는 것입니다. 미로 내부에 루프 가 있는 경우(외벽에 연결되지 않은 벽) 이 알고리즘은 실패합니다. 다음 그림은 벽을 따라 간단한 루프를 시작할 경우 원을 그리며 돌아다니는 방법을 보여줍니다.
만약 루프가 훨씬 크고 복잡하다면, 당신이 루프를 따라가고 있다는 것을 깨닫기 어려울 것이고, 당신은 결코 미로를 떠나지 않을 것입니다. 다행히도 이런 약점이 없는 또 다른 알고리즘이 있습니다. 바로 Trémaux의 알고리즘입니다. 이 알고리즘의 간단한 버전은 실제로 그리스 신화인 테세우스와 미노타우르스에 묘사되었다. 이 이야기에서 건축가 다이달로스는 사나운 괴물인 미노타우르스를 가두기 위해 미로를 만들었다. 미노타우루스에게 먹이를 주기로 한 테세우스는 왕의 딸 아리아드네로부터 미로를 탈출할 계획을 세웠습니다.
보다 알고리즘적인 측면에서 Trémaux의 알고리즘은 다음과 같이 설명할 수 있습니다.
경로를 기록할 선을 그립니다(Theseus는 스레드를 사용하여 표시).
교차로에 표시되지 않은 경로가 있는 경우
그렇지 않으면 한 번 표시된 경로를 따릅니다.
두 번 표시된 경로로 이동하지 마십시오.
막다른 골목에서 돌아서라.
이 방법은 역추적을 사용하기 때문에 막다른 골목에 도달할 때마다 다른 경로를 시도할 수 있습니다. 교차로로 돌아가 더 나은 경로를 시도할 수 있는 능력은 미로에 루프가 있든 없든 간에 출구를 찾을 수 있도록 보장합니다. 다음 그림에서 녹색 화살표는 표시된 경로(알고리즘의 2단계)를 충족할 때 새 경로를 선택하도록 결정하는 내용을 나타냅니다.
이 세 가지 미로 해결 알고리즘은 미로 안에 있는 사람에게 유용합니다. 더 빠르고 최단 경로를 보장하는 다른 방법도 있지만, 미로를 조감할 수 있어야 합니다. 여기에는 폭 우선 검색, Dijkstra의 알고리즘 및 A* 검색 알고리즘과 같은 막다른 길 채우기 및 최단 경로 알고리즘이 포함됩니다. A 레벨 추가 수학에서 D1 모듈을 수행한 사용자는 (루프 없이) 모든 미로의 경로가 (그래프 이론에서) 나무와 비슷하게 당겨지고 펼쳐질 수 있다는 것을 직관적으로 인식할 수 있습니다.
메이즈 해결은 일상생활에 거의 적용되지 않는 것처럼 보이지만, 우리가 매일 사용하는 많은 응용프로그램에서 제한된 환경(미로처럼)에서 한 지점에서 다른 지점으로 도달하는 아이디어는 매우 중요한 것으로 나타났습니다. 그래프 이론에서, 미로를 설명하는 다른 방법은 통로를 모서리로, 교차로를 노드로 하는 것입니다. Google 지도와 같이 도로가 어떻게 연결되어 있는지 알고 있는 웹 사이트는 집에서 학교로 가는 가장 좋은 방법을 알려 줄 수 있으며, Facebook 또는 Snapchat과 같은 친구를 알고 있는 앱은 상호 친구 간의 연결을 기준으로 아는 다른 사용자를 더 잘 추측할 수 있습니다. 브랜드와 모델마다 알고리즘이 다르기 때문에 로봇 진공도 좋은 예다. 값싼 로봇은 무작위로 사용하는 마우스 알고리즘과 비슷한 것을 사용할 수 있는데, 단순히 돌아다니기만 하면 되는 반면, 더 비싼 모델은 먼저 장애물이 어디에 있는지 판단하기 위해 방을 설계한 다음 격자 모양의 패턴으로 앞뒤로 이동할 수 있습니다. 일상생활에서 사용되는 미로 해결 알고리즘은 여기에 설명된 것처럼 단순하지 않을 수 있지만, 실제 응용 분야에서는 하찮아 보이는 것이 어떻게 그렇게 중요할 수 있는지 이해하는 것이 중요합니다.
결론
알고리즘은 우리 삶의 모든 곳에 있는 컴퓨터 응용 프로그램에서 중요하다. 그러나 이 개념은 컴퓨터가 발명되기 전부터 수 천 년 동안 존재해왔다. 이 기사를 읽고 알고리즘의 작동 방식에 대해 더 깊이 알게 되셨기를 바랍니다. 알고리즘마다 상황에 따라 장단점이 있다는 점을 이해하는 것이 중요하다. 병합 정렬은 효율성이 높기 때문에 삽입 정렬보다 사용해야 할 것이 분명해 보일 수 있지만 항상 그런 경우가 항상 있는 것은 아닙니다. 더 효율적인 알고리즘은 대개 더 복잡하고 버그와 오류가 발생하기 쉬우므로 효율성이 떨어지는 알고리즘을 사용하는 것이 좋습니다. 속도가 빨라질 수도 있지만 잘못될 수도 있는 알고리즘보다 어느 정도 속도를 희생하는 것이 가치 있는 일이다. 경우에 따라 검색이 필요한 목록이나 데이터베이스가 정렬되지 않으므로 선형 검색이 이진 검색 대신 사용됩니다. 항목이 데이터베이스에서 계속 추가 또는 제거되는 경우 이진 검색을 위해 항목을 다시 정렬하는 데 필요한 시간이 충분하지 않을 수 있습니다.
알고리즘이 아름다운 이유는 일반화된 문제를 해결할 수 있기 때문입니다. 당신이 해야 할 일은 어떤 종류의 문제든 해결할 수 있는 지시사항을 이해하는 것입니다. 어떤 종류의 목록이 주어지든 병합 정렬로 정렬할 수 있습니다. 어떤 종류의 미로가 주어지든 트르모의 알고리즘으로 빠져나갈 수 있는 길을 찾을 수 있어 이러한 수학적 조리법은 컴퓨터 시스템이 놀라운 일을 할 수 있게 해 구글이 관련 검색 결과를 찾을 수 있게 하고, 아마존이 패키지를 빠르게 배달할 수 있게 하며, 유튜브가 동영상을 추천할 수 있게 해준다. 기술이 우리의 일상을 지배하면서 알고리즘은 사회의 일상적인 기능에서 점점 더 중요해질 것이다.
원래 https://roccojiang.com에 게시되었습니다.
from http://devcloset.tistory.com/349 by ccl(A) rewrite - 2021-07-28 03:26:33