코딩무식자 전공생

문제출처: https://www.acmicpc.net/problem/2399

문제

수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오.

즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다.

입력

첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

이 문제로 효율적인 시간복잡도를 갖는 알고리즘의 설계의 중요성을 알 수 있습니다. 이 문제를 각각 O(n^2), 0(n^2/2), O(nlogn)으로 풀 수 있는데 엄밀히말해서 입력값이 1만이므로 최악의 경우 1억번의 연산을 해야하므로 O(nlogn)으로 풀어야만합니다. 하지만 이 문제는 O(n^2)의 연산풀이도 정답이되는것 같습니다.

O(n^2) : 입력한 수들을 모두 각각 비교하면서 총합을 구합니다. 쓸모없는 연산을 하는 단점이있습니다.(1,2,3,4,5일때 (1.1),(2,2),(3,3),(4,4),(5,5) )

O(n^2/2) : O(n^2)의 방식에서 언급한 쓸모없는연산(본인과 본인사이의 거리)을 하지않고 , 두번더하는연산((1,2),(2,1),(4,5),(5,4)...)을 한번으로줄입니다. 구해진 ans*2가 답입니다. 

O(n^2)의 방식은 n이 5일때 총 5*5=25번연산, O(n^2/2)의 방식은 입력값끼리 한번씩만 연산하므로(O(n^2)의 절반만 계산) 약 O(n^2/2)입니다.

그런데 시간복잡도 상 O(n^2)와 O(n^2/2)는 둘다 O(n^2)로, 여전히 시간초과가 날 우려가 있습니다.

더 좋은방법은 없을까요? 바로 O(nlogn)방법이있습니다. 

10,1,3,7 이있다고칠때, 가장 작은값부터 오름차순으로 좌표값의차이를 비교해가며  연산을 하기위해 1,3,7,10으로 정렬합니다.

(정렬하지않으면 연산식을 같게해도 답이다릅니다. ex) 10,3,1,7-> 94, 1,7,10,3-> 102

사실상 정렬하지않고 연산한 방식을 

여기서, 규칙을 발견할 수 있습니다. 1과 3의 간격 2, 1과 7 의 간격 6, 1과 10의 간격 9, 3과 7의 간격 4, 3과 10의간격 7, 7과 10의 간격3, 이값들을 모두더하고 *2를하면 그게답입니다. 즉,  1,3,7,10일 때 1에서 모든숫자간의 간격 + 3에서 남은 모든숫자의간격(1제외)+ 7과 남은 모든숫자의간격을 구하는겁니다.

여기서 O(n^2/2)와 O(nlogn)의 연산의 차이는 후자의 경우 각 숫자의 간격을 단 한번만 구하고 그 값이 간격을 계산할 때 나오는 경우만큼 곱해주는것입니다.

전자의 경우 10,1,3,7 일때 (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)의 간격을구하죠. 그러나 후자는 3->3->1번씩 구하는게아니라 1->1->1번씩구하고 그 간격의 값들을 곱해주고 더해나갑니다. 위의 예로는 (1.2),(2,3),(3,4) 이렇게 딱 3번만연산합니다. 반복문으로 구해지는 i번째의 인덱스일때 간격 6=(1,3)+(3,7), 16=(1,10)+(3,10), 9=(1,7)+(7,10))

결론적으로 n이4일때 각 시간복잡도의 연산횟수는 16, 6, 3 이렇게되겠습니다.

코드

0~21행: O(nlogn), 38행(n^2/2), 37행(n^2)

#pragma warning(disable:4996)
#include<iostream>
#include<algorithm>
using namespace std;
int arr[10001];
int main()
{
	int n;
	scanf("%d", &n);
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	sort(arr, arr + n);
	for (int i = 1; i < n; i++)
	{
		ans += (arr[i] - arr[i - 1]) * i * (n - i);
	}
	printf("%lld\n", ans * 2);
}

//#include<iostream>
//using namespace std;
//int arr[10001];
//int main()
//{
//	int n;
//	cin >> n;
//	long long ans = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> arr[i];
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = i + 1; j <= n; j++)
//		for(int j=1;j<=n;j++)///////
//		{
//			ans += abs(arr[i] - arr[j]);
//		}
//	}
//	cout << ans * 2 << endl;
//}

