the-ze

CREATE TABLE user(
  id INT NOT NULL AUTO_INCREMENT,
  email VARCHAR(500) NOT NULL,
  name VARCHAR(500) NOT NULL,
  nickname VARCHAR(500) NOT NULL,
  pw VARCHAR(500) NOT NULL,
  newdate DATETIME DEFAULT CURRENT_TIMESTAMP,
  updatedate DATETIME DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  CONSTRAINT user_pk PRIMARY KEY (id)
);

테이블에서 사용할 열의 이름을 id로 하고 열의 데이터 유형을 INT로 지정했다. 여기서 정의한 id는 사용자가 사용할 id가 아닌 식별을 위한 번호일 뿐이다. AUTO_INCREMENT는 자동으로 증가하는 값을 생성함을 나타낸다. 새로운 행이 삽입될 때마다 자동으로 증가한다.

DATATIME은 날짜 및 시간 데이터 유형을 지정한다. DEFAULT CURRENT_TIMESTAMP는 새로운 행이 삽입될 때 현재 날짜 및 시간이 자동으로 저장되는 것이다.

CONSTARAINT user_pk는 제약 조건의 이름을 지정한 것이다. PRIMARY KEY로 보통 각 행을 고유하게 식별하는데 위 코드에서는 id 열을 주 키로 설정했다.

CREATE USER 'myundb'@'localhost' IDENTIFIED BY 'password';
GRANT ALL PRIVILEGES ON myundatabase.* TO 'myundb'@'localhost';
FLUSH PRIVILEGES;

myundb로 user의 name을 정의하고 localhost로 로컬 머신에서만 접근을 허용한다라고 정의 하였다. IDENTIFIED BY 로 사용자의 암호를 설정하고 지정된 사용자에게 모든 권한 (ALL PRIVILEGES)을 부여했다.

ON myundatabase 테이블에 대한 권한과 권한을 받을 호스트(myundb@localhost)를 지정하고 FLUSH PRIVILEGES로 사용자 및 권한 관련 변경 사항을 즉시 적용하도록 하였따. 이 명령은 새로운 사용자나 권한을 추가했을 때, MySQL이 즉시 이를 적용하도록 한다.

MySQL 서버를 킬 때, 환경 변수 설정을 해야한다. 이를 위해서는 MySQL 서버의 경로를 알아야하는데, 경로는 보통

로컬 디스크 (C:) \ Program Files \ MySQL \ MySQL Server x.x \ bin

에 있다. 경로를 찾았으면, 고급 시스템 설정을 열고 환경 변수를 클릭한다.

그러면 사용자 변수와 시스템 변수가 나올텐데, 만약 사용자 변수의 PATH에 해당 경로를 추가하면 현재 사용자만 해당 경로를 사용할 수 있기 때문에, 모든 사용자가 MySQL 서버를 실행할 수 있께 하고 싶으면, 시스템 변수에 PATH를 추가 시켜야한다.

그리고 변경 사항을 적용한 후에는 시스템을 다시 시작하거나 로그아웃하여 변경 사항이 적용되도록 하는 것을 꼭 잊지말자.

동기 I/O(Synchronous I/O)는 입력 또는 출력 작업이 실행될 때 프로그램의 실행이 그 작업이 완료될 때까지 차단(Block)되는 방식을 의미한다. 즉, 동기 I/O 작업을 요청하면 해당 작업이 완전히 끝나야만 다음 코드 라인이 실행된다. 그리고 프로그램의 실행 흐름이 소스 코드의 순서와 일치하기 때문에, 코드를 읽고 이해하기 쉽다.

Blocking I/O에서는 I/O 작업(예: 파일 읽기, 네트워크를 통한 데이터 수신 등)을 요청할 때, 해당 작업이 완료될 때까지 해당 요청을 한 프로세스 또는 스레드가 대기 상태에 들어간다. 즉, 작업이 완료될 때까지 아무것도 하지 못하고 기다려야 한다. 이 방식은 프로그래밍 모델이 단순하고 직관적이지만, I/O 작업의 대기 시간 동안에 CPU가 다른 유용한 작업을 수행하지 못하게 하여 자원을 낭비할 수 있다. (동기 I/O는 I/O 작업 중에 CPU가 유휴 상태가 될 수 있으므로 리소스 활용 측면에서 비효율적일 수 있다.)

동기 I/O 방식을 썼을 때 일어나는 일이 뭐가 있을까?

