Implementation_구현[기초] (Bronze 중위권)

이왕 블로그 만든 김에, 제가 블로그를 만든 이유인 백준 포스팅을 하나 하려고 합니다.

 

 

코딩에 익숙하지 않으신 편이면, 사고는 되는데 구현이 힘든 경우가 많습니다.

 

"아, 나는 이렇게 이렇게 풀어야 함은 아는데, 코드로 구현을 못하겠다... 답답하네."

"설마 이렇게 푸는게 맞겠어? 너무 복잡한데"

 

이러한 한탄은 대부분 코딩 경험이 적어서, 또는 현재 하고 있는 언어(ex. C++) 문법이 익숙하지 않아서일 확률이 거의 80% 이상입니다.

 

간단하게 문제 하나 보고 가시죠.

www.acmicpc.net/problem/1233

1233번: 주사위

문제를 보면, 주사위이긴 주사위인데,

우리가 알고 있는 1부터 6까지 있는 주사위가 아닌, 1부터 20까지, 또는 40까지 있는 주사위입니다.

 

이런 문제를 만나면, 여러분은 어떻게 해결하실 생각이신가요?

보통, 두 가지 케이스로 나뉘더군요.

---

1. 3중 for문 돌려서 빈도수를 다 따져봐야지~

2. 설마 3중 for문 다 돌리는 거겠어? 엄청 복잡해지고 코드 더러워지고, 시간 엄청 오래걸리는거 아냐?

---

놀랍게도, 이 문제는 1번 경우처럼 해결하면 됩니다.

 

3중 for문을 돌린다 해도, 구현이 크게 복잡하지 않으며,

s1<=20, s2<=20, s3<=40 이므로 for문을 돌린다 해도, O(20*20*40)=O(16,000) 입니다.

(시간 복잡도 개념은 알고 있어야 편합니다.)

 

우리 컴퓨터는 보통 1초에 1억번 연산이 가능하다고 알려져 있습니다. (요즘은 컴이 좋아져서 2억번, 5억번까지도 가능하지만, 시간복잡도를 계산할 때 보통 1초에 1억번으로 잡고 계산합니다.)

 

따라서, 16,000번 연산은 컴퓨터 입장에서 아주 우스운 연산 횟수이죠. 3중 for문을 돌립니다.

3중 for문으로 일일이 다 돌려서 빈도수를 체크해줍니다. 이렇게 전체 경우를 완전탐색하는 알고리즘 명칭이 따로 있는데요, 바로 Bruth-Force Algorithm (브루트포스 알고리즘) 입니다. 이 알고리즘에도 종류가 굉장히 여러 개 있죠.

 

---

그런데, 빈도수를 어떻게 체크하죠??

답은 간단합니다. 빈도수를 체크하는 배열 변수를 하나 만들어줍니다.

저는 count 할 때의 그 cnt 변수를 새로 만들어줬습니다.

 

주사위 세 개를 굴릴 때 가장 크게 나올 수 있는 값이 20, 20, 40일 때인 80이므로

cnt[80]까지 만들어주면 되겠습니다... 가 아니라!

 

주사위는 1~80까지의 값이 나옵니다.

cnt[80]으로 만들 경우, cnt[0] ~ cnt[79]까지밖에 접근을 못하므로 cnt[81]로 만들어주도록 합니다.

(물론, 1~80까지 값이 나올 때, 그 값에서 1을 빼줘서 0~79까지의 값을 체크해줘도 됩니다. 다만, 나중에 어떤 값이 제일 많이 나왔는지 체크할 때 헷갈리니까 저는 81까지 배열 크기를 지정해줬습니다.)

---

cnt[0]은 주사위 값이 2부터 있으므로 나올리가 없죠.

cnt[0]=0입니다.

 

cnt[6]부터 값이 나오겠네요. 주사위 s1, s2, s3가 각각 2,2,2일 때 뿐이므로

