기록을

문제 링크

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

재귀라는 아이디어는 쉽게 얻을 수 있었다.

구체적인 구현을 하는 데에는 시간이 꽤 걸렸다.

문제 제목처럼, 2차원 배열 모양의 평면을 반복적인 Z 모양으로 탐색하는 것이다.

재귀 함수를 구현할 때, base condition(탈출 조건)을 2*2 즉 한 변의 길이가 2일 때로 설정하면 된다.

그리고 순회하면서 0부터 쭉 순회 순서를 카운트 해줘야하기 때문에 전역 변수로 cnt를 두었다.

그림을 보면 n = 2일 때는 n = 1일 때의 상황이 네 번 반복된다.

또한 n = 3일 때는, n = 2일 때의 상황이 네 번 반복된다는 것을 알 수 있다.

따라서 base condition이 아닌 n을 처리하기 위해서는 4번의 n - 1을 처리하는 과정이 필요하다는 것을 알 수 있다.

2의 n승 형태로 인자가 들어가기 때문에 1<<n을 사용했다.

#include<iostream>
using namespace std;
int cnt = 0;
int n, r, c;
void func(int len, int row, int col) {
	//base condition: n = 2일 때
	if (len == 2) {
		if (row == r && col == c) {
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		if (row == r && col + 1 == c)
		{
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		if (row + 1 == r && col == c)
		{
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		if (row + 1== r && col + 1 == c)
		{
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		return;
		
	}
	func(len / 2, row, col);
	func(len / 2, row, col + len / 2);
	func(len / 2, row + len / 2, col);
	func(len / 2, row + len / 2, col + len / 2);

}
int main(void) {

	
	cin >> n >> r >> c;
	func(1 << n, 0, 0);

	return 0;
}

0. 시작은 누구나 다르다. 자신에게 꼭 필요한데, 가장 부족한 능력이 무엇인지에 맞춰서 계획을 세워야 할 것이다.

(자료구조는 점점 깊게 공부)

사실상 6부터의 순위는 크게 의미가 없다. etc라고 본다.

1. 재귀

2. 백트래킹

3. BFS, DFS

4. DP 및 이상의 것들을 활용한 완전 탐색

5. 그래프 알고리즘

6. 수학

7. 문자열

8. 기하

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

중학교 수학 문제에 등장했던 하노이의 탑이다.

재귀를 이용한다. 5개의 링을 옮기는 과정 속에는 4개의 링을 옮기는 과정이 포함된다.

4개의 링을 옮기는 과정 속에는 3개의 링을 옮기는 과정이 포함된다.

이런식으로 끄적이며 생각해보면 재귀라는 아이디어를 얻을 수 있을 것이다.

예를 들어서, 첫번째 자리에 있던 모든 링들을 세번째 자리로 옮긴다고 하자.

이를 위해서는 가장 아래에 깔려있는 가장 큰 링을 빼내야 한다. 이를 위해서는 그것 위에 있는 n - 1 개의 링을 모두 임시적으로 다른 곳에 옮길 필요가 있다.

주의할 것은, 2의 20승을 계산할 때, pow함수의 출력이 의도한대로 나오지 않는다는 것이다. 이를 위해서 1 << n 연산을 이용한다.

#include<iostream>
#include<math.h>
using namespace std;

void hanoi(int src, int dst, int n) {
	if (n == 1) {
		cout << src << ' ' << dst << '\n';
		return;
	}
	int temp = 6 - src - dst;
	hanoi(src, temp, n - 1); //1 ~ n-1 링을 중간지점에 옮긴다
	cout << src << ' ' << dst << '\n'; //가장 커다란 링을 목적지로 옮긴다.
	hanoi(temp, dst, n - 1); //중간지점에 있던 n - 1 개의 링들을 목적지로 옮긴다.
}

int main(void) {
	int n;
	cin >> n; //옮기는 링의 개수
	//cout << pow(2, n) - 1 << '\n';// 이렇게 쓰면 틀림 n = 20일때 output이 이상해짐
	cout << (1 << n) - 1 << '\n'; // 2의 n승 -1
	hanoi(1, 3, n);

	return 0;
}

재귀로 풀이를 진행할 때는

1. base condition을 명확히 정의한다.

2. 재귀 식을 찾는다.

n개를 옮기려면, n - 1을 다른곳으로 옮긴 이후에 하나 옮기고 다시 n - 1을 목적지로 옮겨야해.. 와 같은

이 때, 이전 과정이 올바르게 작동할 것이라는 가정을 하고, 현재의 함수가 올바르게 결과를 내놓을지 판단한다.

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

A^B mod m을 연산하는 프로그램을 작성하는 문제이다.

수의 범위가 20억까지 가능하기 때문에 long long 타입을 활용한 것 이외에 재귀를 진행할 때도 아이디어가 하나 필요했다.

B가 홀수냐 짝수냐에 따라서 경우를 나눠줬다.

재귀의 base condition은 B가 0일 때 1을 반환하는 것이 된다.

또한 overflow를 방지하기 위해 계산하는 중간중간에 modular 연산을 수행해줄 필요가 있다.

XYmodM = (XmodM * YmodM) mod M 인 것을 이용하면 되겠다.

지수가 홀수인 경우, 계산 이후에 a를 한 번 더 곱해줘야 하고, 이 과정에서 modular 연산을 한번 더 수행해줘야 한다.

#include<iostream>
using namespace std;
typedef long long ll;

ll POW(ll a, ll b, ll m){
    if(b == 0) return 1;
    ll val = POW(a, b/2, m);
    val = val * val % m;
    
    //b가 짝수, 홀수인 경우 나눠서 처리
    if(b % 2 == 0) return val;
    else
        return (val * a) % m;
    
}

int main(void){
    int a, b, m;
    cin >> a >> b >> m;
    cout << POW(a, b, m);
    return 0;
}

두 문제를 150분 동안 풀면 되는 테스트였다.

1번 문제에서 예상하지 못한 제한 조건이 있었다.

Array와 List만 사용하라는 것이 조건이었다.

이런 조건은 그저 문제를 위한 문제라는 생각이 들었지만, 잘하는 사람이라면 이러한 조건에 상관없이 무리 없이 문제를 풀어냈을 것이다.

구조체를 활용해서 배열을 만들어서 풀기는 했다. 하지만 처음에 크게 삽질을 한 덕분에 시간이 많이 지체되었다.

시간이 지체되었음은 물론이고 문제 하단에 작게 나와있는(나는 못봤지만 그렇다고 전해지는) 대문자와 소문자 상관없이 함수가 동작하도록 코드를 작성하라는 조건을 보지 못했다.

이 작은 부분을 놓쳤기 때문에 테스트는 결과적으로 실패라고 할 수 있겠다.

앞으로는 문자열 문제를 다룰 때, 필히 대문자와 소문자 조건은 어떻게 되는지 예민하게 확인할 필요가 있겠다.

사실 이 조건을 생각하지 않은 경우가 이번이 처음이 아니다. 이전에 보았던 테스트에서도 동일한 실수를 한 경험이 있었다.

따라서 앞으로는, 문자열 문제를 대할 때, 대소문자 조건이 어떻게 되는지 예민하게 확인하도록 하자.

또 다른 한가지는, 기능 단위로 함수를 구현할 때, 특히 bool 타입을 반환하는 함수를 작성하고 호출할 때 나오는 실수이다.

이 문제는 IDE를 사용하지 못했기 때문에 예민하게 알아차릴 수가 없었다.

가령 isContain() 이라는 bool 타입을 반환하는 함수가 있다고 하면, 당연히 함수를 호출할 때 isContain()이라고 호출해야 한다.

하지만 무슨 이유에선지 isContain이라고만 작성했는데 온라인 컴파일러 상에서 작동했고, 나는 로직의 문제가 이 부분이 아닌 다른 부분에 있다고 생각하여 손댈 필요 없는 부분을 손대는 데에 시간을 많이 소비했다.

내가 할 여지가 있는 실수들을 잡아냈다는 점에서는 수확이 있었지만, 아쉽긴 하다.

이러한 실수를 연습할 때 더 많이 해볼 수 있도록 해야겠다.