1. 프로그램이 파일 시스템에서 데이터를 읽거나 쓸 때, 해당 작업이 완료될 때까지 다음 작업으로 넘어가지 않는다.
2. 데이터베이스에 쿼리를 요청하고, 그 결과를 받기 전까지 다른 작업을 진행하지 않는 경우가 생긴다.
3. 웹 요청을 보내고 응답을 받을 때까지 기다리는 작업 등이 동기 I/O 방식의 예이다.

비동기 I/O와 비교할 때, 동기 I/O는 구현의 단순함과 코드의 직관적인 흐름 때문에 작은 규모의 애플리케이션 또는 I/O 작업의 복잡성이 낮은 경우에 적합하다. 반면, 비동기 I/O는 I/O 작업이 백그라운드에서 수행되어 프로그램의 응답성과 성능을 향상시킬 수 있는 환경에서 유리하다.

비동기 I/O(Asynchronous I/O)는 I/O 작업이 시작된 후, 그 작업이 완료될 때까지 프로그램의 실행이 대기하지 않고 바로 다음 작업으로 넘어가는 방식이다. 이는 I/O 작업이 백그라운드에서 처리되며, 작업의 완료와 데이터의 반환을 대기하는 동안 프로그램이 다른 작업을 수행할 수 있게 해준다.

비동기 I/O는 비차단(Non-blocking) 방식을 활용하여 I/O 작업이 프로그램의 실행 흐름을 차단하지 않는다. 프로그램은 I/O 작업의 완료를 기다리지 않고 즉시 다음 코드를 실행할 수 있다.

Non-blocking I/O에서는 I/O 작업을 요청하더라도 해당 작업이 즉시 완료될 수 없을 때 대기하지 않고 바로 제어권이 호출자에게 반환된다. 이는 I/O 작업이 완료되지 않았다는 신호와 함께, 프로세스 또는 스레드가 다른 작업을 계속 진행할 수 있게 해준다. Non-blocking I/O는 I/O 작업의 완료를 폴링(polling)하거나, 이벤트 기반 모델을 사용하여 알아차리게 된다. 이 방식은 리소스를 더 효율적으로 활용할 수 있지만, 작업 완료를 확인하고 관리하기 위한 추가적인 로직이 필요하다.

Non-blocking I/O를 효과적으로 활용하기 위해서는 비동기 프로그래밍 모델, 이벤트 루프, 콜백 함수, 프로미스, async/await 등과 같은 개념과 기술을 이해하고 적용할 필요가 있다. 이러한 방식은 Node.js와 같은 플랫폼에서 널리 사용되며, 고성능 네트워크 서버와 애플리케이션을 구축하는 데 중요한 역할을 한다.

콜백 함수는 다른 함수에 인자로 전달되는 함수로, 어떤 이벤트가 발생했거나 특정 작업이 완료된 후에 실행된다. 이를 통해 비동기 작업을 처리할 수 있다. 그러나 콜백 함수를 사용하여 여러 비동기 작업을 연속으로 처리하려고 할 때, 코드는 점점 중첩되고 가독성이 떨어지는 문제가 발생한다. 이러한 상황을 콜백 지옥(Callback Hell) 또는 콜백 피라미드(Pyramid of Doom)라고 한다.

getData(function(a){
    getMoreData(a, function(b){
        getMoreData(b, function(c){ 
            console.log('콜백 지옥');
        });
    });
});

프로미스는 비동기 작업의 최종 완료 또는 실패를 나타내는 객체다. 콜백 지옥의 문제를 해결하기 위해 ES6에서 도입되었다. 프로미스는 .then() 메서드를 통해 연속된 비동기 작업을 체이닝할 수 있게 해준다. 또한, .catch() 메서드를 통해 에러를 쉽게 처리할 수 있다.

getData()
  .then(result => getMoreData(result))
  .then(result => getMoreData(result))
  .then(finalResult => console.log(finalResult))
  .catch(error => console.error(error));

async/await는 ES2017(ES8)에서 소개된, 비동기 작업을 동기적으로 보이는 코드 스타일로 작성할 수 있게 해주는 문법이다. async 함수 내부에서 await 키워드를 사용하면, 프로미스가 처리될 때까지 함수의 실행을 일시 중단하고, 프로미스의 결과가 반환되면 실행을 재개한다. 이를 통해 비동기 코드를 마치 동기 코드처럼 쉽게 작성하고 이해할 수 있다.

async function asyncCall() {
  try {
    const result = await getData();
    const moreData = await getMoreData(result);
    const finalResult = await getMoreData(moreData);
    console.log(finalResult);
  } catch (error) {
    console.error(error);
  }
}

비동기 프로그래밍 모델의 장접은 애플리케이션의 응답성을 향상시켜주고, I/O 작업 중에도 CPU는 다른 작업을 처리할 수 있으므로, 자원을 보다 효율적으로 활용할 수 있다. 또한, 여러 I/O 작업을 동시에 처리할 수 있어, 애플리케이션의 처리 능력을 향상시킬 수 있다.

