[TIL] 24.01.26

1. 알고리즘 문제 해결

 

 

Z(백준 1074):

 간단한 분할 정복 문제, 한번 분할 할 때마다 크기가 4분의 1로 줄어든다. 먼저 배열의 중심을 기준으로 좌상단, 우상단, 좌하단, 우하단으로 나누어 찾으려는 좌표가 어디에 속하는지 찾는다. 이제 기준이 되는 배열 좌표를 수정하고, 좌표가 속한 위치에 따라 order값을 더해둔다(ex - 좌하단이었다면 변의 길이*변의 길이*2). 변의 길이를 절반으로 줄이고, 변의 길이가 1이 될 때까지 반복한다. 반복이 끝나면 order값을 출력한다. 시간복잡도는 O(N).

 

 

 

쿼드트리 (백준 1992):

 마찬가지로 간단한 분할정복 문제이다. 재귀를 이용해서 문제 내용을 그대로 구현하면 쉽게 해결된다. 압축 함수를 만들고 전달받은 범위 내 원소가 모두 같은지 확인해서 같다면 해당 숫자인 0이나 1을 출력한다. 다르다면 '(' 출력 후 4등분한 부분들에 대해 압축 함수를 다시 호출하고 ')'를 출력해준다.

 

 

종이의 개수(백준 1780):

 위 문제와 동일한 프로세스로 풀 수 있는 문제. base condition에 도달했을 때 문자를 출력하는 대신, 종이 개수 카운트만 알맞게 증가시켜놨다가 모든 재귀 종료 후에 출력해주면 된다.