Posted Updated a minute read (About 190 words)

B11728

개요

백준 문제 11728번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 20분
https://www.acmicpc.net/problem/11728

문제

정렬되어있는 두 배열 A와 B가 주어진다.
두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
using namespace std;
const int MAX =	1000000;
int arrA[MAX],arrB[MAX];
int resultArr[MAX];

void merge(int N,int M)
{
	int k = 0;
	int i,j;
	for(i=0,j=0;i < N && j < M;)
	{
		if(arrA[i] > arrB[j])
		{
			resultArr[k++] = arrB[j++];
		}
		else
		{
			resultArr[k++] = arrA[i++];
		}

	}
	while(i < N)
	{
		resultArr[k++] = arrA[i++];
	}
	while(j < M)
	{
		resultArr[k++] = arrB[j++];
	}


}

void solve()
{
	int N,M;
	cin >> N >> M;
	for(int i=0;i<N;i++)
	{
		cin >> arrA[i];
	}
	for(int i=0;i<M;i++)
	{
		cin >> arrB[i];
	}
	merge(N,M); 
	for(int i=0;i<N+M;i++)
	{
		cout << resultArr[i];
		if(i+1 != N+M)
		{


			cout << " ";
		}

	}

}


int main()
{
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	solve();

}

풀이

  1. 정렬된 두 배열이라는 점
  2. 합친다음 출력한다
    => merge sort에서의 분할을 제외한 부분과 동일

    배울 점, 메모

Posted Updated 3 minutes read (About 377 words)

B10816

개요

백준 문제 10816번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 60분
https://www.acmicpc.net/problem/10816

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다.
상근이는 숫자 카드 N개를 가지고 있다.
정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <algorithm>
#include <iostream>
using namespace std;
const int arrMax = 500000;
const int numMax = 10000001;
int marking[arrMax];
int sortedMark[arrMax];
int num[arrMax];
int plusNum[numMax];
int minusNum[numMax]; // think as just * -1
//1. 숫자 입력받음 
//

void binSearch(int N,int obj)
{
	int i=0,j,mid;
	j = N;
	while(i <= j)
	{
		mid = (i + j)/2;
		if(num[mid] == obj)
		{
			if(obj < 0)
			{
				cout << minusNum[obj * -1];
			}
			else
			{
				cout << plusNum[obj];
			}
			return;		
		}
		else if(num[mid] > obj)
		{
			j = mid -1;
		}
		else if(num[mid] < obj)
		{
			i = mid + 1;
		}

	}
	cout << 0;
}


void solve()
{
	int N,M;
	cin >> N;
	fill_n(plusNum,numMax,0);
	fill_n(minusNum,numMax,0);
	for(int i=0;i<N;i++)
	{
		cin >> num[i];
		if(num[i] < 0)
		{
			minusNum[num[i] * -1] += 1;
		}
		else
		{
			plusNum[num[i]] += 1;
		}
	}
	cin >> M;
	for(int i=0;i<M;i++)
	{
		cin >> marking[i];
		sortedMark[i] = marking[i];
	}
	
	sort(num,num+N);
	for(int i=0;i<M;i++)
	{
		if(i != 0)
		{
			cout << " ";
		}
		binSearch(N,marking[i]);
		
	}

	/*
	for(int i=0;i<M;i++)
	{
		if(marking[i] < 0)
		{
			cout << minusNum[-1 * marking[i]];
		}
		else
		{
			cout << plusNum[marking[i]];
		}
		if(i != M-1)
		{
			cout << " ";
		}
	}		
	*/
	

}

int main()
{

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();

}

풀이

  1. 10815번과 마찬가지로 입력에 대한 정렬
  2. 1 이번에는 입력시에 빈도수를 계산해야한다.
  3. 정렬 한 것에 대한 이분 탐색
  4. 탐색 결과에 대한 출력(빈도수)

피드백, 메모

문제를 잘못이해했음
문제 읽는데 더 시간을 들이자.

Posted Updated 2 minutes read (About 302 words)

B10815

개요

