문제 : https://www.acmicpc.net/problem/1182


[알고리즘풀이]

백트레킹을 이용해 만들 수 있는 모든 부분수열의 합을 구해본다.

#include<iostream>
#include<vector>

using namespace std;

int n_l[20], answer,n,m;

void bt(int i, int j, vector<int> v) {
	if (v.size() == i) {
		int temp = 0;
		for (int k = 0; k < i; k++){
			temp += v[k];
		}
		if (temp == m) {
			answer++;
		}
		return;
	}
	for (int k = j + 1; k < n; k++){
		v.push_back(n_l[k]);
		bt(i, k, v);
		v.pop_back();
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> n_l[i];
	for (int i = 1; i <= n; i++) {
		// i개 씩 뽑을거다.
		for (int j = 0; j < n + 1 - i; j++) {
			// j까지담김
			vector<int> v;
			v.push_back(n_l[j]);
			bt(i, j, v);
			v.pop_back();
		}
	}
	cout << answer;
}

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 2580 - 스도쿠  (0) 2019.09.21
[BOJ] 2981 - GRANICA  (0) 2019.09.21
[BOJ] 1788 - 피보나치 수의 확장  (0) 2019.09.20
[BOJ] 17298 - 오큰수  (0) 2019.09.20
[BOJ] 1874 - 스택 수열  (0) 2019.09.20

문제 : https://www.acmicpc.net/problem/1788


[알고리즘풀이]

음수 N의 피보나치 값 F(N) = F(N + 2) - F(N + 1) 을 통해 구할 수 있고,

양수 N의 피보나치 값 F(N) = F(N - 1) + F(N - 2) 를 통해 구할 수 있습니다.

#include<iostream>

using namespace std;

#define j 1000000
#define m 1000000000
int f[2000001];

int abs(int n) {
	if (n < 0)
		return -n;
	return n;
}
int main(void) {
	f[j + 0] = 0, f[j + 1] = 1;

	int n;
	cin >> n;
	if (n >= 2) {
		for (int i = 2; i <= n; i++)
			f[i + j] = (f[i - 1 + j] + f[i - 2 + j]) % m;
	}
	else if (n < 0) {
		for (int i = -1; i >= n; i--)
			f[i + j] = (f[i + 2 + j] - f[i + 1 + j]) % m;
	}
	if (f[n + j] < 0) {
		cout << "-1\n" << abs(f[n + j]);
	}
	else if (f[n + j] > 0) {
		cout << "1\n" << abs(f[n + j]);
	}
	else
		cout << "0\n" << abs(f[n + j]);
}

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 2981 - GRANICA  (0) 2019.09.21
[BOJ] 1182 - 부분수열의 합  (0) 2019.09.20
[BOJ] 17298 - 오큰수  (0) 2019.09.20
[BOJ] 1874 - 스택 수열  (0) 2019.09.20
[BOJ] 4949 - The Balance of the World  (0) 2019.09.19

문제 : https://www.acmicpc.net/problem/17298


[알고리즘풀이]

스택을 어떻게 활용해야될지 감이 오지 않아, 친구의 도움으로 해결할 수 있었습니다.

 

* 입력의 역순으로 순회하며 알고리즘을 진행합니다. *

1. 현재 값이 Stack의 Top보다 작다면 Stack의 Top이 NGE 값이 된다.

2. 현재 값이 Stack의 Top보다 크거나 같다면 Stack을 Pop하고 다시 1번부터 진행.

3. 현재 Stack이 비어있다면, 현재 값의 NGE 값은 -1이 됩니다.

4. 1,2,3번이 실행되고나면 Stack에 Push 해줍니다.

ex)
#include<iostream>
#include<stack>

using namespace std;

int a[1000000];
int l[1000000];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	stack<int> s;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> l[i];

	for (int i = n - 1; i >= 0; i--) {
		while ( !s.empty() && s.top() <= l[i])
			s.pop();

		if (s.empty())
			a[i] = -1;
		else
			a[i] = s.top();

		s.push(l[i]);
	}

	for (int i = 0; i < n; i++)
		cout << a[i] << ' ';
}

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 1182 - 부분수열의 합  (0) 2019.09.20
[BOJ] 1788 - 피보나치 수의 확장  (0) 2019.09.20
[BOJ] 1874 - 스택 수열  (0) 2019.09.20
[BOJ] 4949 - The Balance of the World  (0) 2019.09.19
[BOJ] 9012 - Parenthesis  (0) 2019.09.19

안녕하세요, 여행벌입니다.

오늘은 Pytorch 기본 연산들에 대해서 배워보도록 하겠습니다.

Pytorch library를 설치하지 못하신 분은 아래 포스팅을 먼저 읽어주세요!

https://travelbeeee.tistory.com/75

이 포스팅을 읽으시는 분들이 Pytorch 라이브러리를 이용해서

손쉽게 딥러닝을 구현할 수 있도록 최대한 세세하게 포스팅을 해보도록 하겠습니다!


1. Tensor 기본 연산 명령어

파이토치는 데이터를 추상화하는 Tensor와 Variable을 제공합니다.

그중 Tensor는 numpy 배열과 유사해서 유용하게 사용할 수 있습니다.

Tensor와 Variable 타입 모두 GPU에서 동작해 'GPU의 빠른 연산력을 사용할 수 있다.'는 장점이 있다고 합니다!

그러면 여러 함수들을 익혀볼까요?

