Algorithm Intermediate

• 사용하는 알고리즘은 서비스별로 다르다.
• 알고리즘의 기본이 되는 것은 무엇일까?

1-1 알고리즘이란

사전에서 알고리즘은 '산법'으로 어떤 문제를 해결하기 위해 입력된 자료를 토대로 원하는 출력을 유도하는 규칙의 집합을 뜻한다. 즉 알고리즘은 '문제를 푸는 절차'다

1) 알고리즘과 프로그램의 차이

• 알고리즘은 문제 해결을 위한 작업 절차 자체이며, 기본적으로 그 절차를 실행하는 수단은 언급하지 않으나 실제로 문제를 풀려면 어떤 수단으로 알고리즘을 실행해야 한다.
• 이 알고리즘을 실제로 실행할 수 있는 형태로 구현한 것이 프로그램이다.
• 즉 프로그램은 프로그래밍 언어로 쓰여진 알고지름의 작업지지서이며 알고리즘 그 자체가 아니다.
• 필요한 결과를 얻기 위해 사용할 수 있는 알고리즘이 하나만 있는 것은 아니다.

2) 알고리즘이 필요한 이유

• 알고리즘은 어떤 문제를 해결하기 위한 일련의 절차와 방법으로, 어디에서나 같은 기능으로 동작한다.예를 들어 강남역 -> 여의도까지 가는 지하철 노선의 최단 경로를 구하고 싶다면 최단 경로를 구하는 알고리즘인 다이크스트라 알고지름을 사용하면 쉽게 구현할 수 있다.
• 자동차 분야에서는 자율 주행 연구가 활발히 진행되었고, 더 이상 사람이 운전을 하지 않아도 되는 세상이 멀지 않았다. 이러한 자율 주행 차를 만들 때도 알고리즘을 많이 사용하며, 이때 이미지 인식(객체 인식) 알고리즘을 대표적으로 사용한다.카메라 여러대에 촬영한 영상을 분석하기 위해 영상을 패턴화하고 그 데이터를 통해 객체를 인식하는 기술의 이면에는 지금까지 알려진 수많은 알고리즘과 인공지능이 사용되고 있다.

3) 최근에 주목받고 있는 대표적인 알고리즘

• 머신러닝
  • 컴퓨터에 지능을 부여하자는 시도가 인공지능이며, 현재는 3차 인공지능인 머신러닝이란 학습하듯이 컴퓨터에도 데이터를 주고 학습시켜서 새로운 지식을 얻는 방법이다.
  • 머신 러닝 알고리즘은 증권 시장 분석, 음성 인식과 손으로 쓴 문자의 인식, 신용카드 사기 색출, 건강상태 확인 및 질병진단 등에 활용된다.
• 영지식 증명
  • 인터넷에서 이용되는 가상 통화에 비트코인이 있다. 비트코인 시스템에서는 통화 발행 및 거래의 상세 정보는 모두 공개하고 기록하기 대문에 통화 위조, 이중 지불 등을 방지할 수 있는 혁신적인 서비스로 주목받고 있다.
  • 은닉성을 유지할 수 있는 Zcash라는 암호 퇑화는 알고리즘으로 완전한 익명성을 유지할 수 있어, 자신의 정보를 넘기지 않으면서 자신이 그것을 알고 있다는 사실만을 전달할 수 있다. 이런 특성 때문에 익명성을 보장해야 하는 전자투표에 쓰이고 있다.

1-2 알고리즘이 만족해야 하는 조건

1) 범용성

• 작업자와 상관없이 어떤 환경에서도 같은 결과를 낼 수 있어야 한다는 것이다.
• 예를 들어 요리 레시피도 하나의 알고리즘인데, 사람마다 생각하고 있는 고기의 익기정도가 다르기 때문에 작업하는 사람마다 해석의 여지가 있으므로 이는 알고리즘이라고 볼 수 없다
• 즉 작업자가 누구든 (그것이 기계라도) 어떤 환경에서도 같은 결과를 얻을 수 있는 것, 즉 범용성이 있어야 올바른 알고리즘이다

2) 정당성

• 주어진 과제에 대하여 올바른 결과(=출력)를 얻을 수 있는 정당성도 중요한 조건이다.

3) 결정성

• 알고리즘은 같은 입력을 했을 때 반드시 같은 결과가 나와야한다. 같은 입력을 해도 다른 결과가 나온다면 올바른 알고리즘이 아니다.

🔍알고리즘 용어

• 문제: 알고리즘에서 해결하려는 내용이며 과제라고도 한다. IT시스템 설계에서는 요구나 조건으로 표현한다.
• 프로그램: 알고리즘은 컴퓨터에서 실행하기 위해 프로그래밍 언어로 써낸 것이다. 알고리즘은 개념이며, 프로그램은 그것을 구체화한 것이라고 할 수 있다.
• 입력:알고리즘 처리 대상이 되는 데이터이다. 프로그램에서는 키보드,터치패널,마우스,파일,서버 등으로 받는다
• 출력:알고리즘을 실행해서 얻는 결과이다. 사용자는 프로그램의 출력을 디스플레이,프린트,스피커 등으로 확인할 수 있다.
• 스텝: 알고리즘을 구성하는 절차이다. 하나의 절차를 스텝 1이라고한다. 복잡하거나 시간이 걸리는 알고리즘일수록 스텝 수가 많다.
• 최적화: 알고리즘의 스텝 수나 처리 시간을 줄여 효율적으로 처리할 수 있도록 개선하는 것이다.

4) 유한성

• 알고리즘은 유한해야한다. 정지하지 않는 알고리즘은 결과를 출력할 수 없는 , 즉 '문제를 해결할 수 없다는 것'이기 때문이다. 스텝이 무한 루프(무한으로 반복하는 상태)와 같다면 올바른 알고리즘이라 할 수 없다.
• 알고리즘안에서 판단 기준이 잘 정의되어 있지 않으면 무한히 반복하기 때문에 결과를 출력할 수 없다.

5) 정지성

• 무한 루프가 아니여도 알고리즘은 언젠가는 정지해야 한다.
• 알고리즘이 유한성을 만족하더라도 실행하는 데 시간이 너무 걸리면 실질적으로 도움이 되지 않을 수 있다. 예를 들어 내일의 날씨를 확실하게 예상할 수 있는 알고지름을 만들었는데 실행하는 데 일주일이 걸린다면 의미가 없으므로 알고리즘은 현실적인 시간내에 종료해야한다.