cnt[6]=1입니다.

cnt[7]은 s1,s2,s3가 각각 2,2,3 / 2, 3, 2/ 3, 2, 2 일 때이므로

cnt[7]=3이겠네요.

 

이렇게 빈도수가 3중 for문을 돌면서 저장이 되는 코드를 작성합니다.

cin >> s1 >> s2 >> s3;
for (int i = 1; i <= s1; i++) {
	for (int j = 1; j <= s2; j++) {
		for (int k = 1; k <= s3; k++) {
			cnt[i + j + k]++;
		}
	}
}

그럼 위와 같이 코드가 완성될 겁니다.

---

그럼 이제, 빈도수 중에서 가장 큰 값을 어떻게 뽑아내지?

구현이 약하시다면, 이 부분도 어려울 겁니다. 잘 생각해봅시다.

 

cnt[0] ~ cnt[80] 중 그 값이 제일 클 때의 index를 뽑아내고 싶은거니까 단순히 max값을 구하는 알고리즘은 아닐겁니다.

사실 구현이 약하면 단순히 max를 구하는 경우도 어렵습니다. (algorithm 헤더파일의 max함수를 모른다는 가정 하에)

 

일단, 80개 중에서 가장 큰 값을 뽑아내고 싶은거니까

for문을 돌아야 할 것임은 확실하고요..

그 다음은 코드를 보면서 설명드리죠.

for (int i = 1; i <= 80; i++) {
	if (ans < cnt[i]) {
		ans = cnt[i];
		idx = i;
	}
}

맨 처음에 ans 변수값은 저는 빈도수 값으로 나올 수 있는 값 중 가장 최소인 0으로 지정을 했습니다. 아예 나올 수 없는 값인 음수로 지정해도 좋습니다. 일단 최솟값으로 놓아주세요.

최댓값을 구하고 싶을 땐, 비교대상을 극소로, 최솟값을 구하고 싶을 때는 비교 대상을 극대로 놓습니다.

---

그 다음에 for문으로 돌아, ans보다 큰 값이 있으면, ans를 그 빈도수 값으로 바꿔줍니다. 위 if문이 바로 그 코드입니다. 이 때 우리는, 빈도수 값을 알고싶은 것이 아닌, 언제 최대가 되는지의 index를 알고 싶은 것이기 때문에 idx 변수로 그 때의 index도 저장을 합니다.  

ans보다 큰 값이 있으면, 그 때의 값으로 바꿔주고, 아닌 때에는 if문 안의 코드가 돌지 않으니, 결론적으로는 ans와 idx는 빈도수가 최대일 때의 값이 저장이 되겠죠?

 

전체 코드를 보시면 좀 더 이해가 편하실 겁니다.

#include <iostream>
#include <algorithm>
using namespace std;
int s1, s2, s3, cnt[81], ans, idx;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> s1 >> s2 >> s3;
	for (int i = 1; i <= s1; i++) {
		for (int j = 1; j <= s2; j++) {
			for (int k = 1; k <= s3; k++) {
				cnt[i + j + k]++;
			}
		}
	}
	for (int i = 1; i <= 80; i++) {
		if (ans < cnt[i]) {
			ans = cnt[i];
			idx = i;
		}
	}
	cout << idx << "\n";
}

• cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)는 c++ 시간 단축을 위해 작성한 코드입니다. 이 코드를 작성하면 printf, scanf와 같은 c언어 코드와 함께 작성할 수 없습니다.
• 전역변수 s1, s2, s3, cnt[81], ans, idx 로 지정할 경우 값이 0 (bool 형일 경우 false)로 초기화됩니다. 전역변수는 객체지향 프로그래밍에서는 지양해야 할 사항이나, 백준과 같은 절차지향 프로그래밍에서는 크게 상관이 없습니다.

이렇게 최대일 때를 뽑아내고, idx만 출력해주면 문제에서 원하는 답이 나옵니다. 

