✏️ 자료 구조와 알고리즘

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

⭐️ 자료 구조란?

자료 구조란 데이터 값의 모임이다. 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다.
예를 들어 한정된 크기의 책장이 있고, 넣어야 될 책들이 있다고 하자.

빈 책장

책장에 가장 많은 책을 넣는 방법은 아무런 규칙 없이 책을 모두 꽂아 넣는 것이다. 그렇다면 당장은 이 책장의 공간을 효율적으로 사용하는 것처럼 보일 수 있다.
그러나 이후 책을 찾을 때 문제가 발생한다.
규칙 없이 책을 꽂아 넣었기 때문에 책을 찾을 때도 규칙 없이 책장의 모든 범위를 찾아야한다.

이번에는 '책을 제목의 오름차순'으로 꽂아 넣는다는 규칙을 세워보자.

책을 제목의 오름차순으로 꽂아 넣었기 때문에 책을 찾을 때도 규칙에 맞게 찾으면 되기에 책을 찾기가 훨씬 수월할 것이다.

예시의 책장과 책은 컴퓨터 세계에서?

• 책장 = 메모리
• 책 = 데이터

디테일이 다를 수 있지만 전체적인 개념을 이해하는 데에는 문제가 없다. 연산에 사용되는 컴퓨터의 메모리 자원은 한정적이다. 그에 반해 처리해야 할 데이터는 무수히 많을 수 있다.
따라서 우리는 메모리 공간을 효율적으로 사용해야 하는데 이때 필요한 것이 자료 구조이다.

모든 목적에 맞는 자료 구조란 없다.
각 자료 구조가 갖는 장점과 한계를 알고 상황에 맞는 자료 구조를 사용하는 것이 중요하다.
단, 자료 구조에서는 메모리 공간의 효율뿐만 아니라 실행 시간의 효율성도 따진다.

시간이란 소중하다

자료 구조 분류

• 단순 구조: 정수, 실수, 문자, 문자열 등과 같은 데이터형에 해당하는 구조
• 선형 구조: 논리적 순서에서 현재와 다음 자료 사이의 관계가 1:1인 구조
• 비선형 구조: 1:다, 다:다 관계인 구조
• 파일 구조

표현할 자료의 특성과 주된 사용 방법, 수행하는 연산의 특성, 구현에 필요한 저장 공간 용량과 실행 소요 시간 등을 고려하여 가장 효율적인 자료 구조를 선택해야 한다.

⭐️ 알고리즘이란?

Algorithm(알고리즘)은 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현할 것이다. 즉, 문제 해결에 필요한 계산 절차 또는 처리 과정의 순서다.

알고리즘은 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다. 문제 해결을 위해 여러 개의 후보 알고리즘 중 정확성, 효율성 등을 평가한 후 최적의 알고리즘을 선택한다.

알고리즘의 조건

• 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
• 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안 됨)
• 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
• 유한성(종결성) : 유한 횟수의 명령어를 수행 후(유한 시간 내)에 종료한다.
• 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능) 한 것이어야 한다.

---

보통 자료 구조가 선택되면 그에 적용할 알고리즘은 거의 명확해진다. 즉, 자료 구조가 효율적인 알고리즘을 사용할 수 있게 하면서 자료 구조와 알고리즘은 매우 밀접한 관계를 가진다.

위의 책장의 예를 다시 생각해보자.
책장에서 '두근두근 자료구조'라는 책을 찾는다고 하자. 이때 책장에 책이 진열되어 있는 구조에 따라 효율적으로 책을 찾는 방법(알고리즘)이 달라지게 된다.
제목 순으로 진열되어 있다면 왼쪽부터 순서대로 찾는 방법(알고리즘)을 선택하면 되는 것이다.

즉, 위와 같이 보통은 자료 구조의 선택 -> 효율적인 알고리즘의 선택이 된다.

---

📌 좋은 알고리즘이란?

프로그램의 품질은 알고리즘의 좋고, 나쁨에 따라 달렸다.

좋은 알고리즘과 안 좋은 알고리즘을 나누는 기준은 뭘까?

• 이해하기 쉽다
  • 알고리즘은 가능한 알기 쉬워야 한다.
    복잡하고 난해한 알고리즘은 본인조차 이해하기가 어렵고, 협업 시 다른 사람이 곧바로 이해할 수 없게되어 문제가 생길 수 있다. 복잡한 알고리즘은 작업 능률의 저하로 이어진다.
• 속도가 빠르다
  • 결과의 값이 같다면 짧은 시간안에 올바른 결과를 얻을 수 있는 알고리즘이 더 좋은 알고리즘이다.
• 효율적이다
  • 프로그램을 실행할 때 사용하는 메모리 영역이 적어야 한다.
    대량의 메모리가 필요한 것은 프로그램의 효율이 낮다는 것으로, 비용 면에서 메모리 영역이 적은것이 더 좋다.
• 재이용하기 쉽다
  • 과거에 작성한 것을 그대로 사용하거나 부분적으로 이용할 수 있다면 새로운 프로그램을 만드는 데 필요한 시간을 단축시킬 수 있다.

📌 일상 속에서의 알고리즘

일상 속에 존재하는 알고리즘을 찾아보자.

• 기초적인 수학 연산 (피타고라스의 정리, 근의 공식 등)
• 학교에서 집까지 가는 길 찾기
  • 학교가 끝나면 빨리 집에 가고 싶다. 최단 거리와 최단 시간 내에(효율적으로) 학교에서 집까지 가는 길은 알고리즘이다.
• 라면 끓이는 방법
  • 라면을 끓이기 위해 필요한 준비와 조리를 순서대로 진행하는 것은 알고리즘이다.
    라면을 끓이는 순서가 달라진다면..? 생각하기도 싫다.
• 편의점에서 물건 구매하기
  • 편의점에서 물건을 구매하는 절차도 알고리즘이다. 계산을 먼저하고 물건을 고르지는 않는다.

프로그래밍에서 알고리즘은 input 값을 통해 output 값을 얻기 위한 계산 과정을 말하는 것이다. 이러한 문제를 해결할 때 정확하고 효율적으로 결과값을 얻기 위해서는 알고리즘이 필요하다.

---

출처
https://bnzn2426.tistory.com/115
https://6u2ni.tistory.com/41
https://velog.io/@hahan/Algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%B4%EB%9E%80