코딩혜영

2024.10.08. 03:23

그때 그 당시에

생생한 감정 그대로를

기록해둔 글은

생명력이 있어서

​

남들보다

더 많은 시간을 가진

더 많은 감정을 느끼고 살아온

부자처럼 보일 수 있겠다

​

-포트폴리오를 몰아서 만들며 이 감정도 기록

프로젝트 시작 준비. 일단 폴더 구조는 다음과 같이 준비한다.

다음 명령어로 기본 세팅을 진행한다.

mkdir guestbook-app
cd guestbook-app
mkdir backend
cd backend
npm init -y
npm install express pg cors dotenv

1. PostgreSQL을 만들기 위한 설치 방법

만약 PostgreSQL이 설치되지 않았다면, 먼저 PostgreSQL을 설치해야 한다. 설치 방법은 운영체제에 따라 다르지만, 대부분의 경우 아래와 같은 명령어로 설치할 수 있다. 나는 macOS이기 때문에 macOS 부분이 더 상세하게 작성될 것 같다.

Ubuntu/Linux

sudo apt-get update
sudo apt-get install postgresql postgresql-contrib

macOS (Homebrew 사용 시)

brew update
brew install postgresql
brew services start postgresql

brew services start postgresql 명령어의 경우 Homebrew를 통해 설치된 PostgreSQL DB 서버를 macOS에서 백그라운드 서비스로 시작하는 명령어이다. 이 명령어는 시스템 부팅 시 자동으로 시작되도록 설정하며, 사용자가 명시적으로 서버를 중지하거나 시스템을 종료하지 않는 한, 계속 실행된다. 따라서 데이터베이스를 사용할 때마다 수동으로 서버를 시작할 필요가 없어서 굉장히 편리하다.

계속 실행되고 있다는 점에서, 메모리와 CPU 사용 측면에서 비효율적인 것이 아닌가 찾아보았다. 하지만 실제 데이터베이스 요청이 들어오지 않으면 CPU 사용량은 거의 없으며, 매우 큰 데이터베이스가 연결되지 않는 한 메모리 사용량은 굉장히 적다고 한다.

하지만 그럼에도 불편함을 느낀다면, 다음 stop 명령어를 통해서 사용하지 않을 때는 꺼둘 수 있다.

brew services stop postgresql

Windows

Windows의 경우, PostgreSQL 공식 사이트에서 설치 파일을 다운로드하여 설치할 수 있다.

2.PostgreSQL로 데이터베이스 생성

psql -U postgres

터미널에서 PostgreSQL에 접속하기 위해, psql 명령어를 사용한다. '-U postgres'는 PostgreSQL의 기본 관리자 계정이다.

그런데 나는 다음과 같은 에러 사항이 발생했다.

psql: error: connection to server on socket "/tmp/.s.PGSQL.5432" failed: FATAL:  role "postgres" does not exist

postgre라는 이름의 역할이 존재하지 않아 발생하는 문제이다. 이는 PostgreSQL을 업그레이드하거나 새로 설치하면서 데이터베이스 설정이 초기화된 경우 사용자 postgres가 사라질 수 있다고 한다. 또는 새로 설치된 PostgreSQL 인스턴스에서는 postgres 역할이 자동 생성되지 않았을 수 있다고 한다.

1) 디렉토리 권한 수정

/usr/local/var 디렉토리에 쓰기 권한을 부여하였다. 해당 디렉토리를 생성하고, 현재 사용자에게 해당 디렉토리에 대한 소유권을 부여한다.

sudo mkdir -p /usr/local/var/postgres
sudo chown -R $(whoami) /usr/local/var/postgres

2) initdb 명령어 다시 실행

디렉토리 권한 수정 후, 다시 데이터베이스 클러스터를 초기화한다.

initdb /usr/local/var/postgres

3) 서버 시작

클러스터가 성공적으로 초기회 되면, PostgreSQL 서버를 시작한다.

brew services start postgresql

근데 이미 시작중이라고 해서, 터미널에 추천으로 뜬 다음 명령어로 재시작해줬다.

brew services restart postgresql@14

4) postgres 역할 생성

서버가 시작되었으므로, createuser 명령어로 postgres 역할을 생성한다.

createuser -s postgres

5) 접속 시도

psql 명령어를 사용하여, PostgreSQL 서버에 접속한다.

psql -U postgres -d postgres

psql 명령어로,

'-U postgres' : postgres 라는 사용자 이름으로 서버에 연결하고, 

'-d postgres' : postgres 라는 이름의 데이터베이스에 연결한다.

만약 -d 옵션을 사용하지 않으면, psql은 기본적으로 현재 시스템 사용자와 동일한 이름의 데이터베이스에 연결을 시도한다.

6) 데이터베이스 및 테이블 생성

CREATE DATABASE guestbook;
\c guestbook

CREATE TABLE guestbook (
    id SERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    message TEXT NOT NULL,
    password VARCHAR(255) NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

생성 후에는 다음 명령어로 테이블 목록을 확인할 수 있다. \dt

이외에도 유용한 명령어들을 정리해보겠다.

7) 백엔드 폴더에 .env 파일 생성

다음과 같이 데이터베이스 연결 정보를 설정한다.

DATABASE_URL=postgres://username:password@hostname:port/guestbook

이때 username, password, hostname, post에는 각각 다음을 써주면 된다.

-username : createuser -s postgres 로 사용자를 생성했기 때문에, 사용자 이름은 postgres 이다.

-password : 다음 명령어로 비밀번호를 설정할 수 있다. 나는 우선 1234로 설정하였다.(보안상 괜찮겠지?)

ALTER USER postgres PASSWORD '원하는 비밀번호';

-hostname : 로컬에서 접속할 것이므로, localhost로 작성해주면 된다.

-port(포트 번호) : 기본적으로 PostgreSQL은 포트 5432에서 동작한다. 특별히 포트를 변경하지 않았다면, 5432로 설정하면 된다.

-/guestbook : 연결하려는 데이터베이스 이름을 써주면 된다.

완성된 코드는 다음과 같다.

DATABASE_URL=postgres://postgres:1234@localhost:5432/guestbook

하지만 비밀번호를 설정하지 않았고, 기본적으로 'trust' 인증(local에서는 비밀번호 없이 사용 가능)을 사용한다면, password 없이 다음 형태로도 가능하다.

DATABASE_URL=postgres://postgres@localhost:5432/guestbook

백엔드 완성된 코드는 다음과 같다.

const express = require("express");
const cors = require("cors");
const { Pool } = require("pg");
require("dotenv").config(); //dotenv 패키지가 .env 파일에 정의된 환경 변수를 로드하도록 함.
console.log(process.env.DATABASE_URL);

const app = express();
app.use(cors());
app.use(express.json());

const pool = new Pool({
  connectionString: process.env.DATABASE_URL,
  ssl: false,
});

// 방명록 항목 추가
app.post("/api/guestbook", async (req, res) => {
  const { name, message, password } = req.body;
  try {
    const result = await pool.query("INSERT INTO guestbook (name, message, password) VALUES ($1, $2, $3) RETURNING *", [
      name,
      message,
      password,
    ]);
    res.json(result.rows[0]);
  } catch (err) {
    res.status(500).json({ error: err.message });
  }
});