결과

문제출처: https://www.acmicpc.net/problem/1964

문제

오각형의 각 변에 아래 그림과 같이 점을 찍어 나간다. N단계에서 점의 개수는 모두 몇 개일까?

입력

첫째 줄에 N(1≤N≤10,000,000)이 주어진다.

출력

첫째 줄에 N단계에서 점의 개수를 45678로 나눈 나머지를 출력한다.

풀이 

규칙찾기문제입니다. 규칙을 찾아볼까요? 1단계는 5, 2단계는 12, 3단계는 22, 4단계는 35...... 여기서 각 단계는 전 단계 + @이므로 식을 다시 써보면,

1단계->5, 2단계-> 5+7, 3단계->5+7+10, 4단계->5+7+10+13.... 규칙이보이사나요? 맞습니다. 2단계부터 7을 시작으로 3씩 증가하는 등차수열입니다.

식을 그대로 코드로 작성하면됩니다. 주의할건 입력의범위가 크므로 ans를 longlong으로 선언해주는겁니다. 

그리고 dp가 메모리를 많이잡아먹는다는것을 보이기위해 아래에 dp로 푼 실행결과도 올렸습니다.

코드

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	long long ans = 5;
	long long num = 7;
	for (int i = 2; i <= n; i++)
	{
		ans += num;
		num += 3;
		ans = ans % 45678;
	}
	cout << ans << endl;
}

결과

dp

반복문

문제출처: https://www.acmicpc.net/problem/1010

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

풀이

n,m의 단위를 작게하여 하나씩 그려보며 규칙을 유도해봤습니다. 일단, 보기에서 n=m=2일때 답은 1가지입니다.

최대한 많이 설치해야하므로 다음과 같은 경우는 잘못된 경우입니다.

n=2, m=4일 때 입니다. 총 6가지입니다.

규칙이 보이시나요? 경우의수는 n<=m일 때만 성립합니다. 그리고 모두 1:1 대응이되어야하죠. 그리고 궁극적으로는 m개중 n개를 순서상관없이 고른 경우의 수 입니다.

즉 mCn이죠. 보기의 예시 모두 mCn을 만족합니다. 그리고 mCn= m-1Cn-1 + m-1Cn을 만족합니다. 코드로 작성하면 끝입니다.

주의할 것은 mCn일 때 m==n이거나 n=0일 때 1을 반환함으로써 재귀함수의 종료문을 작성해야한다는 것입니다.

코드

#include<iostream>
#include<cstring>
using namespace std;
int dp[31][31];
int func(int m, int n);
int main()
{
	int t,n,m;
	cin >> t;
	
	for (int i = 0; i < t; i++)
	{
		cin >> n >> m;
		memset(dp, 0, sizeof(dp));
		cout << func(m, n) << endl;
	}
}
int func(int m, int n)
{
	if (m == n || n == 0)
		return 1;
	if (dp[m][n])return dp[m][n];
	return dp[m][n] = func(m - 1, n - 1) + func(m - 1, n);
}

결과

문제출처: https://www.acmicpc.net/problem/11052

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

풀이

입력받기위해 card[n]을 선언하고 dp[n]을 n개의카드를 구매했을 때 최대비용으로 선언해주고 보기로 주어진 1,5,6,7로 규칙을 찾아봅시다.

dp[1]=card[1]

dp[2]=dp[1]+dp[1] vs card[2]

dp[3]=dp[1]+dp[1]+dp[1] vs dp[1]+dp[2] vs card[3]

..

이 규칙에서 dp[n]을 구할 때 n번 연산을 하는게 보이나요? 그리고 작성한 규칙을 다음과 같이 바꿀 수 있습니다.

dp[1]= card[1]

dp[2]=dp[1]+card[1] vs card[2]

dp[3]=dp[1]+card[2] vs dp[2]+card[1] vs card[3]

dp[n]을 구할때 총 n번 연산하고 dp[n]이 n번씩 값이 바뀌죠.물론 최대비용을 구하는 거니n번의 연산을 max값비교하면됩니다.

