티끌 모아 태산

www.acmicpc.net/problem/1725

분할정복을 통해 문제를 해결하였다.

문제에서 middle(중단점) 을 기준으로 히스토그램을 나누었을 때 최대값이 나올 수 있는 경우는 세가지이다.

1. middle을 중심으로 왼쪽부분에 최대값이 있는 경우

2 middle을 중심으로 오른쪽부분에 최대값이 있는 경우

3. middle을 포함하여 직사각형을 이루고 있는 경우

한 기둥을 중심으로 최대값의 넓이를 계산하기 위해서는 더 높은 막대로 확장해나가면서 최대값과 비교하여 최종적으로 최대값을 구한다.

세가지 경우에 대하여 각각 최대값을 구하고 그 중 가장 큰 값을 출력한다.

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int a[100001];

int maxSize(int start, int end) {
	if (start == end)return a[end];

	int mid = (start + end) / 2;
	int lo = mid, hi = mid + 1;
	int height = min(a[lo], a[hi]);
	int ret = height * 2, tmp;

	//start와 end를 기준으로 조건에 따라
	//한쪽 끝에 도달했을 경우 종료
	while (start < lo || hi < end) {
		if (start == lo) tmp = ++hi;
		else if (hi == end) tmp = --lo;
		//더 큰쪽으로 확장을 진행한다.
		else if (a[lo - 1] < a[hi + 1]) tmp = ++hi;
		else tmp = --lo;
		//1칸씩 확장하면서 현재까지의 최대값을 ret에 저장
		height = min(height, a[tmp]);
		ret = max(ret, height * (hi - lo + 1));
	}

	//1. 가운데에 걸치는 부분 배열, 2. 왼쪽 부분 배열 3. 오른쪽 부분 배열
	//세가지중 가장 큰 값을 return 한다.
	return max(ret, max(maxSize(start, mid), maxSize(mid + 1, end)));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; ++i)cin >> a[i];
	cout << maxSize(0, n - 1);
}

Express.js란?

Express.js는 Node.js의 핵심 모듈인 http와 Connect 컴포넌트를 기반으로 하는 웹 프레임워크이다. Express를 사용하면 코드의 복잡성을 낮춰주고 웹애플리케이션 구현 과정의 공통적으로 요구되는 일을 대신 지원해주면서 보다 쉽게 애플리케이션을 구현할 수 있다.

Hello world 예제 구현

다음과 같은 과정을 통해 간단한 Express 앱을 작성할 수 있다.

전제조건 : Node.js 설치

* 설치확인(node.js 버전확인) : node -v 

1. 디렉토리 생성

mkdir sample

cd sample

2. 해당 디렉토리에서 npm init (npm 설치)

 npm init

3. 해당 디렉토리에 Express 설치

npm install express --save

node-modules : 라이브러리 파일 모음

4. 해당 디렉토리에 백엔드 시작점이 될 index.js 파일 작성

index.js

const express = require('express')
const app = express()
const port = 5000

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

app.listen(port, () => {
  console.log(`Example app listening at http://localhost:${port}`)
})

package.json

{
  "name": "practice",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
   "scripts": {
    "start": "node index.js",
    "test": "echo \"Error: no test specified\" && exit 1"
  },
  "author": "",
  "license": "ISC",
  "dependencies": {
    "express": "^4.17.1"
  }
}

package.json 에서 index.js를 시작스크립트로 지정

5. start 스크립트(index.js)를 시작으로 실행

npm run start

앱은 서버를 시작하며 지정한 5000번 포트에서 연결을 청취하며 라우트에 대한 요청에 Hello World! 로 응답한다.

다른 경로에 대해서는 404 Not Found 로 응답한다.

6.  http://localhost:5000/

브라우저에서 로컬호스트를 로드하여 결과물을 확인한다.

React.js란? 

 리액트는 자바스크립트 라이브러리 중 하나로 사용자 인터페이스(UI)를 만들기 위해 사용된다. 

페이스북에 의해 2013년도에 발표되었으며 프런트엔드 부분에서 Vu.js, Angular 와 함께 가장 있기 있는 라이브러리 중하나이다. 이러한 라이브러리들은 DOM관리, 상태값 업데이트 관리를 최소화하고, 개발자가 사용자 인터페이스를 구현하는 것에 집중 할 수 있도록 많은 기능들을 제공한다.

그 중 React 는컴포넌트 개념에 가장 집중 되어 있는 라이브러리이며 매우 넓은 생태계를 보유하고 있다. 또한 다음과 같은 특징을 가지고 있다.

React의 특징

1. 선언형

 - 리액트는 선언형 성격에 따라 컴포넌트를 얻기 위해 jsx문법을 통해 구현된다. 즉, jsx를 얻기 위한 알고리즘에 대한 구현을 하지 않는다. 리액트를 사용할 때 화면 설계라는 초점에 맞춰 개발할 수 있도록 해주기 때문에, 높은 생산성을 보장해 준다.

2. 컴포넌트 기반