// 방명록 항목 가져오기
app.get("/api/guestbook", async (req, res) => {
  try {
    const result = await pool.query("SELECT id, name, message, created_at FROM guestbook ORDER BY id DESC");
    res.json(result.rows);
  } catch (err) {
    res.status(500).json({ error: err.message });
  }
});

// 방명록 항목 수정
app.put("/api/guestbook/:id", async (req, res) => {
  const { id } = req.params;
  const { message, password } = req.body;
  try {
    const result = await pool.query("SELECT password FROM guestbook WHERE id = $1", [id]);
    if (result.rows.length > 0 && result.rows[0].password === password) {
      const updateResult = await pool.query(
        "UPDATE guestbook SET message = $1 WHERE id = $2 RETURNING id, name, message, created_at",
        [message, id]
      );
      res.json(updateResult.rows[0]);
    } else {
      res.status(403).json({ error: "비밀번호가 일치하지 않습니다." });
    }
  } catch (err) {
    res.status(500).json({ error: err.message });
  }
});

// 방명록 항목 삭제
app.delete("/api/guestbook/:id", async (req, res) => {
  const { id } = req.params;
  const { password } = req.body;
  try {
    const result = await pool.query("SELECT password FROM guestbook WHERE id = $1", [id]);
    if (result.rows.length > 0 && result.rows[0].password === password) {
      await pool.query("DELETE FROM guestbook WHERE id = $1", [id]);
      res.json({ message: "삭제되었습니다." });
    } else {
      res.status(403).json({ error: "비밀번호가 일치하지 않습니다." });
    }
  } catch (err) {
    res.status(500).json({ error: err.message });
  }
});

// 서버 실행
const PORT = process.env.PORT || 3001;
app.listen(PORT, () => {
  console.log(`Server is running on port ${PORT}`);
});

3. 프론트엔드 코드 작성

리액트로 다음과 같은 순서로 프로젝트를 먼저 생성한다.

cd ../frontend
npx create-react-app .

그리고 App.js 파일의 코드는 다음과 같다.

import React, { useState, useEffect } from 'react';

function App() {
    const [name, setName] = useState('');
    const [message, setMessage] = useState('');
    const [password, setPassword] = useState('');
    const [guestbookEntries, setGuestbookEntries] = useState([]);

    useEffect(() => {
        fetch('http://localhost:3001/api/guestbook')
            .then(response => response.json())
            .then(data => setGuestbookEntries(data));
    }, []);

    const handleSubmit = (e) => {
        e.preventDefault();
        fetch('http://localhost:3001/api/guestbook', {
            method: 'POST',
            headers: {
                'Content-Type': 'application/json',
            },
            body: JSON.stringify({ name, message, password }),
        })
        .then(response => response.json())
        .then(newEntry => {
            setGuestbookEntries([newEntry, ...guestbookEntries]);
            setName('');
            setMessage('');
            setPassword('');
        });
    };

    const handleDelete = (id) => {
        const userPassword = prompt('비밀번호를 입력하세요:');
        fetch(`http://localhost:3001/api/guestbook/${id}`, {
            method: 'DELETE',
            headers: {
                'Content-Type': 'application/json',
            },
            body: JSON.stringify({ password: userPassword }),
        })
        .then(response => {
            if (response.status === 403) {
                alert('비밀번호가 일치하지 않습니다.');
            } else {
                setGuestbookEntries(guestbookEntries.filter(entry => entry.id !== id));
            }
        });
    };

    const handleEdit = (id) => {
        const newMessage = prompt('수정할 메시지를 입력하세요:');
        const userPassword = prompt('비밀번호를 입력하세요:');
        fetch(`http://localhost:3001/api/guestbook/${id}`, {
            method: 'PUT',
            headers: {
                'Content-Type': 'application/json',
            },
            body: JSON.stringify({ message: newMessage, password: userPassword }),
        })
        .then(response => {
            if (response.status === 403) {
                alert('비밀번호가 일치하지 않습니다.');
            } else {
                response.json().then(updatedEntry => {
                    setGuestbookEntries(
                        guestbookEntries.map(entry => entry.id === id ? updatedEntry : entry)
                    );
                });
            }
        });
    };

    return (
        <div className="App">
            <h1>방명록</h1>
            <form onSubmit={handleSubmit}>
                <input
                    type="text"
                    placeholder="이름"
                    value={name}
                    onChange={(e) => setName(e.target.value)}
                    required
                />
                <textarea
                    placeholder="메시지"
                    value={message}
                    onChange={(e) => setMessage(e.target.value)}
                    required
                />
                <input
                    type="password"
                    placeholder="비밀번호"
                    value={password}
                    onChange={(e) => setPassword(e.target.value)}
                    required
                />
                <button type="submit">남기기</button>
            </form>
            <h2>방명록 목록</h2>
            <ul>
                {guestbookEntries.map(entry => (
                    <li key={entry.id}>
                        <strong>{entry.name}:</strong> {entry.message} <br />
                        <small>{new Date(entry.created_at).toLocaleString()}</small> <br />
                        <button onClick={() => handleEdit(entry.id)}>수정</button>
                        <button onClick={() => handleDelete(entry.id)}>삭제</button>
                    </li>
                ))}
            </ul>
        </div>
    );
}

export default App;

4. 프론트 서버 및 백엔드 서버 실행. 그리고 연결 확인.

프론트는 npm start, 백엔드는 node index.js 명령어를 사용하여 각각 실행해준다.

그리고 다음 명령어를 통해서, .env에서 DATABASE_URL 변수를 잘 가져오는지 확인한다.

console.log(process.env.DATABASE_URL);

나는 처음에 오류가 있었는데, dotenv 라이브러리를 통해서 .env 파일의 변수를 가지고 오는 원리인데, 백엔드 프로젝트에 dotenv 라이브러리가 설치되어있지 않았다. 이를 설치해줬다. (원래 초반에도 설치하긴 했는데, 다시 깔았더니 되긴 됐다.)

npm install dotenv

그리고 서버를 종료했다가 재실행하니까 되었다.

완전히 성공적으로 가져오는 것을 볼 수 있다! 데이터베이스를 직접 설계하고, 가지고와서 프로젝트를 완성하고, 너무 뿌듯하다.

쌓인 데이터는 접속된 터미널에서 SELECT * FROM guestbook; 명령어를 통해서 터미널에서 확인할 수 있다.

css가 하나도 없어서, 가볍게 css를 만들었다.

.App {
  max-width: 600px;
  margin: 50px auto;
  padding: 20px;
  font-family: Arial, sans-serif;
  background-color: #f9f9f9;
  border-radius: 10px;
  box-shadow: 0 2px 10px rgba(0, 0, 0, 0.1);
}

h1,
h2 {
  text-align: center;
  color: #333;
}

form {
  display: flex;
  flex-direction: column;
  gap: 10px;
  margin-bottom: 20px;
}

input[type="text"],
input[type="password"],
textarea {
  padding: 10px;
  border: 1px solid #ccc;
  border-radius: 5px;
  font-size: 16px;
}

textarea {
  resize: vertical;
  min-height: 80px;
}

