💡코드 없는 알고리즘과 데이터 구조을 바탕으로 작성된 글입니다.

데이터 구조와 알고리즘

💡코드는 문제를 해결하기 위해 프로그래머의 생각을 표현한 것에 불과하다. 이론을 포함한 배경지식을 더 많이 알수록 문제 해결을 위한 더 많은 시도를 할 수 있다.

💡데이터 : 컴퓨터에 저장되어 있거나 컴퓨터가 가공 및 처리하는 모든 것.
💡정보 : 가공이나 처리가 끝난 데이터

데이터 구조

💡데이터를 구성하고 저장하는 방법.(데이터를 담는 컨테이너)

데이터를 식별하는 방법을 제공하고 데이터의 관계를 보여주는 개념이다.

데이터 구조의 특징

• 위 그림같이 데이터를 같은 종류로 구분하여 구성하고, 저장하는 메커니즘을 제공한다.
• 각 요소에 접근할 수 있다.
• 어떤 데이터든 간에 상관없이 식별자를 지정할 수 있다.

알고리즘

💡문제를 해결하기 위해 사용하는 일련의(논리적인) 단계.
정해진 순서대로 문제를 해결하는 방법이며, 간단하게 '절차'라고 할 수 있다.

알고리즘의 특징

• 단순하고 명확하며 모호하지 않아야 한다.
• 단순하고 직관적인 알고리즘은 더 강력하고 유용

🤔 직관적이고 명확해야하는 이유
컴퓨터는 사람과 달리 스스로 생각할 수 없다. 찬장에서 접시를 꺼내라라는 명령을 내렸을 때 만약 찬장의 문이 닫혀 있다면 문이 열릴 때까지 컴퓨터는 작동하지 않는다.

데이터 구조와 알고리즘의 관계

💡서로 다른 개념이면서 상호 보완적인 관계를 가진다.

• 데이터 구조는 알고리즘이 다루는 데이터를 구성하며, 알고리즘이 데이터를 처리하고 사용자가 원하는 완전한 정보를 산출하는 과정에서 필요한 부분을 제공한다.
• 데이터 구조는 알고리즘이 결과를 산출하는 과정에서 처리하는 데이터를 저장하고 구성한다.

기존 자료형

💡자료형 : 처리할 데이터의 속성의 종류와 데이터로 수행하려는 작업의 종류를 컴퓨터에게 알려주기 위해 만들어진 것.

☝️🤓 올바른 데이터를 입력해도 무의미한 결과를 출력하는 상황
1. 알고리즘이 잘못되어 컴퓨터가 문제 해결 과정에서 오류를 내는 것.
2. 처리할 데이터의 자료형을 컴퓨터에 알리지 못해 수행할 동작을 결정하지 못하고 무의미한 결과를 출력하는 것.

• 기본 자료형은 프로그래밍 언어에서 가장 기본적인 요소이기 대문에 보통 프로그래밍 언어에 일부로 포함되어 있다.

기존 자료형의 종류

1. boolean : 논리 자료형, 0과 1, 참과 거짓, 켜기와 끄기 등 두 가지 상태로 표현하는 자료형.
   • boolean형은 전통적 컴퓨팅 분야의 핵심인 자료형

     🤔 전통적 컴퓨팅?
     이진 데이터를 기반으로 한 컴퓨팅을 말한다.
     켜고 끌 수 있는 수많은 트랜지스터(스위치)로 구성된 프로세서가 장착되어 있으며, 트랜지스터들을 켜고 끔으로서 복잡한 연산, 데이터 저장 등을 할 수 있다.

2. 문자(charator)
3. 정수(integer)
   • 수학에서의 정수는 무한하지만, 컴퓨터 과학에서는 CPU 아키텍쳐와 메모리 용량의 한계, 프로그래밍 언어에 정해져 있는 정수 범위의 제한때문에 무한하지 않다.
4. 부동 소수점 수(floating-point number)
   • 단정도 부동 소수점 수(float) : 32비트로 1워드를 표현
   • 배정도 부동 소수점 수(double) : 64비트로 1워드를 표현
   • decimal : 128비트를 1워드로 표현

     🤔 1워드?
     CPU가 한 번의 버스 사티크를 통하여 메모리나 입출력 장치에 접근할 때 데이터의 크기