하지만 비동기 프로그래밍 모델은 동기 모델에 비해 이해하고 사용하기가 더 복잡할 수 있고 콜백 지옥과 같은 문제를 관리해야 하는 단점이 있다.

DB 인덱스는 데이터베이스에서 데이터 검색 속도를 빠르게 하기 위해 사용되는 데이터 구조다. 특정 열(컬럼)의 값을 기준으로 정렬해 둔 목록이라고 볼 수 있다. 이 인덱스를 사용하면 데이터베이스는 테이블 전체를 처음부터 끝까지 찾아보지 않고도 빠르게 원하는 데이터를 찾을 수 있다.

예를 들어, 책 뒤에 있는 색인(index)을 생각해보면 이해가 쉽다. 책의 색인을 사용하면 원하는 정보를 책 전체를 훑어보지 않고도 빠르게 찾아낼 수 있다. DB 인덱스도 비슷하게 작동한다. 특정 데이터를 찾을 때, 인덱스가 있으면 데이터베이스는 인덱스를 먼저 확인해 어디에서 데이터를 찾아야 할지 빠르게 알 수 있다.

그러나 인덱스는 데이터 검색 속도를 향상시키는 대신, 추가적인 저장 공간을 사용하고, 데이터를 삽입하거나 수정할 때 추가 작업이 필요해 성능에 영향을 줄 수 있기 때문에 신중하게 사용해야 한다.

DB 인덱스는 SQL 기반의 관계형 데이터베이스(RDBMS)와 NoSQL 데이터베이스 모두에서 사용될 수 있다. 각 데이터베이스 유형에 따라 인덱스의 구현, 관리 방법, 최적화 전략 등이 다를 수 있다.

SQL 데이터베이스에서 인덱스는 테이블의 하나 이상의 컬럼에 적용되어 데이터 검색 속도를 향상시킨다. 대표적으로 B-트리(B-Tree) 인덱스가 널리 사용된다. 관계형 데이터베이스에서 인덱스는 SELECT 쿼리의 WHERE 절, JOIN 연산 등에서 데이터 검색 시간을 줄이기 위해 주로 사용된다.

NoSQL 데이터베이스는 키-값 저장소, 문서 지향 데이터베이스, 컬럼 패밀리 데이터베이스, 그래프 데이터베이스 등 다양한 형태가 있다. NoSQL 데이터베이스도 데이터 검색 성능을 향상시키기 위해 인덱스를 사용한다. 예를 들어, 문서 지향 데이터베이스인 MongoDB에서는 문서의 특정 필드에 인덱스를 생성하여 쿼리 성능을 개선할 수 있다.

SQL 문에서 발생한 오류 Error Code: 1064는 SQL 구문에 문법 오류가 있음을 나타낸다. 특히 DB 외적인 프로그래밍을 많이 하다가 스키마(데이터베이스)를 정의할 때 작은따옴표(') 대신에 백틱(`)을 사용해야 하는 것을 주의하지 않아 자주 발생한다.

예를 들어, CREATE SCHEMA 'mydatabase' DEFAULT CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci;를 쳤다고 하자 'mydatabase'는 작은 따옴표다.

그럼 0 4 21:31:56 CREATE SCHEMA 'mydatabase' DEFAULT CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci Error Code: 1064. You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near ''mydatabase' DEFAULT CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci' at line 1 0.000 sec 에러가 뜰 것 이다.

그러면 작은 따옴표를 백틱으로 바꿔주면 된다. 그리고 일부 버전의 mySQL에선 SCHEMA 대신 DATABASE 키워드를 더 선호할 수도 있으니

CREATE DATABASE `mydatabase` DEFAULT CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci;

로 바꾸는게 좋다. 이 구문은 mydatabase라는 이름의 데이터베이스를 생성하며, 기본 문자 세트로 utf8mb4를, 정렬 순서로 utf8mb4_general_ci를 설정한다. utf8mb4는 이모지를 포함한 다양한 유니코드 문자를 지원하기 때문에, 다국어 데이터를 처리하는 애플리케이션에 적합하다.

++

MySQL에서 Error Code: 1007은 데이터베이스가 이미 존재할 때 발생하는 오류다. mydatabase가 이미 존재하기 때문에 같은 이름으로 데이터베이스를 다시 만들 수 없다. 데이터베이스가 이미 존재하는지 확인하거나, 새로운 이름으로 데이터베이스를 생성해야 한다. 이미 존재하는 데이터베이스에 테이블을 추가하려면, 해당 데이터베이스를 선택하고 필요한 SQL 명령을 실행하면 된다.

ex)

