알고리즘 CS

현성·2023년 12월 13일

웹 개발자가 필요로 하는 알고리즘과 컴퓨터 과학 관련 지식은 다양하며, 이는 웹 개발 과정에서 성능 최적화, 데이터 처리, 보안, 그리고 코드 구조 등에 관련이 있습니다. 아래에는 웹 개발자에게 유용한 몇 가지 알고리즘과 컴퓨터 과학 지식을 소개합니다.

정렬 알고리즘

Quick Sort, Merge Sort : 대용량 데이터를 효율적으로 정렬하는데 필요한 알고리즘들입니다. 브라우저에서 발생하는 데이터 정렬이나 검색 연산에 사용될 수 있습니다.

추가 정보 : 모두의 코드, 동빈나

검색 알고리즘

이진 검색(Binary Search) : 정렬된 데이터에서 아이템을 효율적으로 찾기 위한 알고리즘입니다. 정렬된 리스트나 배열에서 빠르게 검색할 수 있습니다.
이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있습니다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 됩니다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있습니다.

출처 : 위키백과

그래프 알고리즘

BFS (Breadth-First Search), DFS (Depth-First Search) : 그래프 구조에서 노드 간의 관계를 찾고 특정 경로를 탐색하는 데 사용됩니다. 웹 애플리케이션에서 네트워크 구조, 소셜 그래프 등을 다룰 때 유용합니다.

BFS (Breadth-First Search)는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다. BFS는 큐 자료구조를 이용하며, 체적인 동작 과정은 다음과 같습니다.

탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다.
더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

DFS (Depth-First Search)는 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.
DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같습니다.

탐색 시작 노드를 스택에 삽입하고 방문 처리합니다.
스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

출처 : minam.log

동적 프로그래밍

Memoization, Tabulation: 중복 계산을 피하고 실행 시간을 줄이기 위해 사용되는 기법으로, 웹 애플리케이션에서 효율적인 알고리즘을 구현하는 데 도움이 됩니다.
Memoization은 컴퓨터 프로그램이 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다. 동적 계획법의 핵심이 되는 기술입니다.

출처 : 위키백과

해시 알고리즘

MD5, SHA-256 등 해시 함수: 데이터의 무결성을 보호하거나 보안을 강화하기 위해 사용됩니다. 암호화와 관련하여 개인 정보 보호에 필요한 알고리즘입니다.
MD5(Message-Digest algorithm 5)는 128비트 암호화 해시 함수입니다. RFC 1321로 지정되어 있으며, 주로 프로그램이나 파일이 원본 그대로인지를 확인하는 무결성 검사 등에 사용됩니다. 1991년에 로널드 라이베스트가 예전에 쓰이던 MD4를 대체하기 위해 고안했습니다.
1996년에 MD5의 설계상 결함이 발견되었습니다. 이것은 매우 치명적인 결함은 아니었지만, 암호학자들은 해시 용도로 SHA-1과 같이 다른 안전한 알고리즘을 사용할 것을 권장하기 시작했습니다. 2004년에는 더욱 심한 암호화 결함이 발견되었고. 2006년에는 노트북 컴퓨터 한 대의 계산 능력으로 1분 내에 해시 충돌을 찾을 정도로 빠른 알고리즘이 발표되기도 하였습니다. 현재는 MD5 알고리즘을 보안 관련 용도로 쓰는 것은 권장하지 않으며, 심각한 보안 문제를 야기할 수도 있습니다. 2008년 12월에는 MD5의 결함을 이용해 SSL 인증서를 변조하는 것이 가능하다는 것이 발표되었습니다.
SHA-256와 해시를 이해하기 위해 아래의 블로그를 참고하면 좋을 것 같습니다.
SHA256 해시 이해하기

출처 : 위키백과

트리 구조

이진 트리, AVL 트리, B-Tree 등: 데이터를 계층적으로 표현하고 관리하는데 사용됩니다. 효율적인 데이터 검색 및 조작을 지원합니다.

최단 경로 알고리즘

Dijkstra, Bellman Ford, Floyd-Warshall: 웹 애플리케이션에서 지도 서비스나 경로 탐색 등에 활용될 수 있습니다.
다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색알고리즘입니다.
흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용됩니다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 다만 이때 음의 간선을 포함할 수 없습니다. 물론 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 매우 적합한 알고리즘 중 하나라고 할 수 있습니다.
벨만 포드(Bellman Ford) 알고리즘은 가중 유향 그래프 상에서 특정 한 노드로부터 다른 노드까지의 최단 경로를 구하는 알고리즘입니다. 이는 음의 간선을 포함할 수 없는 다익스트라 알고리즘의 한계점을 보완하기 위해 나왔습니다.
플로이드 워셜(Floyd-Warshall) 알고리즘은 모든 노드 간의 최단거리를 구할 수 있습니다. 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 다익스트라와 벨만포드 알고리즘과 대조됩니다. 플로이드 워셜 알고리즘은 그래프 상에서 음의 가중치가 있더라도 최단 경로를 구할 수 있습니다. 하지만 음의 가중치와 별개로 음의 사이클이 존재한다면 벨만 포드 알고리즘을 사용해야 합니다.

출처 : 동빈나, https://roytravel.tistory.com/340

컴퓨터 네트워크

HTTP, HTTPS, TCP/IP 등 프로토콜 이해: 웹 개발자는 클라이언트와 서버 간 통신에 대한 이해와 웹 보안에 대한 지식을 가져야 합니다.

알고리즘 복잡도 분석

Big O 표기법: 알고리즘의 성능을 평가하고 개선하기 위해 필요한 개념입니다.
Big O 표기법이란 알고리즘 성능을 수학적으로 표기해주는 표기법입니다.
알고리즘의 실행시간보다는 데이터나 사용자 증가률에 따른 알고리즘 성능을 예측하는게 목표이므로 중요하지 않은 부분인 상수와 같은 숫자는 모두 제거합니다. 또한, 빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용됩니다.
여기서 측정되는 복잡성에는 시간 복잡도와 공간 복잡도가 있습니다.
- 시간 복잡도 : 입력되는 n의 크기에 따라 실행되는 조작의 수
- 공간 복잡도 : 알고리즘이 실행될 때 사용하는 메모리 양 (메모리 발전으로 중요도 낮아지는 중)
아래 사진은 대표적인 Big-O의 복잡도를 나타내는 차트입니다.

출처 : https://ssdragon.tistory.com/100

자료 구조

배열, 리스트, 큐, 스택, 해시 테이블 등: 데이터를 저장하고 조작하는 데 필요한 기본 자료 구조에 대한 이해가 필요합니다.

이러한 알고리즘과 컴퓨터 과학 지식은 웹 개발자가 효율적이고 최적화된 코드를 작성하고, 복잡한 문제에 대한 해결책을 찾는 데 도움이 됩니다.
많은 알고리즘들을 알아보고 소개하는 글을 작성해보았는데, 공부할 것이 정말 많다는 것을 알게 되었고, 저는 컴퓨터공학 전공자는 아니지만, 수학교육을 전공했기 때문에 어느정도 알고리즘 학습에 이점이 있지 않을까 생각합니다.
현재는 기본적인 웹사이트를 만드는데에 필요한 JavaScirpt, React를 학습하고 있지만, 추후에 개발자로서 근무하게 된다면 더 실력있는 개발자가 되기 위해서는 이러한 알고리즘 학습이 필요하다고 생각합니다.