button {
  padding: 10px;
  font-size: 16px;
  color: white;
  background-color: #007bff;
  border: none;
  border-radius: 5px;
  cursor: pointer;
  transition: background-color 0.3s ease;
}

button:hover {
  background-color: #0056b3;
}

ul {
  list-style-type: none;
  padding: 0;
}

li {
  background-color: #fff;
  padding: 15px;
  border-radius: 5px;
  margin-bottom: 10px;
  box-shadow: 0 1px 3px rgba(0, 0, 0, 0.1);
}

li strong {
  font-weight: bold;
}

li small {
  color: #666;
  display: block;
  margin-bottom: 10px;
}

li button {
  margin-right: 10px;
  background-color: #dc3545;
}

li button:first-child {
  background-color: #ffc107;
}

li button:first-child:hover {
  background-color: #e0a800;
}

li button:last-child:hover {
  background-color: #c82333;
}

App.js 파일의 맨 위에 다음 코드만 추가해주면 된다.

import './App.css';

완성된 사진은 다음과 같다!

[문제]

https://www.acmicpc.net/problem/11062

-근우(선발 주자)와 명우(후발 주자)가 가장 왼쪽이나 오른쪽 카드를 가져간다.

-최종적으로 근우가 큰 값을 가지도록 했을 때, 근우의 점수를 구하는 것이 목표.

[문제 쪼개기]

-큰 문제를 작은 문제로 쪼개보자.

큰 문제는 '모든 카드에서 최선의 선택'을 하는 것이다. 그런데 남아있는 카드가 [1, 2, 5, 2]라면, 근우는 첫 번째 카드를 가져갈지, 마지막 카드를 가져갈지 선택을 해야만한다.

① 카드가 1장 있을 때 

근우가 A을 가지고 간다.

근우 A점, 명우 0점

② 카드가 2장 있을 때

근우는 고민없이 max(A, B) 값을 가지고 간다.

③ 카드가 3장 있을 때

근우가 A를 가져가면, 명우는 B,C 중에서 큰 값을 가지고 간다.

근우가 C를 가져가면 명우는 A,B 중에서 큰 값을 가지고 간다.

d[i][j] 는 i 번째 카드부터 j번째 카드까지 남아있을 때, 근우가 최적의 전략으로 얻을 수 있는 최대 점수를 의미한다.

1) 왼쪽에서 카드 선택

i 번째 카드를 선택하면, 근우는 cards[i]를 얻고, 명우는 [i+1, j] 구간에서 최적의 선택이 된다.

근우가 첫 번째 카드를 선택했을 때 최종 점수는,

cards[i] + (남은 카드에서 명우가 얻을 점수를 제외한 값)이 됩니다.

즉, dp[i][j] = cards[i] + (전체 점수 - dp[i+1][j])

2) 오른쪽에서 카드 선택

j 번째 카드를 선택하면, 근우는 cards[j]를 얻고, 명우는 [i, j-1] 구간에서 최적을 선택을 하게 된다.

즉, dp[i][j] = cards[i] + (전체 점수 - dp[i][j-1])

3) 최종 점화식

dp[i][j] = max(cards[i] + (전체 점수 - dp[i+1][j]), cards[j] + (전체 점수 - dp[i][j-1]))

=> 실제로 코드 쓸 때는, 내 점수를 현재 카드 점수 + min(근우가 왼쪽 카드 선택하고 남은 점수, 근우가 오른쪽 카드 선택하고 남은 점수) 로 계산함.

C++전체 코드

1. 위 로직대로, 전체 점수에서 명우가 더 큰 값을 가져간다는 로직

#include <iostream>
#include <vector>
#include <cstring> //memset

using namespace std;

int dp[1001][1001]; //dp테이블 정의
int sum[1001]; //카드 점수의 누적 합을 저장

//점수 계산을 위한 함수
int getMaxScore(vector<int>& cards, int left, int right) {
    //기저 조건 : 만약 left 가 right를 넘어서면, 유효하지 않은 범위이므로 0변환
    if (left > right) return 0;
    
    //이미 계산된 값이 있으면 그 값을 사용
    if (dp[left][right] != -1) return dp[left][right];
    
    //전체 카드의 총합 중에서, 상대방이 최선의 선택을 해서 얻을 수 있는 점수를 뺀 값을 계산
    int totalSum = sum[right + 1] - sum [left];
    int pickLeft = totalSum - getMaxScore(cards, left+1, right);
    int pickRight = totalSum - getMaxScore(cards, left, right-1);
    
    //두 경우 중 최대값을 DP 테이블에 저장
    return dp[left][right] = max(pickLeft, pickRight);
    
}

int main() {
    int T;
    cin >> T;
    
    while(T--) {
        //각 카드 점수 입력
        int N;
        cin >> N;
        vector<int> cards(N);
        for (int i=0; i<N; i++){
            cin >> cards[i];
        }
        
        //DP테이블을 -1로 초기화
        memset(dp, -1, sizeof(dp));
        
        //카드 점수의 누적 합 계산
        sum[0]=0;
        for (int i=0; i<N; i++){
            sum[i+1] = sum[i] + cards[i];
        }
        
        //0번부터 N-1번까지 카드가 있을 때 근우가 얻는 최대 점수 계산
        cout << getMaxScore(cards, 0, N-1) << endl;
    }
    return 0;
}

2. 명우가 둘 중에 더 작은 것을 가져간다는 로직으로 짠 코드

#include <iostream>
#include <vector>
#include <cstring> //memset을 사용하기 위해

using namespace std;

int dp[1001][1001]; //dp table 정의

//점수 계산을 위한 함수

int getMaxScore(vector<int>& cards, int left, int right) {
    
    //기저조건 : 만약 left가 right를 넘어서면, 유효하지 않은 범위이므로 0반환
    if (left > right ) return 0;
    
    //기저조건 : 만약 왼쪽=오른쪽이 같으면, 카드가 하나 남았다는 의미
    if (left == right) return cards[left];
    
    //이미 계산된 값이 있으면 그 값 사용
    if (dp[left][right] != -1) return dp[left][right];
    
    //왼쪽을 선택하는 것은 = 준우가 왼쪽 값을 얻고, 다른애가 왼쪽을 고른 것과 오른쪽을 고른 것 중 더 작은 값을 가지는 것
    int pickLeft = cards[left] + min(getMaxScore(cards, left+2, right), getMaxScore(cards, left+1, right-1));
    int pickRight = cards[right] + min(getMaxScore(cards, left+1, right-1), getMaxScore(cards, left, right-2));
    
    //두 경우 중 최대값을 DP 테이블에 저장
    return dp[left][right] = max(pickLeft, pickRight);
}

int main() {
    int T;
    cin >> T;
    
    while (T--){
        //각 카드 점수 입력
        int N;
        cin >> N;
        vector<int> cards(N);
        for (int i = 0; i<N; i++){
            cin >> cards[i];
        }
        
        //DP 테이블을 -1로 초기화
        memset(dp, -1, sizeof(dp));
        
        //0번부터 N-1번까지 카드가 있을 때 근우가 얻는 최대 점수 계산
        cout << getMaxScore(cards, 0, N-1) <<endl;
    }
    return 0;
}

프로님 설명 받아 적은 내용 ...

[DP테이블 정의하기]

