알고리즘과 자료구조

알고리즘이란 일련의 단계적 절차라고 할 수 있고 어떤 문제를 해결하기 위한 동작의 순서와 모임이라고 할 수도 있다. 다시 말해 문제를 해결하기 위해서 계산이 들어가는 과정에서 생기는 규칙과 절차를 알고리즘이라고도 한다. 쉽게 말해 계산 과정, 처리 과정의 순서 그 자체를 뜻한다. 이는 컴퓨터 프로그래밍에서 뺄 수 없는 중요한 것이다. 알고리즘은 영어로 된 것을 한국어로 읽었을 때 알고리즘이라고 발음이 되어 통상 사람들이 그렇게 쓰고 있는 것이고 이를 나름 한국어로 그 의미를 번역해 보면 산법, 계산 절차라고도 한다. 이 알고리즘은 원래 처음부터 알고리즘이라고 불리지 않았다. 9세기 페르시아의 한 수학자인 '무함마드 알콰리즈미'의 이름을 라틴어로 바꾸면 알고 리스 무스라고 할 수 있는데 이것이 알고리즘의 유래이다. 알고리즘은 공식적으로 정의하기 위해서는 몇 가지 확인해 봐야 할 조건들이 있다. 입력, 출력, 유한성, 정밀성, 타당성, 그리고 유일성과 일반성과 같은 것들이 있다. 알고리즘은 정의된 입력을 받아들일 수 있어야 한다. 그리고 이것을 받아 계산하여 답으로 출력을 내보낼 수 있어야 한다. 그리고 이 중간 과정에서 이런 계산 처리 과정이 변하지 않는 명확한 작업 단계를 거치는지 확인하는 정밀성, 그리고 단계마다 명확하게 구분하고 다음 단계를 가져야 하는 유일성, 그리고 이러한 과정들이 실제로 구현할 수 있고 실용적인지 타당성을 따져야 하기도 하며 알고리즘은 끝이 있어야 위에서 말한 출력을 끌어낼 수 있기 때문에 특정수의 작업 이후에 정지해야 한다. (유한성) 알고리즘의 구현은 오늘날에는 대부분 컴퓨터 프로그램으로 구현하지만, 전기회로나 생물학적 신경회로를 이용하기도 한다. 알고리즘은 다음과 같이 분류할 수 있다. 구현, 설계, 최적화 문제, 이론적 분야. 이렇게 4가지가 있고 분류마다 예시로 들 수 있는 것을 이야기 해 보자. 먼저 구현 단계에서 우리가 프로그래밍 코딩을 할 때 종종 볼 수 있는 재귀함수라는 용어가 있는데 재귀적 알고리즘이 있다. 이 재귀는 함수를 실행하는데 그 참조하는 것이 자기 자신을 참조하는 방법을 뜻한다. 인터넷 방송이나 스트리머들이 가끔 화면을 바탕화면으로 내렸을 때 화면이 무한정으로 중간으로 빨려 들어가는 듯한 장면을 본 적이 있을 것이다. 이 부분이 바로 재귀함수가 이용된 시스템이라 볼 수 있다. 이처럼 사진이나 그림 등에서 재귀의 형태를 종종 볼 수 있다. 설계 단계에서는 무차별 대입 공격이라는 것을 예시로 들 수 있는 이는 암호학에서 다루는 용어이다. 이 방법은 암호화가 된 파일이나 문제를 풀 때 가능한 모든 경우의 수의값을 대입해서 문제를 푸는 방식을 말한다. 한마디로 1부터 10000 사이에 암호의 답이 있다고 하면 1부터 순서대로 10000씩 입력을 해보면서 답이 맞는지 아닌지 대조해서 문제를 푸는 것을 의미한다. 이론만 들었을 때 컴퓨터는 0과 1과 같은 숫자로 동작하는 기계이고 그 모든 정보를 숫자로 나타낼 수 있기 때문에 이러한 공격이 시간만 무한정 있다고 가정하면 암호는 이 무차별 대입 공격에 속수무책으로 당할 수밖에 없다고 생각할 것이다. 하지만 내가 예시로 든 건 단순히 10000까지 밖에 없지만 컴퓨터에서는 암호의 길이가 길어지면 길어질수록 암호를 풀기 위해 대입해야 하는 경우의 수는 암호화의 키가 n 비트일 때 2의 n 승 가지가 존재한다. 이러한 공격을 막기 위해서 대칭키 암호라는 것을 이용하기도 한다. 현재 암호체계 중 가장 강력한 암호체계 알고리즘으로는 RSA가 있는데 이 체계를 해독하기 위해서는 천문학적인 시간이 소요된다. 하지만 오늘날에는 컴퓨터의 발전 속도가 빠르기 때문에 이 또한 시간 점점 줄어들어 단시간에 해독될 가능성이 있다는 의견이 분분하다. 이러한 무차별 공격으로 피해를 여러 군데가 있는데 그 중 캐세이 퍼시픽 항공이 무차별 대입 공격을 받았는데, 영국 데이터 감독 기관이 이 항공사가 충분한 해킹 예방 수단을 준비하지 않았다는 이유로 벌금 50만 파운드를 부과한 사례도 있다.



자료구조

자료구조는 컴퓨터 과학에서 어떤 정보에 접근하거나 수정할 때보다 효율적으로 관리하게 하는 자료의 조직, 관리, 저장 등을 의미한다. 자료구조는 데이터와 데이터 간의 관계, 종류가 다른 데이터들의 모임이 될 수도 있다. 효과적으로 설계된 자료구조는 실행시간, 메모리 용량과 같은 컴퓨터 자원을 최소한으로 사용하면서 빠르고 효율적으로 접근하고 연산을 수행할 수 있도록 해준다. 프로그램을 설계할 때는 어떤 자료구조를 사용할 건지 가장 우선순위로 정해야 한다. 프로그램을 개발하고 나서는 항상 수정이 빠지지 않는데 최종 결과물에서 수정할 때 데이터의 구조가 자료구조를 이용하지 않아 복잡하게 되어 있다면 수정하는 데 있어서 효율이 떨어진다. 자료 구조는 프로그래밍 언어에서도 많은 영향을 주고 있는데 대부분의 언어는 일정 수준의 모듈 개념을 가지고 있으며, 이는 자료구조가 검증된 구현은 감추고 사용자가 이용하기 쉽게 인터페이스만을 이용하여 다양한 프로그램에서 사용되는 것을 가능하게 해준다. 자료구조의 분류를 몇 가지 살펴보면, 첫 번째로 배열이 있다. 배열은 가장 일반적인 구조로서 데이터를 메모리상에 같은 타입의 자료가 연속적으로 저장이 되는 형태를 말한다. 그리고 리스트 형태로 나타내는 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있다. 리스트는 노드를 단위로 하며, 연결 리스트는 현재 노드가 다음 노드를 가리키는 참조 값으로 구성되어 있는 형태를 말한다. 원형 연결리스트는 말 그대로 모양을 떠올려 보면 된다. 연결 리스트와 거의 동일하지만 시작노드부터 해서 순서대로 다음 노드를 참조하다가 마지막 노드는 참조 값이 없는 것이 아니라 첫 번째 노드를 가리키는 형태를 말한다.