함수

💡특정 동작을 수행하는 코드 덩어리. 수학적 개념.

수학의 함수

정의역 : 입력값(독립변수)의 집합
치역: 결괏값(종속변수)의 집합

• 수학의 함수는 독립변수를 종속 변수에 대응시키는 표현식
• 각 입력값에 대응되는 결괏값이 존재한다.

프로그래밍의 함수

• 입력값(매개변수)을 처리한 값을 반환하기 때문에 수학의 함수와 같은 개념을 가진다.
• 다만, 프로그래밍의 함수는 결과값을 반환하지 않는 함수(void 함수)가 있다는 점에서 수학의 함수와는 다르다.

💡 매개변수(parameter)와 인수(argument)

• 매개변수 : 함수를 정의할 때 사용하는 변수(ex. sum(int a, int b))
• 인수 : 함수를 호출하며 전달하는 매개변수의 실제 값(ex. sum(1, 2))

메소드, 프로시저, 서브루틴

💡메소드 : 객체지향 프로그래밍 언어에서 사용하는 클래스 내부에 있는 함수, 클래스의 객체 이름을 사용해 호출하는 함수를 뜻한다.

💡프로시저, 서브루틴 : 일부 프로그래밍 언어에서 함수를 일컫는 말. 프로시저는 값을 반환하지 않는 함수를 뜻하기도 한다.

• 🚨 함수, 메소드, 프로시저, 서브루틴은 모두 의미와 사용하는 목적이 같다.
• 🚨 함수는 모두 커다란 프로그램 내에서 호출될 수 있는 작은 프로그램 또는 하위 프로그램이다.

재귀와 반복

💡재귀 : 자기참조.
재귀 함수 : 특정 조건을 충족할 때까지 자기 자신을 호출하는 함수
💡반복 : 특정 조건을 충족할 때까지 함수의 실행이 되풀이 되는 것

🚨
재귀와 반복은 특정 조건을 충족할 때까지 끊임없이 실행된다.
재귀 함수는 호출 횟수가 늘어날수록 컴퓨터의 가용 메모리 공간은 줄어들고, 호출 횟수의 한계인 최대 재귀 깊이를 초과해 스택 오버플로 에러가 발생한다.

알고리즘의 유형

분할 정복 알고리즘

: divide and conquer algorithm

💡 큰 문제를 여러 개의 작은 문제로 나눠 해결하고 결과를 결합해 하나의 해결 방법을 얻는 알고리즘.

탐욕 알고리즘

: greedy algorithm

실행되는 순간마다 최상의 결정(가장 적합한 동작)을 내리는 알고리즘으로, 어떤 선택이 최선의 선택인지 순간적으로 판단해야 하며, 결단력이 필요하다.

💡 특정 순간에 최적인 해결방법을 찾는 알고리즘

동적 프로그래밍

: dynamic programming(동적 계획법)

💡 과거에 내린 결정이 앞으로의 결정에 영향을 주는 알고리즘.
문제를 해결하는 다양한 해결 방법을 찾아 저장한 후 나중에 재사용한다.

🤓☝️
탐욕 알고리즘은 근사치를, 동적 프로그래밍 알고리즘은 최적화를 한다.

알고리즘 분석

알고리즘을 설계하는 것과 별개로 성능을 분석해야 할 필요가 있다. 문제를 해결하기 위해 사용하는 단계가 적을수록 더 효율적인 알고리즘이며, 이 효율성을 분석할 때 시간 복잡도와 공간 복잡도를 이용한다.

공간 복잡도

알고리즘이 문제를 해결할 때 점유하는 컴퓨터의 메모리 공간.
잘 사용하지 않는다.

시간 복잡도

주어진 입력에 다라 알고리즘이 문제를 해결할 때 걸리는 시간을 뜻한다.

빅 오 표기법

💡 알고리즘을 실행하는 데 걸리는 최대 시간을 측정. 실행 시간이 최악인 경우를 나타내는 것이다.
빅 오 표기법