dp[3]=max(dp[1]+card[2],dp[2]+card[1] ,card[3])

n범위까지의 dp값을 구하는데 각dp[n]은 또 n번 연산합니다.  이중반복문이겠죠? 여기서부터는 반복문작성입니다.(이게 답입니다.)

코드

#include<iostream>
#include<algorithm>
using namespace std;
int card[1001];
int dp[1001];
//dp[n]: n개의 카드를 살 때의 최대비용저장
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> card[i];

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			dp[i] = max(dp[i], dp[i - j] + card[j]);
		}
	}
	cout << dp[n] << endl;
	
}

결과

중학교, 고등학교 수학시간에 배우고 써먹었던 간단한 공식들이지만 코딩에 적용해야할 때 까먹는 경우가 빈번한 것 같아서 몇가지 수학 공식들을 적어둡니다.(계속 추가 및 수정할 예정입니다.)

의외로 모르면 문제를 못 풀거나 어려움에 처할 수 있는 공식들입니다.

백준사이트의 c++기초문제집을 처음부터 풀다보면 마주칠 수 있는 공식들입니다.

1.  두 수 사이의 합 (합공식)(등차수열일때만.)

1부터 n까지의 합 공식은 n(n+1)/2 입니다.

그러면 5부터7까지(n부터 m까지의합) 합은 7(7+1)/2일까요? 아닙니다.

 n(n+1)/2을 풀어써보면 (수의 갯수) * (끝수+첫번째 수) / 2입니다.

정답률 25%문제풀기

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

결론

n~m까지의 합 : (n부터 m까지의 갯수) * (n+m) / 2 

ex) 5부터7까지의합 : 3*(5+7)/2=18

2. 다각형의 대각선의 갯수

n각형,n>=3일때 n(n-3)/2

3. 삼각형의 조건

세 변 a,b,c 이고 가장 긴 변이 c일때

a+b>c (역으로, 삼각형이 아니려면? a+b<=c)

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

++피타고라스의정리

세 변 a,b,c이고 c가 직각을 바라보는 변 일 때 

4. 등차수열, 등비수열

등차: 숫자간의 간격(차,d), 첫 수: a ,n번째 수 

일반항: a+(n-1)d

등비: 숫자간의 간격(곱,r), 첫 수:a, n번째 수

일반항: ar^(n-1)

5. 원의 위치관계(내접,외접)★★

머리가 좋으시다면 외워놓는게 좋지만 그게아니라면 직접 두 원을 그려보면서 이해하는게 제일 좋습니다.

(r:반지름길이, d: 두 원의 중심사이의 거리)

출처https://mathbang.net/101

원의 위치관계를 이용한 정답률 19퍼센트짜리의 문제입니다. 모르면 못풀고 알면 공식만 작성해서 제출하면됩니다.

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

6. 기울기, y절편 구하기

두 점(x1,y1),(x2,y2)가 주어질 때

기울기: (y2-y1) / (x2-x1)

y절편: 기울기구하고 주어진 좌표 중 아무거나 대입하여 y절편을 구함

7. 조합,순열 ★★★(스택,재귀,dfs, 백트래킹)

조합: nCm = n! / m! = (n-m)! / m! (단 m=0일떄 답 1)

순열 nPm =n! / (n-m)! (단 m=0일때 답1)

조합에서,  mCn = m-1Cn-1 + m-1Cn

이 공식으로 풀 수 있는 dp문제

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

문제출처: https://www.acmicpc.net/problem/3986

문제

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

입력

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 좋은 단어의 수를 출력한다.

풀이

페이지하단의 알고리즘분류의 스택을 힌트로얻어풀었습니다. 아치형 곡선이 교차 할 때와 교차하지 않을 때(정답이 아닐 때)는 아래의 그림과 같습니다.

스택이 비지않고 상단의 문자와 현재 문자가 같을때는 pop시키고, 그 외의 경우에는 삽입하면서 결과적으로 스택이 비어있으면 정답입니다.

 21~24행의 주석부분같은 실수만 조심하면됩니다.(ABBA일 때)