dp[i][j]를 i번째 카드부터 j번째 카드까지 있을 때 근우가 얻을 수 있는 최대 점수로 정의한다.

-초기화

'i==j'인 경우, 즉 카드가 하나만 남아 있을 때, 근우는 남아있는 카드의 점수를 모두 가져갑니다. 따라서 dp[i][i]=카드의 점수[i]가 됩니다.

-점화식

근우가 왼쪽 카드i를 가져가면, 명우는 i+1부터 j까지 카드를 가져가게 됩니다.

근우가 오른쪽 카드 j를 가져가면, 명우는 i부터 j-1까지의 카드를 선택하게 됩니다.

왼쪽카드를 선택하면

a[i] + s(i,j) - d(i+1, j)

오른쪽카드

a[j] + s(i,j) - d(i, j+1)

이런 문제는 4선 DP로 쌓아올리거나, top-down or bottom-up으로 풀 수 있다.

점화식이 어려운, 냅색(배낭문제, KnapSack) 이라는 유형을 변형한 문제이다.

맨 처음 출력/입력 조건을 본다.

문제 내용상 흐름을 파악해봤을 때, N은 100, M은 1억이다. 

완전탐색을 가정했을 때, 활성화됐는지 아닌지 쭉 파악하는 시간복잡도는 on/off 여부를 모두 체크하면 (2^N)이다.

입력값은 1억까지인데, 2^N으로 감당할 수 있는 입력값은 20이므로, 이는 시간복잡도 내에 해결할 수 없다.

=> 따라서 다른 방법을 생각해보자. DP로 해야한다.

DP로 하려면 3가지가 필요하다.

1)DP 배열

2)점화식

3)초깃값

dp[i][j]에서 i와 j를 뭐라고 생각할지 판단해야한다.

처음에는 i번째에 확보할 수 있는 메모리 j에 드는 비용 cost를 dp[i][j]라고 세웠다. 그런데 이렇게 되면, j의 범위가 1억까지이므로 메모이제이션이 불가능하다.

따라서 d[i][j]를 i번째 앱까지, j의 cost로 확보할 수 있는 메모리로 정의한다.

실제로 문제 풀 때도 손으로 그려서 파악한다.

d[j-1][j-cost[i]+m[i]와 d[i-1][j] 비교

와! 점화식이 왜 d[i-1][j-cost[i]] + memory[i] 이런식인가 했더니, 해당하는 비용값을 하나 더하면 당연히 필요로 하는 j값에는 cost[i]만큼 빠진 것이 이제 필요로 되고, 대신 메모리를 얻으니까 이런거다.

강사님께서 주신 자바 코드.

package b7579;

import java.util.Scanner;

/*
 * 백준 7579 앱
 * updated 2024-02-17
 */
public class Main2 {
    static int N, M;    // 앱개수, 필요한 메모리
    static int[] m; // 앱 메모리
    static int[] c; // 비용
    static int sum;
    static int[][] d;       // 비용 i번째 앱까지 j 의 비용을 들였을 때 얻을 수 있는 최대 메모리양

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        m = new int[N+1];
        c = new int[N+1];

        for (int i=1; i<=N; i++) {
            m[i] = sc.nextInt();
        }
        for (int i=1; i<=N; i++) {
            c[i] = sc.nextInt();
            sum += c[i];
        }
        d = new int[N+1][sum+1];
        for (int i=1; i<=N; i++) {
            for (int j=0; j<=sum; j++) {
                if (j - c[i] >=0) d[i][j] = Math.max(d[i][j], d[i-1][j-c[i]] + m[i]);
                d[i][j] = Math.max(d[i][j], d[i-1][j]);
            }
        }
        int cost = 0;
        for (int i=1; i<=N; i++)
            for (cost=0; cost<sum && d[i][cost]<M; cost++);
        System.out.println(cost);       
    }

}

그리고 C++코드로 변환한 것

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N, M; // 앱 개수, 필요한 메모리;
    cin >> N >> M;
    
    vector<int> m(N+1); // 앱 메모리
    vector<int> c(N+1); //비용
    int sum = 0;
    
    //입력 받는 것 - python과 달리, 미리 공간을 파놓고 입력을 받는다.
    for (int i=1; i<=N; i++){
    	cin >> m[i];
    }
    
    for (int i=1; i<=N; i++){
    	cin >> c[i];
        sum += c[i];
    }
    
    //비용 1번째 앱까지 j의 비용을 들였을 때 얻을 수 있는 최대 메모리양
    vector<vector<int>> d(N+1, vector<int>(sum+1,0));
    
    for (int i=1; i<=N; i++){
    	for (int j=0; j <=sum; j++){
        	if (j-c[i] >=0) {
            	d[i][j] = max(d[i][j], d[i-1][j-c[i]] + m[i]);
            }
            d[i][j] = max(d[i][j], d[i-1][j]);
        }
    }
    
    int cost = sum;
    for (int i=0; i<=sum; i++){
    	if (d[N][i] >= M) {
        	cost = i;
            break;
        }
    }
    
    cout << cost << endl;
    
    return 0;
}

그래프 알고리즘에서 '최소 비용', '최단 거리'를 구해야 하는 경우,

사용할 수 있는 대표적인 알고리즘으로는

'다익스트라 알고리즘', '벨만-포드 알고리즘', '플로이드 워샬 알고리즘'이 있다.

이번 글에서는 '다익스트라 알고리즘'에 대해서 알아보겠다.

1. 언제 쓰이나요?

다익스트라 알고리즘은 '최소 비용' 중에서도,

주어진 두 노드(시작 노드, 도착 노드)사이의 최소 비용인 '경로'를 찾을 때 유용하게 사용된다.

가중치의 값이 모두 양수일 때(즉, 가중치에 음수가 없을 때) 사용된다.

하다보면 '당장 눈 앞에 드는 비용이 더 적다고, 해당 정점을 다시는 안쳐다봐도 될까?' 이런 질문이 생길 수 있다.

하지만 가중치 값이 양수이기만 하면 이는 만족하므로 걱정하지 않아도 된다.

2. 동작 원리

2-1.O(N^2) 반복문을 통한 시간 복잡도

지금부터 '비용' 이라는 말을 많이 사용하게 될 것이다. 이 '비용' 값은 1차원 배열 Dist[] 배열에 저장되어 있다고 생각하자.

0.초기 Dist[] 배열 모든 값은, 무한대(INF)로 초기화 되어있다.

1.시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.

2.방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로 선택해준다.

3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.

4. 2-3번 과정을 반복한다.

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.

//시작 노드-연결된 i노드의 가격을 Dist 배열에 업데이트
for (int i=1; i <= V; i++) Dist[i] = MAP[Start][i];
Dist[Start]=0; //시작 노드에서의 비용은 0으로 바뀐다.
Select[Start]=true;

2.방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로 선택해준다.

int Find_Shortest_Node()
{
	int Min_Dist, Min_Idx;
    Min_Dist = INF;
    Min_Idx = -1;
    
    for (int i=1; i<=V; i++)
    {
    	//선택된 건 넘기자~
    	if (Select[i] == true) continue;
        //현재 제일 작은 값보다, Dist[i] 비용이 더 작으면, Dist[i] 비용을 최솟값으로 선택
        if (Dist[i] < Min_Dist)
        {
        	Min_Dist = Dist[i];
            Min_Idx = i;
        }
    }
    return Min_Idx;
}

