DP 문제로 DP[N] : 2 x N 타일링하는 경우의 수라고 한다면, 2 x N 타일링은 2 x (N - 1) 타일링 방법에 세로 한 줄을 추가하는 경우의 수와 2 X (N - 2) 타일링 방법에 가로 두 줄을 추가하는 경우의 수의 합으로 다음과 같은 점화식이 성립합니다.
■ DP[N] = DP[N - 1] + DP[N - 2]
이때, 여러개의 테스트 케이스에 대해서 2 x N 타일링하는 경우의 수를 출력하는 게 아니라 단 한 번만 출력하면 되므로 굳이 배열을 선언해 메모리를 낭비하지 않고 2 x N 타일링하는 경우의 수를 앞에서부터 차곡차곡 쌓아가면 됩니다.
#include <string>
#include <vector>
#define M 1000000007
using namespace std;
int solution(int n) {
int answer = 0, left = 0, right =1, temp;
for(int i = 2; i <= n; i++){
temp = (left + right) % M;
left = right;
right = temp;
}
answer = (left + right) % M;
return answer;
}
관계 연산자는 두 개의 피연산자 사이에서 크기 및 동등 관계를 따져주는 이항 연산자로 결과에 따라서 true 또는 false를 반환합니다.
연산자
연산자의 기능
결합 방향
<
a < b
a 가 b 보다 작은가?
→
>
a > b
a 가 b 보다 큰가?
→
<=
a <= b
a 가 b 보다 작거나 같은가
→
>=
a >= b
a 가 b 보다 크거나 같은가
→
==
a == b
a 가 b 랑 같은가?
→
!=
a != b
a 가 b랑 다른가?
→
논리 연산자 : &&, ||, !
연산자
연산자의 기능
결합 방향
&&
A && B
A와 B 모두가 true이면 true, 아니면 false ( 논리 AND 와 동일 )
→
||
A || B
A와 B 모두가 false이면 false, 아니면 true ( 논리 OR 과 동일 )
→
!
!A
A가 true이면 false, false이면 true 반환 ( 논리 NOT )
→
예시 1)
package Hello;
public class HelloWorld {
public static void main(String args[]) {
int num1 = 0;
int num2 = 0;
boolean result;
result = ((num1 += 10) < 0) && ((num2 += 10) > 0);
System.out.println(result);
System.out.println(num1);
System.out.println(num2);
}
}
위의 출력 결과는 어떻게 될까요?
false
10
0
num1은 10이지만, num2는 0인 것을 확인할 수 있습니다. 그 이유는 && 연산자 때문입니다. ( (num1 += 10) < 0 ) 이 먼저 수행되는데, num1 += 10을 하면 num1은 10이 되므로 0보다 작지 않습니다. 따라서 ( (num1 += 10) < 0 ) 은 false가 됩니다. 이때, && 연산자는 false가 하나라도 존재하면 어차피 false 값을 같습니다. 따라서 ( (num2 += 10) > 0) 연산을 진행하지 않고 result 에는 false가 저장됩니다.
예시 2)
package Hello;
public class HelloWorld {
public static void main(String args[]) {
int a = 5; // 코드 1번
System.out.println(a++); // 코드 2번
System.out.println(a); // 코드 3번
System.out.println((a++ + 5) * 3); // 코드 4번
a = (a++ + 5) * 3; // 코드 5번
System.out.println(a); // 코드 6번
}
}
위의 코드는 어떤 값들을 출력할까요? 정답은 아래와 같습니다!
5
6
33
36
코드 1번에서 a 에 5를 할당합니다.
코드 2번에서는 a를 출력한 후, ++ 연산이 진행되므로 '5'를 출력하지만 a의 값은 6이 됩니다.
코드 3번은 코드 2번에 의해 '6' 을 출력하게 됩니다.
코드 4번에는 ( ) , ++, +, * 4가지 연산이 등장합니다. 우선순위는 ( ), ++, *, + 순으로 괄호 안에 식을 먼저 진행해야 됩니다. 따라서 ++ 과 + 연산이 진행되는데 이때, ++ 연산은 명령을 마무리 한 후에 a의 값을 올려주므로 (6 + 5) 가 진행됩니다. 그 후 * 3을 해서 33이라는 값이 만들어지고 a는 1 증가해서 7이 됩니다.
코드 5번은 ( ), ++, +, * , = 5가지 연산이 등장합니다. 우선순위는 ( ), ++, *, +, = 순으로 코드 4번과 마찬가지로 괄호 안에 식을 먼저 진행해야됩니다. 따라서 (7 + 5) 가 먼저 계산되고, 12 * 3이 계산되고 ++ 연산에 의해 a는 1 증가해서 8이 됩니다. 하지만 = 연산에 의해 계산된 36이란 값이 a에 저장되므로 a는 결국 36이 저장됩니다.
예시 3)
package Hello;
public class HelloWorld {
public static void main(String args[]) {
int a = 1; // 코드1
a = ~a; // 코드2
System.out.println(a); // 코드3
}
}
위의 예시는 어떤 값을 출력할까요?
-2
정답은 '-2' 입니다.
컴퓨터는 모든 숫자를 2진수로 저장합니다. 우리는 앞의 포스팅에서 int 는 4바이트로 이루어져 있다고 배웠습니다. 따라서, a에 1을 할당하면 다음과 같이 컴퓨터에는 저장됩니다.
a = 0000 0000 0000 0000 0000 0000 0000 0001 (2)
~ 연산은 쉽게 말하면 2진수로 저장된 a의 비트들을 반대로 바꿔주는 연산입니다. 즉, 코드2에 의해 a는 다음과 같이 바뀝니다.
a = 1111 1111 1111 1111 1111 1111 1111 1110 (2)
컴퓨터가 정수는 저장하는 방법인 2의 보수법에 의하면 위의 2진수 코드는 '-2' 를 의미합니다. 따라서 -2가 출력됩니다.
예시 4) 비트 연산자
<< 연산자는 비트 값들을 왼쪽으로 이동시킨 후에 오른쪽의 빈 공간에는 모두 0으로 채운다.
>> 연산자는 비트 값들을 오른쪽으로 이동시킨 후에 왼쪽의 빈 공간에 양수라면 0으로, 음수라면 1로 채워줍니다.
>>> 연산자는 비트 값들을 오른쪽으로 이동시킨 후에 부호와 상관없이 0으로 채워줍니다.
package Hello;
public class HelloWorld {
public static void main(String args[]) {
int a = 1; // 코드1
a = a << 5; // 코드2
System.out.println(a);
a = a >> 3; // 코드3
System.out.println(a);
int b = -2147483648; // 코드4
b = b >> 1; // 코드5
System.out.println(b);
int c = -2147483648; // 코드6
c = c >>> 1; // 코드7
System.out.println(c);
}
}
위의 예시는 어떤 값들을 출력할까요?
32
4
-1073741824
1073741824
코드1에서 a에 1을 할당하므로 a = 0000 0000 0000 0000 0000 0000 0000 0001 (2) 가 됩니다.
코드2에 의해 a는 왼쪽으로 5칸씩 비트가 이동하게 되고, 오른쪽의 파란 부분에는 0이 채워지고 위의 노란 부분에 해당하는 비트들은 사라지게 됩니다.
a = 0000 0000 0000 0000 0000 0000 0010 0000 (2)
따라서, 현재 a는 10진법으로 32를 나타냅니다.
코드3에 의해 a는 오른쪽으로 3칸씩 비트가 이동하게 되고, 양수이므로 왼쪽의 빨간 부분에 0이 채워지게 됩니다.
a =0000 0000 0000 0000 0000 0000 0000 0100 (2)
따라서, 현재 a는 10진법으로 4를 나타냅니다.
코드4에서 b에 -2147483648 을 할당하므로 b = 1000 0000 0000 0000 0000 0000 0000 0000(2) 가 됩니다.
코드5에서 >> 연산은 음수 값은 왼쪽의 비는 부분을 1로 채우므로 b = 1100 0000 0000 0000 0000 0000 0000 0000(2) 가 되고, 10진수로 표현하면 -1073741824 가 됩니다.
코드6에서 c = 1000 0000 0000 0000 0000 0000 0000 0000(2) 가 됩니다.
코드7에서 >>> 연산은 부호에 상관 없이 왼쪽의 비는 부분을 0으로 채우므로 c = 0100 0000 0000 0000 0000 0000 0000 0000(2) 가 됩니다. 부호를 나타내는 맨 앞 코드가 0이 되어서 c는 양수가 되고 10진수로 표현하면 1073741824가 됩니다.
현재 input[x] 가 k 라면 아직 사용 안 한 값 중에서 (k + 1) 번째로 큰 값을 선택합니다. 그러면, 역순으로 채우고 있기 때문에 input[x] 보다 값이 크면서 index는 작은 값들이 k 개가 됩니다. 이때, 아직 사용 안 한 값 중에서 (k + 1)번 째로 큰 값이 없다면 불가능한 경우이므로 "NIE"를 출력합니다.
ex) input = [ 0 0 1 0 2 0 4 ]
input 배열을 역으로 순회하며 정답 배열을 채워보자.
1) input[7] = 4 / check = [ 0 0 0 0 0 0 0 ]
check 배열을 순회하며 아직 사용 안 한 값 중에서 5번 째로 큰 값을 선택한다.
→ ans[7] = 3
2) input[6] = 0 / check = [ 0 0 1 0 0 0 0 ]
→ ans[6] = 7
3) input[5] = 2 / check = [ 0 0 1 0 0 0 1 ]
→ ans[5] = 4
4) input[4] = 0 / check = [ 0 0 1 1 0 0 1 ]
→ ans[4] = 6
5) input[3] = 1 / check = [ 0 0 1 1 0 1 1 ]
→ ans[3] = 2
6) input[2] = 0 / check = [ 0 1 1 1 0 1 1 ]
→ ans[2] = 5
7) input[1] = 0 / check = [ 0 1 1 1 1 1 1 ]
→ ans[1] = 1
#include<iostream>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, input[30001] = {}, ans[30001] = {};
bool check[30001] = {};
cin >> N;
for (int i = 1; i <= N; i++)
cin >> input[i];
bool flag = false;
for (int i = N; i >= 1; i--) {
int c = 0, j = N;
while (!(c == input[i] && !check[j])) {
if (!check[j])
c++;
j--;
}
if (j < 1) {
flag = true;
break;
}
ans[i] = j;
check[j] = 1;
}
if (flag)
cout << "NIE\n";
else{
for (int i = 1; i <= N; i++)
cout << ans[i] << '\n';
}
}
세그트리를 이용해서 푸신 분들이 많은데, 코드를 뜯어보고 추후에 다시 포스팅하도록 하겠습니다.
오늘은 JAVA의 자동 형 변환(Implicit Conversion) 과 명시적 형 변환(Explicit Conversion) 에 대해서 다뤄보겠습니다.
자료형의 변환
연산을 진행할 때, 컴파일러는 변수가 자료형이 동일할 것을 기대합니다. 하지만, 다음과 같이 서로 다른 자료형에 대해서 덧셈 연산을 진행한다면 어떻게 될까요?
int num = 5;
long num2 = 10L;
// num + num2 ??
int 형 변수 num과 long 형 변수 num2 에 대해서 덧셈 연산을 진행한다면 데이터를 다루는 범위가 더 큰 long 형으로 자료형을 통일해줘야 데이터의 손실 없이 연산이 가능할 것입니다.
- num에 저장된 값을 long 형으로 변환하여 메모리에 임시 저장한다.
- 변환된 값과 num2에 저장된 값을 대상으로 덧셈을 진행한다.
따라서, 위의 두 과정이 진행되야만 우리가 원하는 결과를 얻을 수 있을 것입니다.
이러한 과정을 '자료형 변환' 또는 '형 변환' 이라고 합니다.
자동 형 변환(Implicit Conversion)
프로그래머가 명시한 형 변환이 아니고 필요한 상황에서 규칙에 근거하여 자동으로 일어나는 형 변환을 '자동 형 변환' 이라고 합니다.
- 자료형의 크기가 큰 방향으로 형 변환이 일어난다.
- 자료형의 크기에 상관없이 정수 자료형보다 실수 자료형을 우선시한다.
위의 두 규칙에 근거하여 자바에서는 자동 형 변환이 발생합니다.
예시를 통해서 조금만 익혀보겠습니다.
int num1 = 50;
long num2 = 9999999999L;
System.out.println(num1 + num2); // num1을 long 형으로 자동 형 변환 후 연산 진행
자동 형 변환에 의해 에러 없이 다음과 같이 결과가 나옵니다.
[console]
10000000049
이번에는 정수형과 실수형을 같이 연산해보겠습니다.
package Hello;
public class HelloWorld {
public static void main(String args[]) {
int num1 = 50;
float num2 = 3.04f;
System.out.println(num1 + num2); // num1을 long 형으로 자동 형 변환 후 연산 진행
}
}
[console]
53.04
에러 없이 결과가 나오는 것을 확인할 수 있습니다.
명시적 형 변환(Explicit Conversion)
자동 형 변환이 진행되지 않는 상황에서도 필요하다면 프로그래머가 '명시적 형 변환' 을 통해서 강제로 형 변환이 이뤄지도록 할 수 있습니다.
double num1 = 3.1415;
int num2 = (int)num1; // num1을 강제로 형 변환 -> num2 = 3
다음과 같이 변수 앞에 (우리가 원하는 자료형) 을 통해 강제로 형 변환을 진행할 수 있습니다. 위의 예시는 double 형을 int 형으로 강제로 형 변환했으므로 소수점 이하의 값들은 날아가고 num2 에는 3만 저장됩니다.
short num1 = 3;
short num2 = 5;
short result = num1 + num2;
short 형 num1과 num2를 연산해서 같은 자료형 result에 저장했습니다. 위의 코드는 문제가 없을까요??
문제가 있습니다!! '자바에서 정수형 연산은 int 형으로 진행한다.' 때문에 num1 + num2의 결과는 int 형입니다. 따라서 다음과 같이 강제로 형 변환을 해야만 에러가 발생하지 않습니다.
package Hello;
public class HelloWorld {
public static void main(String args[]) {
short num1 = 3;
short num2 = 5;
short result = (short)(num1 + num2);
}
}