- 컴포넌트는 독립적인 단위의 소프트웨어 모듈을 말한다. 리액트는 웹에서 쓰는 각각의 요소들을 컴포넌트로 만들어 기존의 UI를 다른 화면에서 재사용 하거나 다른 프로젝트에서 재사용 할 수 있는 장점을 가진다.

3. Virtual DOM 기반

- Real DOM VS Virtual DOM  : Real DOM을 사용할 경우 만약 10개의 리스트가 있다고 가정할 때 한가지의 리스트만 update 되더라도 전체 리스트를 다시 Reload 해야 하므로 작업이 expensive할 수 있다. 하지만 Virtual DOM을 사용할 경우 처음 상태를 저장해 놓은 Snap shot과 수정된 리스트만을 비교하여 이 부분만 DOM에서 바꿔줄 수 있다.

4. State와 Props

- 리액트는 내부적으로 State와 Props를 가지는데 ,이는 UI가 Action에 따라 다른 UI나 Action이 필요하기 때문이다.

- Props VS State : props는 컴포넌트간에 어떠한 인터렉션이 있을 때 부모 컴포넌트에서 자식 컴포넌트에 전달한 것은 자식 컴포넌트에서 자체적으로 수정할 수 가없다. 반면 State 는 컴포넌트 내에서 데이터를 교환하거나 전달 할 때 사용할 수 있으며 자체적으로 내부에서 변화를 줄 수 있는 Relandering 성질을 가진다.

node.js란

즉 Chrome 브라우저가 JavaScript 코드를 해석하기 위해 내장하고 있는 JavaScirpt Engine인 V8 엔진을 이용하여 브라우저에서 JavaScript를 해석하듯이 JavaScript를 동작할 수 있도록 하는 환경이다.

Node.js 관련 핵심키워드

- 크롬 V8

 크롬 V8 또는 간단히 V8은 웹 브라우저를 만드는 데 기반을 제공하는 오픈 소스 자바스크립트 엔진이다. 구글 크롬 브라우저와 안드로이드 브라우저에 탑재되어 있다.

- 비동기 I/O처리(Non-Blocking I/O)

하나의 쓰레드가 request를 받으면 바로 다음 처리에 요청을 보내놓고 다른 작업을 처리하다가 먼저 요청한 작업이 끝나면 이벤트를 받아서 응답을 보낸다.

동시 request가 오더라도 처리가 완료될때까지 기다리지 않아도 되기 때문에 서버 부하가 적다.

- NPM

npm (노드 패키지 매니저/Node Package Manager)은 자바스크립트 프로그래밍 언어를 위한 패키지 관리자이다. 자바스크립트 런타임 환경 Node.js의 기본 패키지 관리자이다. 명령 줄 클라이언트(npm), 그리고 공개 패키지와 지불 방식의 개인 패키지의 온라인 데이터베이스(npm 레지스트리)로 이루어져 있다.

www.acmicpc.net/problem/1074

문제 해결

• 이전에 해결하였던 쿼드트리 문제와 동일하게 각각의 problem을 4개의 subProblem으로 나누어 해결하였다.
• 하지만 이 문제는 최대 2의 15승까지의 입력 값을 받기 때문에 크기 1의 subProblem를 모두 찾아서 위치를 비교하여 문제를 해결할 경우 시간초과가 난다.
• 그렇기 때문에 subProblem으로 들어왔을 때 만약 주어진 (r,c)가 현재 subProblem의 범위에 포함되어 있지 않은 경우에는 현재 subProblem에 포함되어 있는 개수 h* h를 출력값 answer에 더해주고 return 시켜서 더이상 현재 subProblem이 분할하여 재귀에 들어가지 않도록 하였다.
• 문제 해결순서는 현재 문제에서 주어진 Z 와 같은 이동 순서를 가지므로 최종 출력값이 마지막에 문제에 대한 답을 찾기 전까지의 모든 최하위 subProblem의 갯수와 동일하므로 문제가 발생하지 않는다.
• 최종적으로 주어진 c와 r에 해당하는 subProblem에서 현재 answer값의 출력하고 return하여 이후 과정에서 출력 값이 변화하는 것에 대한 문제를 해결하였다.

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> check;
int N, r, c;
int answer = 0;

void solution(int h, int x, int y)
{
	//입력값으로 주어진 r과 c에 해당하는 subProblem에서 출력
	if (x == r && y == c){
		cout << answer << endl;
		return;
	}
	//c와 r이 현재 subProblem의 범위 내에 포함되지 않는 경우
	//현재 subProblem의 크기만큼 answer에 더해주고 return하여
	//더이상 재귀를 진행하지 않는다.
	if (r > x + h - 1 || c > y + h - 1 || r < x || c < y){
		answer += h * h;
		return;
	}

	solution(h / 2, x, y);
	solution(h / 2, x, y + (h / 2));
	solution(h / 2, x + (h / 2), y);
	solution(h / 2, x + (h / 2), y + (h / 2));
}

int main() {

	cin >> N >> r >> c;
	solution(pow(2, N), 0, 0);
	return 0;
}

결과

www.acmicpc.net/problem/1992