3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.

void Update_Dist(int NewNode)
{
	for (int i=1; i<=V; i++){
    	//선택됐던 것은 넘어가고~
    	if (Select[i] == true) continue;
        //아닌건
        if (Dist[i] > Dist[NewNode] + MAP[NewNode][i])
        {
        	Dist[i] = Dist[NewNode] + MAP[NewNode][i];
        }
    }
}

4.2-3번 과정을 반복한다.

몇 번 반복해야하는지 판단해야한다.

즉 업데이트는 N(정점의 수)-1번 진행한다.

[전체 코드]

//다음 노드 선택
int Find_Shortest_Node()
{
	int Min_Dist, Min_Idx;
    Min_Dist = INF;
    Min_Idx = -1;
    
    for (int i=1; i <=V; i++) //V는 정점의 수
    {
    	if (Select[i] == true) continue;
        if (Dist[i] < Min_Dist)
        {
        	Min_Dist = Dist[i];
            Min_Idx = i;
        }
    }
    return Min_Idx;
}

//선택한 노드에 대해 업데이트 해주기
void Update_Dist(int NewNode)
{
	for (int i=1; i <=V; i++)
    {
    	if (Select[i] == true) continue;
        if (Dist[i] > Dist[NewNode] + MAP[NewNode][i])
        {
        	Dist[i] = Dist[NewNode] + MAP[NewNode][i];
        }
    }
}

void Dijkstra()
{
	//시작노드 초기화
	for ( int i=1; i <= V; i++) Dist[i] = MAP[Start][i];
    Dist[Start] = 0;
    Select[Start] = true;
   	
    //반복해줌
    for (int i=0; i<V-1; i++)
    {
    	int NewNode = Find_Shortest_Node();
        
        Select[NewNode] = true;
        Update_Dist(NewNode);
    }
}

2-2. 우선순위 큐를 이용한 방법 O(E*logN) E=간선 수, N=노드 수

인접한 간선들을 모두 Queue에 집어 넣은 후, 최소힙을 구하는 연산을 통ㅎ서, 최소비용이 드는 정점부터 처리하는 방식이다.

시간복잡도가 O(E*logN)인 이유는

-모든 정점들에 대해서 최소힙으로 추출하는데 걸리는 시간복잡도가 O(logN)이다.

-각 노드마다 인접한 모든 간선들을 확인해봐야하므로 시간복잡도가 O(E)이다.

void Dijkstra_Using_Heap()
{
	priority_queue<pair<int, int>> PQ; //값이 클 수록 더 높은 우선순위를 갖게된다. 따라서 아래에서 -를 붙여서 값의 크기를 반전한다.
    PQ.push(make_pair(0, Start));
    Dist[Start] = 0;
    
    while (PQ.empty() ==0)
    {
    	int Cost = -PQ.top().first; //간선 길이에 -붙이는 이유는 최소힙 구현을 위해서
        int Cur = PQ.top().second;
        PQ.pop();
        
        for ( int i=0; i<Vertex[Cur].size(); i++)
        {
        	int Next = Vertex[Cur][i].first;
            int nCost = Vertex[Cur][i].second;
            
            if (Dist[Next] > Cost + nCost)
            {
            	Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next)); //간선 길이에 -붙이는 이유는 최소힙 구현을 위해서
            }
        }
    }
    
    for ( int i=1; i<=V;i++)
    {
    	if (Dist[i] == INF) cout << "INF" << endl;
        else cout << Dist[i] << endl;
    }
}

아래와 같이 선언하면, 값이 작을 수록 우선순위를 갖는 최소힙으로 사용이 가능하다.

priority_queue<int, vector<int>, greater<int>> PQ;

[출처]

개인적으로 공부를 위하여, 아래 블로그 내용을 상세하게 참고한 글이다.

https://yabmoons.tistory.com/364

[핵심암기]

1.cin >> a >> b; 로 띄어쓰기가 자동으로 처리되어 입력을 받을 수 있다.

1.문제

https://www.acmicpc.net/problem/1000

2.정답 코드

#include <iostream>

using namespace std;

int main() {
	
    ios::sync_with_stdio(false);
    cin.tie(0);
	
	int a, b, c;
    
    cin >> a >> b;
    c = a + b;
    cout << c << "\n";
}

3.배운점

3-1. 띄어쓰기가 포함된 숫자 2개 입력 받기

c++에서는 다음과 같이 띄어쓰기가 포함된 연산을 입력 받을 수 있다.

cin이 자동으로 띄어쓰기를 처리해준다.

cin >> a >> b;

3-2. python의 input()처럼 한 줄로 입력받는 법

#include <iostream>
#include <string> //문자열 사용을 위해 필요하다.

using namespace std;

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
    
	string input_line;
	getline(cin, input_line);

	cout << "You entered: " << input_line <<"\n";

	return 0;
}

3-2. python과의 입력 코드 및 시간 비교

python에서는 모든 입력을 문자열로 받는다. 따라서 문자열을 입력 받고 쪼갠 다음 각각의 문자에 매핑해줘야하는 코드였다.

a, b = map(int,input().split())

간단한 입출력 예제인데도

메모리는 약 5배 시간은 c++은 거의 걸리지 않는 정도로 차이난다.

왜 c++을 알아야한다고 하는지, 확실히 체감이 되기 시작한다.

[핵심암기]

1. c++코드 짤 때 효율적인 기본 세팅은 다음과 같습니다. #iostream #namespace #"\n"

#include <iostream>

using namespace std; // namespace 한 번에 가져오는 tip

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    
	std::cout << "Hello, World!" << "\n";
	return 0;
}

1. C++ 3가지 입출력 정리

C++에는 기본적으로 3가지 입출력 방식이 있습니다.

3번 cstdio > 2번 stdio.h > 1번 iostream 순서로 메모리 성능이 더 좋습니다.

1.iostream : C++의 표준 입출력 헤더파일 입니다. 대표적으로 cin, cout이 있습니다.

iostream도 입출력을 빠르게 할 수 있는 방법이 있긴 합니다. 나중에 공부해보세요.

#include <iostream>

main() {
	int a;
    std::cin >> a;
    std::cout <<a;
}

2.stdio.h : C++은 기본적으로 C의 확장버전입니다. 즉, C의 표준 라이브러리를 사용할 수 있기 때문에 C의 표준 라이브러리 헤더 파일들을 include하여 해당 함수들을 사용할 수 있습니다.

#include <stdio.h>

main() {
	int a;
    scanf("%d", &a);
    printf("%d", a);
}

3.cstdio : stdion.h와 크게 다를 것은 없습니다. C언어에서는 namespace 개념이 없지만, c++에서는 namespace를 지원하면서 C언어의 표준 라이브러리를 namespace안에서도 사용할 수 있도록 한 것입니다. 함수 기능상에서는 차이가 없습니다.

#include <cstdio>

main() {
	int a;
    scanf("%d", &a); // std::scanf도 가능
    printf("%d", a); // std;:printf도 가능
}

2. [백준 C++] 2557번 : Hello World

위에서 배운 3가지 방법으로 문제를 풀어보겠습니다.