DROP DATABASE mydatabase;

CREATE DATABASE `mydatabase` DEFAULT CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci;

React와 Express는 Node.js 환경에서 실행되므로, Node.js가 설치되어 있지 않다면 먼저 설치한다. Node.js 공식 웹사이트(https://nodejs.org)에서 안내에 따라 설치할 수 있다.

터미널을 열고, 원하는 위치에 프로젝트를 위한 새 디렉토리를 생성한다.

mkdir my-web-app
cd my-web-app

Create React App을 사용해 React 프론트엔드 애플리케이션을 생성한다.

npx create-react-app client

이 명령은 client라는 이름의 디렉토리에 React 애플리케이션을 생성한다.

React 애플리케이션 외부에서 Express 애플리케이션을 설정한다.

루트 디렉토리(my-web-app)로 돌아가고 Express 애플리케이션을 위한 server 디렉토리를 생성하고 초기화한다.

mkdir server
cd server
npm init -y

Express를 설치한다.

npm install express

server 디렉토리 내에 index.js 파일을 생성하고, 기본 서버 설정을 추가한다.

const express = require('express');
const app = express();
const PORT = process.env.PORT || 5000;

app.get('/', (req, res) => {
  res.send('Hello World!');
});

app.listen(PORT, () => {
  console.log(`Server running on port ${PORT}`);
});

개발 중에 React 애플리케이션과 Express 서버를 동시에 실행하기 위해, 루트 디렉토리(my-web-app)에 concurrently와 nodemon을 사용하는 설정을 추가한다.

my-web-app로 돌아가 package.json 파일을 생성한다.

npm init -y

concurrently와 nodemon을 설치한다.

npm install concurrently nodemon --save-dev

my-web-app/package.json 파일에서 scripts 섹션을 다음과 같이 수정한다.

"scripts": {
  "client": "cd client && npm start",
  "server": "cd server && nodemon index.js",
  "dev": "concurrently \"npm run server\" \"npm run client\""
}

이 설정을 통해, npm run dev 명령으로 React 애플리케이션과 Express 서버를 동시에 실행할 수 있다.

이러면 DeprecationWarning 이 뜨는데,

DeprecationWarning은 React 스크립트나 사용 중인 라이브러리에서 더 이상 사용하지 않는 기능을 사용했을 때 발생한다. 이 경고들은 주로 개발 환경 설정에 관련되어 있으며, 애플리케이션의 실행에는 직접적인 영향을 주지 않는다. 만약 webpack 관련 버전 문제로 DeprecationWarning이 났고 이를 해결하기 위해서는 webpack 설정을 확인하고 업데이트하는 것이 좋다. React와 관련된 설정은 node_modules 안의 관련 라이브러리 설정에서 찾을 수 있으며, 일반적으로 사용자가 직접 수정할 필요는 없다.

webpack 설정 확인하고 업데이트 하는 법:

프로젝트 폴더에서 터미널을 열고, 현재 설치된 Webpack 버전을 확인한다.

npm list webpack

npm 레지스트리에서 Webpack의 최신 버전을 확인한다.

npm view webpack version

원하는 버전(대개 최신 버전)으로 Webpack을 업데이트한다.

npm install webpack@latest --save-dev

@latest 대신 특정 버전을 지정하고 싶다면, @ 뒤에 해당 버전 번호를 명시한다 (예: webpack@4.44.1). --save-dev는 이 패키지가 개발 의존성임을 나타낸다.

Webpack과 함께 사용되는 로더(loader) 및 플러그인(plugin)도 최신 버전으로 업데이트하는 것이 좋다. 이는 호환성 문제를 방지하기 위함이다.

npm install webpack-cli@latest webpack-dev-server@latest --save-dev

여기서 webpack-cli와 webpack-dev-server는 Webpack을 사용하는 데 흔히 필요한 패키지이며, 프로젝트에 따라 추가적인 로더나 플러그인이 필요할 수 있다.

업데이트 후 프로젝트가 여전히 정상적으로 작동하는지 확인해야한다. 때때로 메이저 버전 업데이트는 기존 설정이나 코드와 호환되지 않을 수 있으므로, 특히 중요한 변경 사항을 적용한 후에는 프로젝트를 꼼꼼히 테스트해야 한다.

업데이트 후 의존성 문제나 버전 충돌이 발생할 수 있다. 이런 경우, 해당 패키지의 문서를 참고하여 새 버전에 맞게 설정을 조정하거나 필요한 변경을 적용한다.

최신 버전으로 업데이트 한 후에도 여전히 동일한 경고 메시지가 나타나면, react - scripts 패키지 내부에서 사용되는 webpack 설정 때문에 발생할 수 있다. react - scripts 는 Create React App을 통해 생성된 프로젝트에서 Webpack과 같은 도구들을 추상화해 제공한다. 때문에 react - scripts 내부의 webpack 설정은 직접적으로 수정할 수 없다.

Create React App 팀이 react-scripts의 새 버전을 출시하여 이러한 경고를 해결할 수 있다. 따라서 react-scripts의 최신 버전을 확인하고 업데이트하는 것이 좋다.

npm install react-scripts@latest --save

ESLint 경고는 개발자가 직접 해결할 수 있다. App.tsx 파일에서 사용하지 않는 logo 변수를 제거하면 된다.

npm audit은 보안 취약점에 대한 경고다. npm audit 또는 npm audit fix를 실행하여 취약한 의존성을 해결할 수 있다. 일부 의존성은 메이저 업데이트를 필요로 할 수 있으며, npm audit fix --force를 사용하여 강제로 수정할 수 있다. 하지만, 이는 기존 코드에 영향을 줄 수 있으므로 주의해서 사용해야 한다.

npm audit를 정기적으로 실행하여 보안 취약점을 확인하고 해결하는 것이 좋다.

Sliding Window(슬라이딩 윈도우) 알고리즘은 배열이나 리스트의 일정 범위의 요소를 '창'으로 생각하고, 이 창을 배열이나 리스트의 끝까지 이동시키면서 주어진 문제의 조건에 맞는 최적의 해를 찾는 방식이다. 이 알고리즘은 특히 연속된 데이터에 대해 최대합, 최소값, 평균 등을 효율적으로 계산할 때 유용하다.

슬라이딩 윈도우를 구현할 때에는 윈도우의 크기를 결정하고, 배열의 시작 부분에 윈도우를 위치시킨 뒤, 윈도우를 한 칸씩 오른쪽으로 이동시키면서, 윈도우에 포함된 요소들을 이용해 문제를 해결한다.

각 이동마다 최적의 해를 찾거나 조건을 만족하는지 검사하고, 필요한 경우 해를 갱신해야 한다.

윈도우를 한 번만 순회하므로, 알고리즘의 시간 복잡도는 대체로 O(n)이다. 데이터 스트림과 같이 동적으로 변하는 연속된 데이터에 대해서도 실시간으로 최적의 해를 찾는 데 적합하다.

def max_sum_subarray_of_size_k(arr, k):
    max_sum = 0
    window_sum = sum(arr[:k])  # 초기 윈도우의 합을 계산
    max_sum = window_sum

    for i in range(len(arr) - k):
        window_sum = window_sum - arr[i] + arr[i + k]  # 윈도우를 한 칸씩 오른쪽으로 이동
        max_sum = max(max_sum, window_sum)  # 최대 합 갱신

    return max_sum

arr = [1, 15, 1, 2, 6, 12, 5, 7]
k = 4
print(max_sum_subarray_of_size_k(arr, k))

#출력
#30

투 포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 두 개의 포인터를 이용하여 문제를 해결하는 방법이다. 주로 정렬된 배열에서 두 요소의 합, 최대값 또는 최소값을 찾거나, 특정 조건을 만족하는 부분 배열을 탐색하는 데 유용하다. 대부분의 경우 선형 시간 안에 해를 찾는다.

배열의 시작점에 두 포인터를 위치시킨다. 보통 한 포인터는 배열의 시작점에, 다른 하나는 끝점에 위치시킨다. 주어진 조건에 따라 포인터들을 적절히 이동시키면서 문제의 해를 찾는다.

• 합이 특정 값보다 작을 때는 시작 포인터를 오른쪽으로 이동시켜 합을 증가시킨다.
• 합이 특정 값보다 클 때는 끝 포인터를 왼쪽으로 이동시켜 합을 감소시킨다.

중첩 반복문을 사용하지 않아 시간 복잡도가 O(n^2)에서 O(n)으로 줄어든다.

def two_sum(arr, target):
    left, right = 0, len(arr) - 1  # 초기화

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return None

arr = [1, 2, 3, 4, 5]
target = 9
print(two_sum(arr, target))

# 출력
# (3,4)

LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 두 시퀀스(예: 문자열, 리스트 등)에서 순서를 변경하지 않고 양쪽 시퀀스에서 모두 찾아낼 수 있는 가장 긴 부분 수열을 찾는 문제다. 이 문제는 다이나믹 프로그래밍(dynamic programming) 기법을 이용하여 효율적으로 해결할 수 있다.

LCS 문제를 해결하는 기본 아이디어는 두 시퀀스의 각 위치에 대해, 해당 위치까지의 최장 공통 부분 수열의 길이를 저장하는 2차원 배열(또는 테이블)을 만드는 것이다. 이 배열을 dp라 할 때, dp[i][j]는 첫 번째 시퀀스의 i번째 원소와 두 번째 시퀀스의 j번째 원소까지 고려했을 때의 최장 공통 부분 수열의 길이를 나타낸다.

dp 배열의 모든 값을 0으로 초기화한다. 여기서 dp[0][j]와 dp[i][0]은 첫 번째 시퀀스 또는 두 번째 시퀀스의 원소가 하나도 없을 때를 의미하므로, 공통 부분 수열의 길이는 0이다.

• 만약 현재 위치의 원소가 같다면, dp[i][j] = dp[i-1][j-1] + 1로 설정한다. 이는 현재 원소가 공통 부분 수열에 포함되므로, 이전 위치까지의 최장 길이에 1을 추가한 것이다.
• 만약 현재 위치의 원소가 다르다면, dp[i][j] = max(dp[i-1][j], dp[i][j-1])로 설정한다. 이는 현재 원소를 제외하고, 이전 위치에서의 최장 공통 부분 수열의 길이를 가져오는 것이다.

dp 배열의 마지막 원소인 dp[n][m]이 두 시퀀스의 최장 공통 부분 수열의 길이를 나타낸다. 여기서 n과 m은 각각 두 시퀀스의 길이다.

LCS 문제는 컴퓨터 과학뿐만 아니라, 생물 정보학에서 유전자 시퀀스 비교나 텍스트 편집 거리 계산 등 다양한 분야에서 응용된다.

def lcs(X, Y):
    # 두 문자열의 길이 계산
    m, n = len(X), len(Y)

    # dp 테이블 초기화 (m+1)x(n+1) 크기
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # dp 테이블 채우기
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:  # 현재 문자가 서로 같은 경우
                dp[i][j] = dp[i-1][j-1] + 1
            else:  # 현재 문자가 서로 다른 경우
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]  # 테이블의 마지막 값이 최장 공통 부분 수열의 길이