구현력이 약할 경우, cnt 변수를 만들어주는 것과 idx변수를 만들어주는 것을 힘들어하셨을 겁니다.

이는 앞으로의 경험으로 충분히 메꿀 수 있습니다. 구현은 많이 해보는 것이 답입니다.

---

그럼 추천문제 드리겠습니다.

 

 

www.acmicpc.net/problem/1085

1085번: 직사각형에서 탈출

난이도: 하

쉽습니다. 다만, 맞왜틀 (맞았는데 왜 틀림?) 하는 경우도 꽤 있더라고요.

x, y, w-x, h-y 중 최소를 구하면 되는 문제입니다.

어떻게 하면 좋을까요? algorithm 헤더파일의 함수인 min함수를 써도 좋고, 배열에 넣어서 sorting 후 0번째 원소를 뽑아내도 좋을 것 같고, 위 주사위 문제처럼 for문 돌아서 if문으로 최솟값을 뽑아내도 좋을 것 같습니다.

---

 

www.acmicpc.net/problem/2490

2490번: 윷놀이

난이도: 하

0이 몇 개 나오는지 세주면 되는 문제입니다.

각 한 줄(테스트케이스)마다 네 개의 수를 입력받아, 0이 입력될때마다 특정변수의 값을 증가시키면 되겠네요.

이후, 그 값에 따라 A, B, C, D, E 중 하나를 출력해주면 됩니다.

---

 

www.acmicpc.net/problem/10250

10250번: ACM 호텔

난이도: 중

왜 Bronze III인지 모르겠네요. 저는 브론즈2 정도는 된다고 생각합니다.

이걸 구현으로 풀지, 수학으로 풀지 난감하시죠?

배열로 하면 코드가 꽤나 복잡해지리라 예상합니다. 단순히 수학으로 접근할 수 있습니다.

---

 

www.acmicpc.net/problem/1259

1259번: 팰린드롬수

난이도: 중

처음에 이 문제를 접하면 어려울 겁니다. 팰린드롬(회문)은 앞으로 굉장히 많이 보게 될 주제 중 하나죠.

처음에 구현이 약하실 때에는 문자열 길이가 홀수인지, 짝수인지에 따라 if문으로 나눠서 해결하는 경우가 많습니다.

그러나, 이 문제는 if문 없이 단일for문으로 충분히 해결이 가능합니다.

 

문자열의 길이/2 까지만 for문을 돌아야 하므로 헷갈릴 수 있는데, C++에서 홀수/2 의 경우, 소수점은 버립니다. 만약 문자열의 길이가 7이라면, 3번째 문자까지 for문을 돈다는 소리죠. 

이걸 왜 설명했냐면, 문자열의 길이가 홀수일 땐, 가운데 문자는 따져볼 필요가 없습니다!

그 이유는 가운데 문자가 뭐든 간에, 가운데 글자는 거꾸로 해도 가운데거든요.

 

따라서 그냥 아래처럼 코드를 짜시면 됩니다. flag=0이 되면 팰린드롬수가 아니라는 거예요

for (int i = 0; i < s.length()/2; i++) {
	if (s[i] != s[s.length() - 1 - i])
		flag = 0;
}

문자열의 길이가 8일 때, 마지막 문자의 index는 8이 아닌 7임에 주의하세요.

---

 

 

사실 쉬운 구현 문제들은 백준에 셀 수 없이 많이 있습니다.

아래 홈페이지에서 구현력을 충분히 기르시면 됩니다. 

solved.ac/problems/tags/implementation

solved.ac - 문제 › 태그 › implementation

포스팅 이거 은근 많이 시간 잡아먹네요 ㅠㅠ

아마 담엔 기초부터 차근차근 포스팅하진 않을 거 같고,

중간중간 동기들, 지인분들한테 알려주고 싶은 알고리즘 포스팅할거같네요