● torch.Tensor() : tensor 배열을 생성한다. numpy 배열을 input으로 받으면 tensor 배열로 변환해준다.

● torch.randn() : 평균 0, 분산 1인 정규 분포를 따라서 tensor 배열을 생성한다.

● torch.add(x,y) : tensor 배열 x, y를 더해준다.

● torch.add(x, y, out = result) : tensor 배열 x, y를 더해 result tensor 배열에 저장한다.

● y.add(x) : tensor 배열 y 에 x를 더한 값을 y에 in_place 하게 저장한다.

● x + y : numpy 배열처럼 tensor 배열 x, y를 더한다.

● x - y : numpy 배열처럼 tensor 배열 x, y를 뺀다.

● x * y : numpy 배열처럼 tensor 배열 x, y를 행렬 곱을 한다.

● .size() : tensor 배열의 크기를 알려준다.

import numpy as np
import torch
# 1번 코드
x = torch.Tensor(5,3) # 5 x 3 tensor 배열을 만든다.
print(x)
# 2번 코드
y = np.random.rand(5,3) # 5 x 3 numpy 배열을 만든다.
print(y)
# 3번 코드 중요!
z = torch.Tensor(y) # numpy 배열 y를 tensor 배열로 바꿔 저장한다.
print(z)
print(type(z))

먼저 numpy 와 torch library를 import 하겠습니다. 1번 코드를 보시면, numpy 배열과 비슷하게 tensor 배열을 만들 수 있습니다. 위에서 tensor 타입은 numpy와 비슷하다고 했는데, 3번 코드를 보시면 numpy 배열인

y를 tensor 배열로 쉽게 변환할 수 있는 것을 확인할 수 있습니다.

출력 :
tensor([[0.0000, 0.0000, 0.0000],
        [0.0000, 0.0000, 0.0000],
        [0.0000, 0.0000, 0.0000],
        [0.0000, 0.0000, 0.0000],
        [0.0000, 0.0000, 0.0000]])
[[0.67086163 0.55784783 0.62186057]
 [0.99621408 0.86104033 0.17540402]
 [0.22081897 0.53235119 0.6920162 ]
 [0.02901596 0.3410925  0.69009763]
 [0.62706006 0.16814722 0.5602715 ]]
tensor([[0.6709, 0.5578, 0.6219],
        [0.9962, 0.8610, 0.1754],
        [0.2208, 0.5324, 0.6920],
        [0.0290, 0.3411, 0.6901],
        [0.6271, 0.1681, 0.5603]])
<class 'torch.Tensor'>

z에 numpy 배열이 tensor 배열로 바뀐 후 저장된 것을 확인할 수 있습니다.

import torch
x = torch.rand(5,3)
print(x)
y = torch.rand(5,3)
print(y)
print(x+y)
print(torch.add(x,y))
result = torch.Tensor(5,3) # 결과를 담아줄 배열을 만든다.
torch.add(x,y, out = result)
print(result)

다음으로는 여러 가지 덧셈 문법에 대해서 알아보도록 하겠습니다.

numpy 배열처럼 직접 x + y를 할 수도 있고, torch.add 함수를 이용할 수도 있습니다.

torch.add 함수는 특이하게 결과값을 out을 통해 변수에 저장할 수도 있습니다.

출력 :
# print(x)
tensor([[0.1405, 0.4824, 0.5622],
        [0.4702, 0.0449, 0.5176],
        [0.8134, 0.2111, 0.0923],
        [0.9565, 0.9365, 0.7615],
        [0.1268, 0.6055, 0.6063]])
# print(y)
tensor([[0.8514, 0.3682, 0.6901],
        [0.9142, 0.6101, 0.8050],
        [0.0158, 0.1671, 0.3655],
        [0.9922, 0.4498, 0.1291],
        [0.3218, 0.4852, 0.7165]])
# print(x+y)
tensor([[0.9919, 0.8506, 1.2523],
        [1.3843, 0.6550, 1.3226],
        [0.8291, 0.3782, 0.4578],
        [1.9488, 1.3863, 0.8907],
        [0.4486, 1.0906, 1.3228]])
# print(tensor.add(x,y))
tensor([[0.9919, 0.8506, 1.2523],
        [1.3843, 0.6550, 1.3226],
        [0.8291, 0.3782, 0.4578],
        [1.9488, 1.3863, 0.8907],
        [0.4486, 1.0906, 1.3228]])
# print(result)
tensor([[0.9919, 0.8506, 1.2523],
        [1.3843, 0.6550, 1.3226],
        [0.8291, 0.3782, 0.4578],
        [1.9488, 1.3863, 0.8907],
        [0.4486, 1.0906, 1.3228]])

또, 다음과 같이 in_place하게 덧셈을 진행할 수도 있습니다.

y.add(x) #  y 배열에 x 배열을 더해서 y 배열에 다시 저장.
print(y)
출력 :
# print(y)
tensor([[0.9919, 0.8506, 1.2523],
        [1.3843, 0.6550, 1.3226],
        [0.8291, 0.3782, 0.4578],
        [1.9488, 1.3863, 0.8907],
        [0.4486, 1.0906, 1.3228]])

배열의 크기를 알아볼 수도 있습니다.

print(x.size())
print(y.size())
출력 :
torch.Size([5, 3])
torch.Size([5, 3])

오늘은 여기까지만 다뤄보고,

다음 포스팅 때 다른 명령어들을 알아보겠습니다!

+ Recent posts