문제 해결

문제의 예제와 아래에 있는 입력과 출력 예제를 보고 나서 문제의 내용을 이해할 수 있었다.

• 입력에 따른 출력형식은 problem을 4개의 subProblem으로 나누고 크기가 1인 가장 하위 subProblem까지 갔을 때 부터 결정되기 시작한다.
• 상위 subProblem의 출력형식은 하위 4개의 subProblem이 통일되어 있는지, 다른지에 따라서 결정되기 때문이다.
• 입력은 항상 2의 제곱수로 이루어지기 때문에 1, 4, 8, 16... 등 크기가 1인 가장 하위 subProblem에서 return한다고 하였을 때 모든 입력을 4개의 subProblem으로 나누어 해결할 수 있다.

반례

0000

0101

0000

0101

다음과 같은 입력의 경우에는 4개의 subProblem의 return값이 모두 같아서

(0001) 로 출력이 되는 문제가 발생하였는데 문제의 조건에 따르면

((0001)(0001)(0001)(0001)) 이렇게 출력이 되어야 문제가 해결된다.

이를 해결하기 위해

if (compareString(req)&&(req[0]).size()==1)
      return req[0];

다음의 부분을 통하여 각각의 subProblem의 return값이 모두 동일하더라도 size가 1일 때만 하나로 통합되도록 하였다.

코드

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

using namespace std;

#define MAX 65

int N;
int image[MAX][MAX];
string str[MAX];
string answer;

bool compareString(vector<string> str) {
	bool check=true;
	for (int i = 1; i < str.size(); i++) {
		check = str[i - 1].compare(str[i]);
		if (check != 0)
			return false;
	}
	return true;
}

string solution(int h,int x,int y)
{ 
	//h가 1일 때 현재 index를 return
	if (h == 1)
		return to_string(image[x][y]);
	vector<string> req;
	req.push_back(solution(h / 2 ,x, y)); 
	req.push_back(solution(h / 2, x, y+(h / 2)));
	req.push_back(solution(h / 2, x+(h /2) , y));
	req.push_back(solution(h / 2, x+(h / 2), y+(h / 2)));
	
	//abcd가 다 같다면 한 개의 값만 뽑아서 그걸 print하는데 그 때는 ()를 쓰지않음
	//abcd의 값이 다 같은게 아니라면 ()를 쓰고 안에 내용들을 모두 프린트
	if (compareString(req)&&(req[0]).size()==1)
			return req[0];
	else
		return "("+ req[0] + req[1] + req[2] + req[3]+")";
}

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++){
		string s;
		cin >> s;
		for (int j = 0; j < N; j++)
			image[i][j] = s[j] - '0';
	}
	cout << solution(N, 0, 0);
	return 0;
}

결과

기본 개념

분할정복법이란 주어진 문제를 동일 유형의 하위 문제로 나눈뒤 각각의 작은 문제들을 해결하여 정복하는 방식이다.

분할 정복법은 다음과 같이 크게 3단계의 과정을 통해 진행된다. 퀵 정렬, 병합정렬, 큰수곱셈, FFT 등 여러 분야에서 분할정복 알고리즘을 이용하여 문제를 해결하고 있다.

• 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다. _divide

• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. _solve (conquer)

• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다. _combine (merge)

* 장점: 문제를 나누어 해결함으로써 복잡한 문제를 부분적으로 해결하여 병렬형식로 문제를 보다 쉽게 해결한다는 장점이 있다.

* 단점 : 재귀함수를 사용함으로 인해 함수 호출에 의한 오버헤드가 발생

관련문제

쿼드트리 1992번 https://www.acmicpc.net/problem/1992

Z 1074번 https://www.acmicpc.net/problem/1074

부분배열 고르기 2104번 https://www.acmicpc.net/problem/2104

히스토그램 1725번 https://www.acmicpc.net/problem/1725

Greedy Algorithm은 최적해를 구하는 상황에서 사용하는 방법이다.

- 여러 경우 중 최적의 경우의 수를 선택하여 문제를 해결해 나간다.

- 즉, 데이터 간의 관계를 고려하지 않고 수행 과정에서 'greedy(욕심내어)' 데이터를 선택한다.

- 이러한 선택을 '근시안적' 선택이라고도 한다.

- Greedy Algorithm은 방법이 통하는 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다.

- 방법이 통하는 문제들은 다음의 특징을 가진다

  1. 한번의 선택이 다른 선택에 전혀 무관한 값이다.

  2. 매 순간의 최적해가 문제에 대한 최적해이다.

- 순간순간마다 최적의 결정을 함을 통해 전체 문제해결에 대해서 가장 최적의 결과를 얻는 것이 보장되어 있지 않다.

- 어느정도 적합한 수준의 해답을 알려주는 알고리즘이다.

- 계산속도가 정확한 알고리즘에 비해서 실행속도가 빠른 경우가 많아 실용적인 사용이 가능하다.

 Greedy Algorithm을 통해 해결한 문제

[백준 13904] 과제

[백준 4796] 캠핑

[백준 1449] 수리공 항승