X = "GXTXAYB"
Y = "AGGTAB"
print(f"LCS length: {lcs(X, Y)}")

#출력
#LCS length: 4
#(GTAB로 4이기 때문)

Knapsack 문제는 조합 최적화(Combinatorial Optimization)의 대표적인 예로, 특정한 제약 조건 하에서 최적의 해를 찾는 문제다. 이 문제는 배낭에 넣을 수 있는 물건들이 주어졌을 때, 물건의 무게 제한을 초과하지 않으면서 가치의 합을 최대화하는 방법을 찾는 것이다. Knapsack 문제에는 여러 변형이 있지만, 가장 널리 알려진 형태는 0-1 Knapsack 문제와 Fractional Knapsack(분할 가능 배낭) 문제다.

0-1 배낭 문제에서는 각 물건을 통째로 넣거나 아예 넣지 않아야 한다.(분할 불가)

• n개의 아이템이 있으며, 각 아이템은 가치(value)와 무게(weight)를 가진다.
• 최대 무게가 W인 배낭이 있다.
• 배낭의 무게 한도를 초과하지 않으면서 가치의 합을 최대화하려면 어떤 아이템을 배낭에 넣어야 하는가?

분할 가능 배낭 문제에서는 물건을 부분적으로 나누어 넣을 수 있다. 이는 그리디 알고리즘을 사용해 해결할 수 있으며, 아이템의 가치 대비 무게(가치/무게 비율)를 기준으로 선택한다.