1.iosream

#include <iostream>

int main() {
	std::cout << "Hello World!";
    return 0;
}

2.stdio.h

#include <stdio.h>

int main() {
	printf("Hello World!");
    return 0;
}

3.cstdio

#include <cstdio>

int main() {
	printf("Hello World!");
    return 0;
}

3. C++ 입출력 속도 해결

시간초과 방지를 위해서 아래 두 줄을 추가해주는 것이 좋습니다.

ios::sync_with_stdio(false);
cin.tie(0);

기존 입출력을 cin, cout, printf, scanf 함수를 이용했다가,

위의 두 줄을 추가하고 cin, cout만 사용하면 입출력 속도가 빨라집니다.

3-1. ios::sync_with_stdio(false)

이 코드는 C와 C++ 표준 stream의 동기화를 비활성화합니다.

동기화가 활성화 되어있다는 것의 의미는, C 스타일과 C++ 스타일의 입출력을 혼합해도 문제가 없습니다.

예를 들어 C스타일(printf, scanf)과 C++스타일(cin cout)을 혼합하여 사용해도 문제가 없습니다.

하지만 위의 코드를 추가하게 되면, 두 스타일 혼합은 할 수 없지만,

C++ 스타일 코드만 사용하면, 기존 동기화 과정에서 필요하던 시간이 절약되어 입출력 속도가 빨라집니다.

다만, 이 코드를 사용하면 기존 C의 표준 입출력인 scanf, printf, getchar 함수 사용시 오류가 납니다.

따라서 C++의 입출력인 cin, cout만 사용하도록 주의해야합니다.

3-2. cin.tie(0);

cin.tie는 평소 cin과 cout을 묶어줍니다.

예를 들어서 아래와 같은 코드가 있다고 생각해봅시다.

cout << "이름을 입력하세요" <<;
cin >> name;

평소에는 cin과 cout이 묶어져 있으므로,

반드시 "이름을 입력하세요"가 출력된 후 이름을 입력할 수 있습니다.

하지만 cin.tie(0) 혹은 cin.tie(null) 코드를 추가해주면,

"이름을 입력하세요"가 출력되기 전에 이름을 입력할 수 있습니다.

평소에는 이름을 묻기도 전에 이름을 입력할 수 있는 어색한 상황이 펼쳐지겠지만,

알고리즘 문제를 풀 때는 상관없기 때문에 이 코드를 많이 사용합니다.

일반적으로는 scanf printf가 cin cout보다 빠릅니다.

하지만 위에서 다룬 2줄의 코드를 추가하고, 두 줄을 입력한 뒤 프로그래밍 하는 것이 좋습니다.

3-3. 사용 시 주의할 점

두 호출은 성능과는 아무 관련 없는 다른 의미를 가집니다.

웬만하면 알고리즘 문제 풀 때만 시간 절약을 위해 사용합시다.

모든 프로그램에 입출력 시간을 절약하기 위해 사용하는 것은 잘못된 방법입니다.

4. 입출력 시 시간 절약을 위하여

입출력시 개행할 때, endl 대신 '\n'을 사용해야 시간 절약을 할 수 있습니다.

둘 다 개행 문자라는 점에서 차이는 없습니다.

하지만 endl은 버퍼를 비우고 즉시 ans 부분을 출력합니다. 버퍼를 지우는 과정 때문에 속도가 더 느립니다.

"\n"은 단순히 개행만 해주고, 버퍼를 비우는 역할은 없습니다.

1)  endl

std::cout<<ans<<std::endl;

2) "\n"

std::cout<<ans<<'\n';

5. 입출력 절약한 백준 2557번 나의 최종 코드

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cout << "Hello World!" <<"\n";
    return 0;
}

[참고자료]

연습을 위해 아래 두 글을 상세하게 참고하였습니다.

https://st-lab.tistory.com/200

https://dingcoding.tistory.com/62

나는 현재 NEXT에서 알고리즘 스터디를 진행하고 있다.

빠른 바로 가기를 위해서 다음 링크를 추가해둔다. 오 그리고 옆에다가 간단히 내용도 정리해두면 좋겠다.

200 - 자료구조 1

• 스택
• 단어 뒤집기
• 괄호
• 스택 수열
• 에디터
• 큐
• 조세퍼스 문제
• 덱

201 - 자료구조 1 (연습)

• 단어 뒤집기 2
• 쇠막대기
• 오큰수
• 오등큰수

203 - 자료구조 1 (참고)

• 후위 표기식2
• 후위 표기식
• 알파벳 개수
• 알파벳 찾기
• 문자열 분석
• 단어 길이 재기
• ROT13
• 네 수
• 접미사 배열

300 - 수학 1

• 나머지
• 최대공약수와 최소공배수
• 최소공배수
• 소수 찾기
• 소수 구하기
• 골드바흐의 추측
• 팩토리얼
• 팩토리얼 0의 개수
• 조합 0의 개수

301 - 수학 1 (연습)

• GCD 합
• 숨바꼭질 6
• 2진수 8진수
• 8진수 2진수
• -2진수
• 골드바흐 파티션

303 - 수학 1 (참고)

• 진법 변환 2
• 진법 변환
• Base Conversion
• 소인수분해

400 - 다이나믹 프로그래밍 1

• 1로 만들기
• 2×n 타일링
• 2×n 타일링 2
• 1, 2, 3 더하기
• 카드 구매하기
• 카드 구매하기 2
• 1, 2, 3 더하기 5
• 쉬운 계단 수
• 이친수
• 가장 긴 증가하는 부분 수열
• 가장 긴 증가하는 부분 수열 4
• 연속합
• 제곱수의 합
• 합분해

401 - 다이나믹 프로그래밍 1 (연습)

• 1, 2, 3 더하기 3
• RGB거리
• 동물원
• 오르막 수
• 스티커
• 포도주 시식
• 정수 삼각형
• 가장 큰 증가 부분 수열
• 가장 긴 감소하는 부분 수열
• 가장 긴 바이토닉 부분 수열
• 연속합 2
• 타일 채우기

402 - 다이나믹 프로그래밍 1 (도전)

• 동물원
• RGB거리 2
• 합분해

[문제]

1.A진법으로 나타낸 숫자를 B진법으로 변환시켜주는 프로그램을 작성하기로 하였다.

2.N진법이란, 한 자리에서 숫자를 표현할 때 쓸 수 있는 가짓수가 N개라는 뜻이다.

3.예를들어, N=17일 때, 한 자릿수에서 사용할 수 있는 수는 0, 1, 2, ..., 17가지이다.

[입력]

1.첫 줄에는 A진법, B진법이 공백을 구분하여 주어진다. (2<=A,B<=30 이하의 자연수)

2.입력의 두 번째 줄에는 A진법으로 나타낸 숫자의 자리수의 개수 m(1<=m<=25)이 주어진다.

3.세 번째 줄에는 A진법을 이루고 있는 숫자 m개가 공백으로 구분되어 높은 자릿수부터 주어진다.

4.각 숫자는 0이상 A미만임이 보장되며, 0으로 시작되는 경우는 존재하지 않는다.

5.A진법 수를 10진법으로 변환하면, 양의 정수이며 2^20보다 작다.