백준 문제 10815번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 30분
https://www.acmicpc.net/problem/10815

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다.
상근이는 숫자 카드 N개를 가지고 있다.
정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> num;
void binSearch(int N)
{
	int i,j;
	int M = 0;
	int mid = 0;
	int obj;
	int searched = 0;
	cin >> M;
	for(int k=0;k<M;k++)
	{
		cin >> obj;
		if(k != 0)
		{
			cout << " ";
		}
		i = 0;
		j = N-1;
		searched = false;
		while(i <= j)
		{
			mid = (i + j)/2;
			if(obj == num[mid])
			{
				searched = 1;
				break;
			}
			else if(obj > num[mid])
			{
				i = mid+1;
			}
			else
			{
				j = mid-1;
			}
		}
		cout << searched;
	}

}
void solve()
{
	int obj;
	int val = 0;
	int N;

	cin >> N;
	for(int i=0;i<N;i++)
	{
		cin >> val;
		num.push_back(val);
	}
	sort(num.begin(),num.end());
	binSearch(N);

}

int main()
{
	ios_base::sync_with_stdio(0);
    cin.tie(0);
	solve();
}

풀이

탐색 -> 빠른 탐색 알고리즘인 이진 탐색 사용
이진 탐색 사용할려면 정렬해야함 -> 이번에는 sort() 사용

배울 점, 메모

1
2
ios_base::sync_with_stdio(0);
cin.tie(0);

위 코드 안써서 시간초과남
부담갖지말고 매일매일 하루를 채운다는 느낌

Posted Updated 5 minutes read (About 784 words)

B2110

개요

백준 문제 B2110번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 60분
https://www.acmicpc.net/problem/2110

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 200001;
int home[MAX];
int maxLen = 0;
int countNum = 0;


int checkPosibleInstall(int distance)
{
	int count = 1;
	int curHome = home[0];
	for(int i=1;i<countNum;i++)
	{
		if(distance <= home[i] - curHome)
		{
			count++;
			curHome= home[i];
		}
	}
	return count;
}

void binarySearch(int start,int end,int haveToInstall)
{	
	if(start > end)
	{
		return;
	}
	int mid = (start + end) / 2;
	int installedCount = checkPosibleInstall(mid);
	if(installedCount >= haveToInstall)
	{
		maxLen = max(maxLen,mid);
		binarySearch(mid+1,end,haveToInstall);
	}
	else
	{
		binarySearch(start,mid-1,haveToInstall);		
	}



}

void solve()
{
	int N,installNum;
	cin >> N >> installNum;
	for(;countNum<N;countNum++)
	{
		cin >> home[countNum];
	}
	sort(home,home+countNum);
	int distance = home[countNum-1] - home[0];
	binarySearch(1,distance,installNum);
	cout << maxLen;
}


int main()
{
	solve();
}

풀이

* 웹에서 참고 많이한 문제

문제 풀이는 우선 동적계획법과 비슷한 느낌으로
정해진 간격을 두고 일단 설치한 뒤에 조건을 돌아보는 식으로 풀 수 있다.
자세히는 설치하는 공유기들은 이전에 설치된 공유기와 간격값이 크거나 같아야 한다.(주어진 간격보다 적으면 안되니까)
이 조건으로 우선 설치를 한 뒤에
설치할 수 있는 수와 비교하여 간격을 줄이거나 늘리는 방법으로

답을 찾을 수 있다.

배울 점, 메모

이 문제를 보고 생겼던 의문점 하나
이분 탐색인데 정렬이 안되어서 입력이 들어온다 -> 정렬해야하지 않나? => YES
logN에 풀어야하는데 기존 정렬함수는 효율적으로 잘 짜여져있어 사용해도 됨.

문제를 읽고 생각을 해봤는데 자신의 생각에 확신이 안들어 금방 포기해버렸다.
간격을 항상 같아야 한다고 생각했는데 사실 간격보다 크기만 하면 되는 것이었다.
일단 설치한 뒤에 조건을 돌아보는 방식을 생각하지 못하여서 어떻게 구현할지 조차 감이 안잡혔다.

어떻게 개선할까

  • 한 문제당 최소 30분 이상은 안풀리더라도 구현하지않고 생각하자
  • 생각 및 구현이 1 시간이 넘어가지 않는다면 무조건 자신감 갖고 그냥 생각한대로 구현해보자
    • 이것이 필요한 이유는 첫번째로 자신의 생각에 자신감을 갖기 위함
    • 두번째로 틀리거나 모르겠어도 배울점이 많을 것이기 때문이다
Follow

Categories

Recents

Archives

Tags

CRF3
algorithm72
book_report2
database1
java26
jpa1
pet project12
pet_project1
retrospect1
springboot3
web3
web pet project2
write3

Subscribe for updates

×