0-1 배낭 문제는 다이나믹 프로그래밍을 사용해 효율적으로 해결할 수 있다. 핵심 아이디어는 두 가지 선택지가 있을 때 최적의 선택을 결정하는 것이다: 아이템을 배낭에 추가하거나 추가하지 않는다. 다이나믹 프로그래밍 접근 방식에서는 이러한 결정을 기반으로 값을 메모하여, 반복 계산을 줄인다.

1. (n+1)x(W+1) 크기의 테이블을 0으로 초기화한다. 여기서 n은 아이템 수, W는 배낭의 최대 무게다.
2. 각 아이템에 대해, 가능한 모든 무게에 대해 최대 가치를 계산하여 dp 테이블을 채운다.
3. dp 테이블의 마지막 값(dp[n][W])은 주어진 무게 한도에서 얻을 수 있는 최대 가치다.

예를 들어, 배낭의 최대 무게가 50이고, 다음 3개의 아이템이 있을 때의 최적의 해를 찾는다고 가정하자.

• 아이템 1: 무게 10, 가치 60
• 아이템 2: 무게 20, 가치 100
• 아이템 3: 무게 30, 가치 120

0-1 배낭 문제의 해결책은 이 아이템들 중에서 선택하여 최대 가치를 얻는 조합을 찾는 것이다.