[출력]

입력으로 주어진 A진법으로 나타낸 수를 B진법으로 변환하여 출력한다.

[예제 입력 1]

17 8

2

2 16

[예제 출력 1]

6 2

[문제 풀이]

1. a_nums를 10진수로 변환할 때, 각 자리를 변환하고 10진수로 합쳐야하는데, 다음과 같이 한 번에 처리하는 오류가 발생했다.

나는 아래 내 코드가 완벽하게, a_nums를 10진수로 바꿔준다고 생각했는데, 아닌가보다!

문제에 주어져있었다. A진법을 이루고 있는 숫자 m개가 높은 자리수부터 주어진다는 것이므로 결국 하나의 숫자다.

위처럼 잘못 풀었던 첫 번째 코드

import sys
input=sys.stdin.readline

A, B = map(int,input().split())
m=int(input())
a_nums=input().split()
#1.10진수로 변환 시키는 과정 필요
###방법 : int(숫자,n진수)
#a_nums에서 하나씩 꺼내서 x자리에 넣고, 그것은 A진수이니, 10진수로 바꿔주세요. 그리고 a_nums_10에 넣어주세요
a_nums_10=list(map(lambda x : int(x,A), a_nums))

#2.10진수를 n진수로 변환시키는 함수 작성
def convert_to_base(num, base):
    if num==0:
        return 0
    digits=[]
    while num:
        digits.append(int(num%base))
        num=num//base
    return ''.join(str(x) for x in digits[::-1])

#3.a_nums_10 차례대로 넣어서 반환
a_nums_b=list(map(lambda a : convert_to_base(a, B), a_nums_10))
print(*a_nums_b)

[정답코드]

import sys
input=sys.stdin.readline

A, B = map(int,input().split())
m=int(input())
a_nums = list(map(int, input().strip().split()))
#1.10진수로 변환 시키는 과정 필요
###방법 : int(숫자,n진수)
#a_nums에서 하나씩 꺼내서 x자리에 넣고, 그것은 A진수이니, 10진수로 바꿔주세요. 그리고 a_nums_10에 넣어주세요
# a_nums_10=list(map(lambda x : int(x,A), a_nums))
decimal_value=0
for num in a_nums:
    decimal_value=decimal_value*A + num

#2.10진수를 n진수로 변환시키는 함수 작성
def convert_to_base(num, base):
    if num==0:
        return [0] #다른 return 값이 리스트이므로 [0]으로 통일
    digits=[]
    while num:
        digits.append(int(num%base))
        num=num//base
    return digits[::-1]
#3.a_nums_10 차례대로 넣어서 반환
b_nums=convert_to_base(decimal_value, B)
print(' '.join(map(str,b_nums)))

10진수로 변환시키는 저 부분을 이해해야할 것 같다.

1.4일차 복습

최대공약수 : 유클리드 호재법

동치 역원 구하기 : 확장 유클리드 호제법(?)

소수구하기 : 나눠서 구한다(제곱근 지우기), 에라토스테네스의 체

오일러 피 함수 : 1~N-1까지 

경우의 수 : 순열, 조합(조합은 동적 계획법으로 해결)

2. 다리놓기 1010

[문제]

1.도시를 동서로 나누는 큰 일직선 모양의 강이 흐르고 있다. 동서를 잇는 적합한 곳(사이트)에 다리를 짓고자 한다.

2.서쪽에는 N개의 사이트, 동쪽에는 M개의 사이트가 있다.(N<=M)

3.한 사이트에는 한 개의 다리만 연결 가능하며, 서쪽 사이트 개수만큼 다리를 지을 수 있는 경우의 수를 구하여라.

=>결국 오른쪽 M개의 점 중에서 N개를 선택하면, 순서대로 왼쪽에 연결된다고 생각할 수 있다.

[풀이]

지난번에 조합을 한 번 쭉 정리한 적이 있다. 하지만 암기하지는 않았었다. 그래서 기억이 나지 않는다.

정리한 노트를 보고 암기를 오늘 제대로 해야겠다.

암기하기 전에 예상되는 풀이 방법으로는,

-일반식을 새롭게 세웠었다.

-일반식을 새로 가져오는 것 외에는, 라이브러리를 사용하는 방법과, 메모이제이션 방법이 있었던 것 같다.

[정답코드]

def comb(n,k):
    if k > n:
        return 0
    if k==0 or n==k:
        return 1
    
    #k가 n/2보다 큰 경우, nCk=nC(n-k)와 같음. 더 작은 수로 바꿔주는 과정
    if k > n/2 :
        k = n-k

    result=1
    for r in range(k): #r-1까지 돌 것임
        result = result * (n-r) // (r+1)

    return result

c=int(input())
for _ in range(c):
  r, n = map(int, input().split())
  print(comb(n,r))

[팁]

가장 큰 수인 M도 한 번 찍어봐야한다. overflow 방지를 위해서!

최대 크기가 10만으로 주어지면, nlogn 알고리즘을 사용하면 된다.

3. 순열의 순서 1722(골드5)

[문제]

1.임의의 순열(N!)은 정렬할 수 있다. 예를 들어 N=3인 경우, 6가지 경우의 수가 있다. 6가지 경우의 수를 나열하면 앞에서부터 작은 것이 순서상 앞선다.

2.N이 주어지면 , 두 가지 소문제 중 하나를 풀어야한다.

-문제 번호 1) K를 입력받고, N!에서의 K번째 순열을 구한다.

-문제 번호 2) 임의의 순열 N개를 입력받고, 이 순열이 몇 번째 순열인지를 출력하기.

4.사전 1256(골드2)

[문제]

-사전에 수록되어있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져있다. 다른 문자는 없고, 알파벳 순서대로 수록되어있다.

-규완이는 사전을 완성했고, 동호는 사전을 완성하지 못했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에 문자열 하나만 찾을 수 있다.

-N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

-입력 : 첫째 줄에 세 정수 N,M,K가 주어진다.

-출력 : 규완이의 사전에서 K 번째 문자열을 출력한다. 사전에 등록된 문자열 개수가 K보다 작으면 -1을 출력한다.

[풀이]

-경우의 수만 따져가며, 앞에서부터 문자열을 채우는 것이 핵심이다.

-n,m개의 문자로 구성할 수 있는 문자열의 수는 math.comb(n+m,n)이다. a의 자리를 결정하면, 나머지를 z로 채우기만 하면 된다.

-n,m에 대해 (n-1)개의 a와, m개의 z로 만들 수 있는 문자열의 수인 math.comb(n+m-1,n-1)보다 k의 값이 크다면, 맨 앞 

유독 이해가 안되는 문제...

from math import comb as c

a,b,i=map(int,input().split())
s=["z"]*(a+b)

if c(a+b,a)<i:
  print(-1)
else:
  ans=""
  #과정을 반복하여 n,m 둘 중 하나가 0이되거나 k의 값이 0이될 때까지 반복하며 문자열을 채워나가고, 남은 문자가 있다면 그 개수만큼 뒤에 붙여준다.
  while i and (a and b):
    if i > c(a+b-1,a-1): #n-1개의 a와 m개의 z로 만들 수 있는 수 c(a+b-1,a-1)보다 k가 크면, 맨 앞 문자는 a이므로
      ans+="z"
      i-=c(a+b-1,a-1)
      b-=1
    else:
      ans+="a"
      a-=1
  print(ans+"a"*a+"z"*b)