<겹칠 때> 

쌍을 맞추기 위해 단어의 배치를 바꿀 때 아래 경우처럼 무조건 겹침

<겹치지 않을 때>

최초: 안겹침. BB삭제 후 AA일때 안겹침

코드

#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main()
{
	int n;
	cin >> n;
	string s;
	int cnt = 0;
	for(int i=0;i<n;i++)
	{
		//순서가뒤바뀔때 엇갈리면안됨
		
		stack<char>st;
		cin >> s;
		for (int i = 0; i < s.size(); i++)
		{
			//if(st.empty())
			//st.push(s[i]);
			//else if(!st.empty()&&st.top()==s[i])
			//st.pop();
			if (!st.empty() && st.top() == s[i])
				st.pop();
			else
				st.push(s[i]);
		}
		if (st.empty())
			cnt++;
	}
	cout << cnt << endl;
}

결과

문제출처: https://www.acmicpc.net/problem/1912

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

문제의 정답률이 사람들이 얼마나 dp를 어려워하는지를 보여주네요..하지만 정답을 도출하는 과정이 어렵진않습니다. 헷갈릴 순있어도.....

dp[N]은 첫번째 수~N번쨰 수까지의 수 중 연속된 최댓값을 저장합니다. 그렇기 때문에  혹시라도 dp[2],dp[3],d[4]을 10이라고 생각 하셨던 분들은 접근을 잘못 한겁니다.

결과적으로 dp[2]는 10-4=6, dp[3]=9..이런식이므로 이어지므로 dp[i]=max(dp[i-1]+arr[i],arr[i])만 해주시면됩니다. 여태까지의 최대연속합dp[N]이 arr[N]보다 작을 때 arr[N]이 최대값이 된다는것만 주의하면됩니다.(이 때 arr[N]은 0개연속). 그리고 연산하면서 정답을 출력할 변수를 매번 최대값으로 갱신해주면됩니다. 주의: dp[n]은 정답아님(32)

코드

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100001];
int dp[100001];
//index까지 최대합 저장 dp[5]=1~5번째 수 중 최대연속값

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	dp[1] = arr[1];
	int MAX = dp[1];
	//10,-4 .. 일때 dp[2]=10이아님....6임
	//dp[2]=10은 연속하지않음,그러나 10,16일때
	//dp[2]는 16일때 가장 큰 수(0개연속)
	for (int i = 2; i <= n; i++)
	{
		dp[i] = max(arr[i], dp[i - 1] + arr[i]);
		//cout << dp[i] << " ";
		if (dp[i] > MAX)MAX = dp[i];
	}
	cout << MAX << endl;
}

결과

문제출처: https://www.acmicpc.net/problem/2193

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

풀이

dp문제는 규칙을 찾는게 중요합니다. 조건에맞게 규칙을 하나씩 찾아보면 분명 쉽게 답이 나오는 문제도많습니다.

일단 1~90자리의 이친수의 개수를 담을 dp[91]배열을 선언합니다.(dp[5]=5자리 이진수의 이친수갯수 저장)

규칙을 찾아봅시다.(노트에 적어가며) 

1자리이친수: 1(1),  2자리: 1(10),  3자리:2(100,101),  4자리:3(1000,1010,1001).......규칙이보이시나요?

2번쨰 인덱스부터 dp[i]=dp[i-2]+dp[i-1]이성립합니다.! (규칙이 안보이시면 5,6자리까지구해보세요)

주의할건 배열을 int형선언이아닌, long long형으로 선언해야한다는겁니다. 입력값이 최대 90자리이므로,, int형범위로는 택도없습니다. 참고: long long 형범위: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

코드

#include<iostream>
using namespace std;
long long dp[91];
//1~90자리의 수의 이친수의 개수담는배열

int main()
{
	int n;
	cin >> n;
	dp[1] = 1, dp[2] = 1;
	/*dp[3] = 2, dp[4] = 3;
	dp[5] = 5, dp[6] = 8;*/
	for (int i = 3; i <= n; i++)
		dp[i] = dp[i - 2] + dp[i - 1];
	cout << dp[n] << endl;
}