Knapsack 문제는 그 해결 방법이 명확하고, 다양한 실생활 문제에 응용될 수 있는 대표적인 최적화 문제 중 하나다.

def knapsack(W, wt, val, n):
    """
    :param W: int 배낭의 최대 무게
    :param wt: list 아이템의 무게 리스트
    :param val: list 아이템의 가치 리스트
    :param n: int 아이템의 총 개수
    :return: int 최대 가치
    """
    # 기본적으로 0으로 초기화된 DP 테이블 생성
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    
    # DP 테이블을 채워나감
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                # i번째 아이템을 포함시킬 경우와 포함시키지 않을 경우 중 최대 가치 선택
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                # i번째 아이템을 포함시킬 수 없는 경우
                K[i][w] = K[i-1][w]

    return K[n][W]  # 최대 가치 반환

# 예시 데이터
val = [60, 100, 120]  # 아이템의 가치
wt = [10, 20, 30]  # 아이템의 무게
W = 50  # 배낭의 최대 무게
n = len(val)  # 아이템 개수

# 최대 가치 계산
print(knapsack(W, wt, val, n))

# 출력
# 220

다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프 내에서 두 노드 사이의 최단 경로를 찾는 알고리즘이다. 주로 네트워크 라우팅 프로토콜, 지도의 경로 탐색 등에 활용된다. 이 알고리즘은 음의 가중치를 갖지 않는 그래프에 적용된다.

다익스트라 알고리즘은 시작 노드 설정 후, 시작 노드로부터 각 노드까지의 거리(가중치)를 저장하는 배열을 무한대로 초기화한다. 시작 노드의 거리는 0으로 설정하고, 방문하지 않은 노드 중 시작 노드로부터 가장 가까운 노드를 선택한다. 그리고 선택한 노드를 경유지로 하여 갈 수 있는 다른 노드들까지의 거리를 계싼하고, 기존에 저장된 거리보다 짧을 경우 갱신한다. 모든 노드를 방문할 때 까지 이 과정을 반복하면 시작 노드로부터 각 노드까지의 최단 거리가 계산된다.

다익스트라 알고리즘은 그리디 알고리즘을 적용하여 매 선택에서 지역적으로 최적인 해를 선택해 나가는 방식으로, 전체적으로 최적의 해를 찾는다.

음의 가중치가 있을 경우, 알고리즘은 정확한 결과를 보장할 수 없다.

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if distances[current_node] < current_distance:
            continue

        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])

    return distances

# 그래프 예시
graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

start_node = 'A'
print(dijkstra(graph, start_node))