사전 문제랑 순열의 순서 문제 이해가 잘 안됨. 다시 봐야함 ...

직접 시간 들여서 풀어봐야하는 듯.

5. 6549 히스토그램에서 가장 큰 직사각형

[풀이]

https://codable.tistory.com/1

위의 블로그에 설명이 상세하게 적혀있어서, 참고하며 공부를 해보려고 한다.

1) 분할 정복 풀이 : 중앙값을 기준으로, 양쪽으로 넓혀가며 최댓값을 찾는 작업.

처음 중간값인 8에서 시작하고, 왼쪽과 오른쪽 중 더 높이가 높은쪽으로 확장한다. 그리고 이때의 넓이값도 적어둔다.

또 해당 직사각형과 맞닿아있는 히스토그램 중 더 높은 쪽으로 확장한다. 확장하고나서 넓이를 갱신해준다.

최종적으로 분할 기준을 포함하는 최댓값, 왼쪽 범위의 최댓값, 오른쪽 범위의 최댓값을 모두 구하고, 이 셋을 비교하여 가장 큰 값을 최댓값으로 잡아준다.

어려웠지만 코드 이해 안되는 부분은 손으로 쓰고, 직접 값 넣어서 생각하니 이해가 되었다. 까먹기 전에 복습 혹은 영상을 찍어두면 도움이 될 것 같다.

import sys
input = sys.stdin.readline

res=[]

def divide_and_conquer(histogram, start, end):
  #end=start 같으면, 복잡한 과정 거칠 것 없이 그냥 histogram[end] 또는 histogram[start]다.
  if end == start:
    return histogram[end]
  #만약 end와 start가 바로 한 칸 차이면(붙어 있으면)
  elif end - start == 1:
    #게다가 end보다, start가 더 높이가 높을 경우
    if histogram[end] < histogram[start]:
      #복잡한 과정 할 것 없이,end값에 두 배를 한 것과, start 값 중 더 큰 값 비교
      return max(2*histogram[end], histogram[start])
    else:
      #start 값에 두 배를 한 것과, end 값 중 더 큰 값 비교
      return max(2*histogram[start], histogram[end])

  mid = ( start + end ) //2
  left_area = divide_and_conquer(histogram, start, mid)
  right_area = divide_and_conquer(histogram, mid+1, end)
  left=mid-1
  right=mid+1

  #mid_area : 기존 넓이를 기록할 변수 초기화
  mid_area = histogram[mid]
  #now_height : 현재 높이를 기록할 변수 초기화. 시작은 중간값
  now_height = histogram[mid]

  while start <= left and right <= end:
    #왼쪽과 오른쪽 중 오른쪽 히스토그램 높이가 더 높으면
    if histogram[left] < histogram[right]:
      #'오른쪽 히스토그램 높이' 보다, '현재 높이'가 더 높으므로
      if histogram[right] < now_height:
        #'현재 높이'를 더 낮은 '오른쪽 히스토그램 높이'로 설정한다.
        now_height = histogram[right]
      #그리고 현재까지의 넓이(mid_area)와, 새롭게 지정된 높이(now_height)에 대한 넓이를 비교하여
      #더 높은 것을 새로운 mid_area로 지정한다.
      mid_area = max(mid_area, now_height * (right-left))
      #그리고 오른쪽으로 한 칸 범위를 높인다.
      right +=1
    #왼쪽과 오른쪽 중 왼쪽 히스토그램 높이가 더 높으면
    else:
      if histogram[left] < now_height:
        now_height = histogram[left]
      mid_area = max(mid_area, now_height*(right - left))
      left -= 1
  
  #right는 범위를 벗어났고, 조건이 없어졌다. 왼쪽으로 확장할 공간만 남은 상황.
  while start <= left:
    if histogram[left] < now_height:
      now_height = histogram[left]
    mid_area = max(mid_area, now_height * ( right - left ))
    left -=1
  
  while right <= end:
    if histogram[right] < now_height:
      now_height = histogram[right]
    mid_area = max(mid_area, now_height * ( right - left))
    right+=1
  
  return max(left_area, right_area, mid_area)



res=[]

while True:
  #직사각형의 수, 직사각형의 높이들 주어짐 ex) 7 2 1 4 5 1 3 3
  histogram = list(map(int, input().split()))

  n = histogram[0]
  #입력 마지막 시에 종료 조건
  if n ==0:
    break

  #1부터 넘겨주어, 0번째인 값은 해당되지 않도록 함. 
  res.append(divide_and_conquer(histogram, 1, n))

for i in res:
  print(i)​

6. 가장 긴 증가하는 부분 수열 11053

[문제]

가장 긴 증가하는 부분 수열의 길이를 구하는 문제.

예를 들어 [10, 20, 10, 30, 20, 50]이 주어지면,

[10, 20, 10, 30, 20, 50]

[팁]

-최대수가 1,000으로 주어지면, n^2으로 해결할 수 있다.

-최장증가부분수열(LIS)

-앞에서부터 하나씩 확인한다. 

-나보다 더 앞에 작은게 있어야 붙을 수 있음.

-원리를 계산해봐도 n^2 알고리즘이라는 것을 파악할 수 있음.

[풀이]

dp[i] = A[i]를 마지막 원소로 가지는 부분 수열의 최대 길이.

=> A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는,

A[i]가 추가되기 전 증가부분수열의 마지막 값이, A[i]보다 작은 값이어야한다.

A[i]를 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는,

A[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.

n=int(input())
arr = list(map(int, input().split()))

#i가 0일 때 증가하는 최대 부분 수열의 길이는 1이기 때문에, 테이블을 우선 전부 1로 초기화해줌
d = [1]*n

for i in range(1, n): #1부터 n-1번 인덱스까지의 모든 i에 대하여
  for j in range(i): #i보다 작은 j (0부터 i-1까지 = i보다 작은 것 모두)
    if arr[j] < arr[i]: #j의 원소가 i의 원소보다 작은 값이 존재하면!, 즉, 부분적으로 증가한다면
      d[i] = max(d[i], d[j]+1) #i에서의 최적의 해를 갱신해준다.
print(max(d))

문제 원리는 이해가 됐는데, 코드 이해가 덜 되었다. 따로 이해 필요하다. 유튜브에 강의가 존재하므로 확인해봐야겠다.

뭐야 나무위키에 엄청 상세하게 정리가 잘되어있다. 공부해보자.

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

7. 가장 긴 증가하는 부분 수열2 

이 문제 풀이는 총 세 가지가 존재한다.

1)동적계획법(N^2) = 가장 긴 증가하는 부분 수열1

2)인덱스 트리로 계산 가능 : 이분 탐색보다 코드가 조금 복잡하다.

3)근데 이분탐색이 더 빠르게 코드 짜짐.(강사님 자료에서 설명해주셨던 것. 근데 내용 이해 필요)

1 5

2 3

앞에 다음과 같은 예시가 있다. 5뒤에 붙을 수 있는 애는 3뒤에도 붙을 수 있기 때문에, 당연히 2 3을 선택하면 된다.