#출력 결과
{'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 쌍 최단 경로 문제를 해결하는 알고리즘이다. 이 문제는 주어진 가중치 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 것이 목표이다. 플로이드-워셜 알고리즘은 동적 프로그래밍을 기반으로 한다.

알고리즘의 기본 아이디어는 각 단계마다 '경유점'을 하나씩 추가하며, 이 경유점을 통해 갈 수 있는 모든 정점 쌍의 최단 거리를 업데이트하는 것이다. 여기서 '경유점'이란 특정 정점을 거쳐 가는 경로를 말한다.

최단 거리 정보를 저장할 2차원 배열 D를 준비한다. D[i][j]는 정점 i에서 j로 가는 직접 경로의 가중치를 나타낸다. 직접 경로가 존재하지 않는 경우, 해당 값은 무한대로 설정한다. 자기 자신으로 가는 경로의 가중치는 0으로 설정한다.

각 정점을 경유점으로 고려: 모든 정점 쌍 (i, j)에 대해서, 가능한 모든 경유점 k에 대하여 D[i][k] + D[k][j]의 값을 계산하고, 이 값이 D[i][j]보다 작은 경우 D[i][j]를 D[i][k] + D[k][j]로 업데이트한다. 그리고 모든 정점을 경유점으로 고려한 후, 배열 D에는 모든 정점 쌍 사이의 최단 경로의 가중치가 저장된다.

시간 복잡도는 O(N^3)이며, 여기서 N은 그래프의 정점 수이다. 음의 가중치가 있는 그래프에서도 사용할 수 있다. 단, 그래프에 음의 사이클이 있으면 안 된다. 동적 프로그래밍 방식을 사용하여 문제를 해결한다.

# 무한대를 의미하는 값으로 초기화한다. 실제 사용에서는 충분히 큰 수를 사용한다.
INF = float('inf')

# 그래프의 가중치를 나타내는 2차원 리스트. graph[i][j]는 정점 i에서 j로 가는 가중치를 의미한다.
# 직접 연결이 없는 경우 INF로 설정한다.
graph = [
    [0, 3, INF, 5],
    [2, 0, INF, 4],
    [INF, 1, 0, INF],
    [INF, INF, 2, 0]
]

# 플로이드-워셜 알고리즘 실행
def floyd_warshall(graph):
    n = len(graph)
    
    # 최단 거리를 저장할 2차원 리스트를 그래프의 가중치로 초기화한다.
    dist = [row[:] for row in graph]
    
    # 모든 정점을 경유점으로 하여 최단 거리를 업데이트한다.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

# 최단 거리 계산
shortest_distances = floyd_warshall(graph)

for row in shortest_distances:
    print(row)

#출력 결과
#[0, 3, 7, 5]
#[2, 0, 6, 4]
#[3, 1, 0, 5]
#[5, 3, 2, 0]

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하는 방법이다. 각 하위 문제는 한 번만 계산되며, 그 결과는 테이블에 저장되어 필요할 때마다 재사용된다. 이 접근법은 중복 계산을 피하고, 효율성을 크게 향상시킨다.

DP 추천 알고리즘 : https://www.acmicpc.net/problem/10870

DP는 큰 문제를 해결할 수 있는 작은 문제로 나누고, 각 하위 문제를 해결하고, 결과를 저장한 뒤, 저장된 하위 문제의 해결책을 조합하여 원래 문제의 해결책을 구하는 방식이다.

Top-Down(Memoization)방식은 큰 문제를 작은 문제로 나누어 재귀적으로 해결한다. 이미 계산된 결과는 저장(메모)하여 중복 계산을 방지한다.

Bottom-Up(Tabulation)방식은 가장 작은 하위 문제부터 시작하여 순차적으로 큰 문제를 해결해 나가는 방식이다. 각 단계의 결과를 테이블에 저장하며, 최종적으로 원하는 문제의 해를 얻을 수 있다.

피보나치 수열에서 F(n) = F(n-1) + F(n-2)라는 관계가 있다. 이를 동적 계획법으로 해결할 수 있다.

# Top-Down
def fib_memo(n, memo):
    if n <= 1:
        return n
    if memo[n] == 0:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

n = 10
memo = [0]*(n+1)
print(fib_memo(n, memo))

#Bottom-Up
def fib_tab(n):
    if n <= 1:
        return n
    fib_table = [0]*(n+1)
    fib_table[1] = 1
    for i in range(2, n+1):
        fib_table[i] = fib_table[i-1] + fib_table[i-2]
    return fib_table[n]

n = 10
print(fib_tab(n))

탐욕 알고리즘(Greedy Algorithm)은 매 순간 최적이라고 생각되는 선택을 하여 최종적인 해답에 도달하는 방법이다. 이 알고리즘은 전체를 고려하는 것이 아니라, 각 단계에서 최선의 결정을 내려서 전역 최적화(global optimum)를 추구한다. 탐욕 알고리즘은 구현이 간단하고, 계산 효율이 높다는 장점이 있지만, 모든 문제에 대해 항상 최적의 해를 보장하지는 않는다.

그리디 알고리즘은 각 단계에서 지역적으로 최적이라고 판단되는 선택을 함으로써 전체 문제의 최적해를 찾아가고, 한 번 선택된 결정은 취소할 수 없다. 최적의 선택을 통해 탐색 공간을 신속하게 축소한다.

그리디 알고리즘을 적용하기 위해서는 두 가지 규칙이 있는데 첫 번째는 앞의 선택이 이후의 선택에 영향을 주지 않으며, 부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있는 것이고, 두 번째 규칙은 문제의 최적 해결책이 그 부분 문제의 최적 해결책으로부터 구성될 수 있다는 것이다.

#동전의 종류가 500원, 100원, 50원, 10원이 있을 때, 
#거스름돈을 가장 적은 수의 동전으로 나누어 주는 방법을 찾는 것이 목표

def min_coins(change, coins):
    count = 0
    for coin in sorted(coins, reverse=True):
        count += change // coin
        change %= coin
    return count

coins = [500, 100, 50, 10]
change = 1260
print(min_coins(change, coins))

각 단계에서 가장 큰 동전부터 최대한 많이 사용하는 탐욕적 선택을 한다. 이러한 선택이 전체 문제에 대한 최적의 해답(최적 해)을 제공한다.