내가 그때 이걸 알았더라면

> 문제

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

> 풀이

문제 자체는 보기엔 간단해 보이지만, 1~n까지의 모든 문자열 각각에 대해 각 자리의 숫자를 카운트 해주면 시간초과가 나는 문제이다. 시간복잡도만 보자면 O(nlogn)인데 문자열 처리에 걸리는 시간에  n <= 10^9 라 시간 초과가 나기 쉽다.

Idea 1)

10^k <= n인 최대 k를 구한 뒤,

1~10^k - 1까지 각 숫자마다 나오는 개수를 세고, 다시 10^k~n에서 나오는 숫자를 카운팅 해주는 아이디어이다.

하지만 구현이 복잡했고 더 간단한 방법이 있어 두 번째 방법을 이용했다.

Idea 2)

각 자리에서 0~9 각 숫자마다 가질 수 있는 경우의 수를 세주는 알고리즘이다.

이렇게 하면 O(logn)만에 해결 가능하다.

원리는 다음과 같다.

ex) n = 54321 일 때

일의자리수 -> 

0은 10, 20, 30, .., 54320까지 5432번 가능하다.

1은 1, 11, 21, .., 54321까지 5432 + 1 = 5433번 가능하다.

2는 2, 12, .., 54312까지 54332번 가능하다.

...

9는 9, 19, .., 54319까지 5432번 가능하다.

십의자리수 ->

0은 100~109, 200~209, .., 54200~54209, 54300~54309 까지 총 5432*10 + 10번 가능하다.

1은 10~19, 110~119, 210~219, .., 54210~54219, 54310~54319 까지 총 (5432 + 1) * 10 + 10번 가능하다.

2는 20~29, 120~129, .., 54220~54229, 54320~54321까지 총 (5432+1) * 10 + 2번 가능하다.

...

만의자리수 ->

0은 0번 가능하다.

1은 10000~19999까지 10000번 가능하다.

...

4도 40000~49999까지 10000번 가능하다.

5는 50000~54321까지 4321 + 1 = 4322번 가능하다.

이 과정에서 규칙들을 찾아보면 각각 i번째 자리일 때 (i는 자릿수 - 1)

> i = 0~ i = length - 2 에서는

- 0 갯수

i번째 자리수가 0보다 클 때)

cnt[0] => (n // 10^i+1) * 10^i

i번째 자릿수가 0일때)

cnt[0] => (n // 10^i+1 - 1) * 10^i + n % 10^i + 1

- 1~9 갯수 (각자 j라고 하자)

i번째 자릿수가 그 수보다(j) 클 때)

cnt[j] => (n // 10^(i+1) + 1) * 10^i

i번째 자릿수가 j와 같을 때)

cnt[j] => (n // 10^(i+1)) * 10^i + n % 10^i + 1

i번째 자릿수가 j보다 작을 때)

cnt[j] => (n // 10^(i+1)) * 10^i

> i = length - 1 (맨 왼쪽 자리)일때

- 0갯수

cnt[0] = 0

- 나머지 수 갯수(n의 맨 상위 자릿수보단 작은 수 j)

cnt[j] => 10^i

- n의 맨 상위 자릿수

cnt[j] => n % 10^i + 1

이렇게 각각 더해 주는 코드를 작성하면 아래와 같다.

// Baekjoon No. 1019 - 책 페이지 220121~220911
// Time Complexity O(logn)
// #Math
/** 
각 자리마다 각 숫자들이 몇 개의 경우의 수를 제공할 수 있는지 케이스를 나누어 각각 세어 답을 구하는 알고리즘
기존의 1~n까지 모든 숫자를 str로 변환해 수를 하나씩 세는 알고리즘은 너무 비효율적임.
*/
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, length;
	int i, j;
	unsigned long long int cnt[10] = { 0 };
	cin >> n;

	// solving
	string number = to_string(n);
	length = number.length();
	// 일의자리~ 맨 상위자리 - 1 까지
	for (i = 0; i < length - 1; i++) {
		// 0은 따로 취급. 0보다 그 자릿수가 작은 경우는 없으므로 그 경우는 제외하고 0일때랑 0이 아닐 때 (클 때)만 고려.
		if(number[length - 1 - i] - '0' != 0)
			cnt[0] += (n / (int)pow(10, i + 1)) * (int)pow(10, i);
		else
			cnt[0] += (n / (int)pow(10, i + 1) - 1) * (int)pow(10, i) + n % (int)pow(10, i) + 1;

		for (j = 1; j < 10; j++) {
			// 그 자리의 숫자 (number[length - 1 - i]) 가 j (현재 가짓수 더하는 수)보다 클 때, 같을 때, 작을 때 세가지로 나누어 분류.
			if (number[length - 1 - i] - '0' > j)
				cnt[j] += (n / (int)pow(10, i + 1) + 1) * (int)pow(10, i);
			else if (number[length - 1 - i] - '0' == j)
				cnt[j] += n / (int)pow(10, i + 1) * (int)pow(10, i) + n % (int)pow(10, i) + 1;
			else
				cnt[j] += (n / (int)pow(10, i + 1)) * (int)pow(10, i);
		}
	}

	i = length - 1;
	// 맨 상위자리
	for (j = 1; j < 10; j++) {
		if (number[0] - '0' > j)
			cnt[j] += (int)pow(10, i);
		if (number[0] - '0' == j) {
			cnt[j] += n % (int)pow(10, i) + 1;
		}
	}
	
	for (i = 0; i < 10; i++)
		cout << cnt[i] << " ";

	return 0;
}

> 결론

각 자리마다 나오는 수를 세는 알고리즘이 가장 간결하고, 구현도 그나마 쉬운 편이다.

> 문제

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

> 풀이

idea 1) memorization

1. 길이가 k+1인 배열을 만들고 (memory[x+1], memory[x]에 쌍 개수 저장할 것)
2. 입력받은 숫자들을 하나씩 순회하며 (arr[0]~ arr[n-1])
3. 만약 memory[]의 그 숫자에 해당하는 칸이 존재한다면 (memory[arr[i]]) 1을 집어넣는다.
4. 그리고 memory[x - arr[i]] 에 1이 담겨 있다면, 쌍이 존재한다는 의미이므로 memory[x]의 값을 1 증가시킨다.
5. memory[x]의 값을 출력한다.

이처럼 길이가 x+1인 배열을 만들고, 두 수의 합으로 x를 만들 수 있는 쌍이 ai, aj가 다르면 유일하다는 점을 이용해 memory에 각각 x를 구성하는 ai - aj가 존재함을 저장해 ai마다 x를 만들 수 있는 aj가 있는지 확인하는 방법으로 문제를 해결할 수 있다.

// Baekjoon No. 3273 두 수의 합
// Time Complexity O(n)

#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, x;
    int i;
    cin >> n;
    vector<int> arr(n);
    for (i = 0; i < n; i++)
        cin >> arr[i];
    cin >> x;
    vector<int> memory(x + 1, 0);

    // solving
    for (i = 0; i < n; i++) {
        if(arr[i] < x)
            memory[arr[i]] = 1;
        if (x - arr[i] > 0 && arr[i] * 2 != x && memory[x - arr[i]])
            memory[x] ++;
    }
    cout << memory[x];

    return 0;
}

idea 2) 투 포인터

그리고 문제 유형에 적혀 있는 투 포인터 방식을 이용하는 방법이 있다.

1. 쌍 개수를 저장할 cnt 변수를 0으로 초기화한다.
2. 배열 arr[]에 ai 값들을 입력받는다.
3. arr[]을 오름차순 정렬한다. (시간복잡도 O(nlogn)
4. 정렬한 arr에서 arr[0]이 arr[n-1]이랑 더했을 때 x보다 큰지 작은지 확인한다.
5. 만약 그 값이 x보다 크다면, arr[0] + arr[n - 1 - i] 가 x보다 작거나 같을 때까지 i를 0부터 증가시킨다. (arr의 오른쪽 idx--)
6. 만약 그 값이 x와 같다면, cnt++, arr의 오른쪽 idx -- (또는 왼쪽 idx ++)
7. 만약 그 값이 x보다 작다면, arr의 왼쪽 idx ++
8. 이대로 arr의 오른쪽 idx와 왼쪽 idx가 겹칠 때까지 반복을 수행한다.

언뜻 보면 arr[l] (왼쪽 idx)를 증가시켰을 때 arr[r]과의 합이 x보다 커버리는 경우가 생길 수도 있다고 생각할 수 있지만, 애초에 arr[l]을 증가시키는 경우는 arr[l] + arr[r] < x인 경우이므로 이 경우에는 r--을 해주어야 한다.

> 결론

- 투 포인터를 이용하면 O(nlogn), memorization을 이용하면 O(n)

- 배열을 다룰 때 idx 범위를 조심할 것 (memorization에서 0 < arr[i] < x, 2*arr[i] != x)

https://m.blog.naver.com/ndb796/221236874984

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-sort

위 블로그를 참고하였습니다.

> 위상 정렬이란?

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
위상 정렬을 사용하면 기존에 해줘야 하는 작업들을 순서대로 정렬할 수 있으며, 해당 그래프가 위상 정렬을 사용할 수 있는 그래프인지까지 알 수 있다.
- https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

> 그럼 어떻게 만들 수 있는가?

queue, 또는 stack을 이용하여 구현할 수 있다고 한다.

일단 여기서 필자는 queue를 이용하여 구현을 했다.

백준 1005번 ACM Craft (https://www.acmicpc.net/problem/1005) 를 풀 때 사용했다.

> 알고리즘 순서 (queue를 이용한 방법)

1. 먼저 노드에 오는 간선 개수가 0인 노드들은 큐에 추가한다.
2. 큐에서 노드를 하나 빼서 그 노드가 가리키는 간선들을 제거한다.
3. 큐에서 빠진 노드를 리스트에 추가한다.
4. 다시 노드에 오는 간선 개수가 0인 노드들을 큐에 추가한다.
5. 2, 3을 큐가 비워질 때까지 반복한다.
6. 큐가 비워졌을 때 만약 모든 노드가 큐에서 나오지 않았다면(리스트 요소 개수 != 총 노드 개수), 그 그래프는 위상 정렬이 불가능한 그래프(loop가 존재)이다.
7. 위상 정렬이 성공이라면, 위에서 빠진 노드들을 추가해 줬던 리스트가 위상 정렬이 된 리스트이다.

> 알고리즘 (stack을 이용한 방법)

1. 한 노드를 선택해 dfs를 시행한다.
2. 노드

> 결론

시간 복잡도가 O(V+E)라서 상당히 빠른 정렬이라고 한다. (V는 노드의 개수, E는 간선의 개수이다)

1005번은 아직 도전 중이나, 처음에 사용했던 방식인 map과 queue를 이용한 탑-다운 dp보다는 나은 것 같다.

> 문제

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

> 풀이

1. 첫 번째 풀이 : 처음에는 이전의 계단 오르기 문제랑 동일하다고 생각해서 그때의 문제풀이를 바탕으로 arr[i]에 wines[i-1] + arr[i-3] 이랑arr[i-2]랑 더 큰 수를 더하는 방법을 사용했다.
그런데 이렇게 문제를 풀면 반례가 존재하여 문제풀이에 성공할 수 없었다.

2. 두 번째 풀이 : 질문에 있던 반례를 참고하여 1.에서 사용했던 방법은 2개의 포도주를 건너뛸때 반례에 걸린다는 것을 이해했다. 그래서 arr[i] 에 wines[i] + wines[i-1] + arr[i-3] 이랑 wines[i] + arr[i-2], wines[i] + wines[i-1] + arr[i-4]중 제일 큰 수를 더해주는 걸로 고쳤다.

* 그리고 arr[n-1] 이랑 arr[n-2]랑 마지막에 비교해서 출력해줘야 하는데, 그건 arr[n-2]가 최고인 경우도 존재하기 때문이다.(arr[n-1]에 1을 마지막에 붙인 경우)

> 느낀 점

같은 유형에 비슷한 조건이라고 해서 문제풀이까지 완전히 똑같지는 않다는 것을 깨닫게 되었다. 앞으로는 비슷한 유형의 문제를 보면 그 풀이를 그대로 따라하지 맣고 참고만 하여 새로운 문제풀이 방법을 만들어낸다는 생각으로 PS를 진행해야겠다.

도움을 얻었던 글

https://www.acmicpc.net/board/view/64747

비슷했다고 생각했던 문제

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

> 코드

// Baekjoon No. 2156 포도주 시식 220801~ 220807
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, i;
    scanf("%d", &n);
    vector<int>wines(n, 0);
    vector<int>arr(n, 0);
    for(i = 0; i < n; i++)
        scanf(" %d", &wines[i]);
    
    // 초깃값만 각각 설정
    arr[0] = wines[0];
    if(n > 1)
        arr[1] = wines[0] + wines[1];
    if(n > 2)
        arr[2] = max(wines[0], wines[1]) + wines[2];
    if(n > 3)
        arr[3] = max(wines[3] + wines[2] + wines[0], wines[3] + arr[1]);
    // wines[i] + wines[i-1] + arr[i-3], wines[i] + wines[i-1] + arr[i-4], wines[i] + arr[i-2] 이렇게 3개 확인해야함.
    // 5 5 1 1 5 5 같은 반례 존재.
    for(i = 4; i < n; i++){
        arr[i] = max(max(wines[i] + wines[i-1] + arr[i-3], wines[i] + arr[i-2]), wines[i] + wines[i-1] + arr[i-4]);
    }

    if(n > 1)
        printf("%d", max(arr[n-2], arr[n-1]));
    else
        printf("%d", arr[0]);
    return 0;
}

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

from itertools import permutations
k, m = map(int, input().split())
lst = []
MAX = 98765 // 10**(5-k)    # K개의 숫자를 고를 때 나올 수 있는 가장 큰 수

# 일단 최대 범위까지 소수 리스트 만들어 놓음
check = [0] * (MAX + 1)
prime_lst = set()   # 있는지 체크하기에는 set 자료형이 최고
for i in range(2, MAX+1):
    if check[i] == 0:
        check[i] = 1
        prime_lst.add(i)  # 1부터 N까지 소수 리스트
        j = 1
        while i * j <= MAX:
            check[i*j] = 1
            j+=1

# k개의 숫자 조합
for num in permutations(range(10), k):
    if num[0] == 0: # 첫 자리가 0이면 취급 안함
        continue
    N = int(''.join(list(map(str, num))))   # 숫자 조합
    temp = N
    while temp % m == 0:    # m으로 나누어떨어지지 않을 때까지 나눠줌
        temp //= m
    i = 2
    temp_lst = []
    while i <= int(temp**0.5):  
        if temp % i == 0:   # 한 번이라도 소수와 소수가 아닌 수가 있어도 반례이므로 break 해줌
            if i in prime_lst and temp//i in prime_lst: # 2조건
                j = 2
                while j < N // 2:  # 1조건
                    if j in prime_lst and N-j in prime_lst:
                        lst.append(N)
                        break
                    j += 1
            break   #?
        i += 1
                    
print(len(lst))

처음에는 단지 리스트로 구현을 했다 시간이 너무 오래 걸려 한번 조건 부분을 손보고 리스트로 set으로 바꾸니 훨씬 연산이 빨라졌다.

시간 복잡도 개선을 위해서 set이나 deque자료형을 쓰는 것을 아끼지 말아야겠다. 

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

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

예시 입력과 출력은 다음과 같다.

여기서 필자가 제일 먼저 본 예제는 1.이다.

예제 1.에서 생각해 보면, 

여기서

이렇게 바뀌고

이렇게 바뀌어간다.(익어간다.)

이렇게 보았을 때, 1인 칸 주변의 칸들이 먼저 1로 변하고, 또 그 주변 칸이 1로 변한다는 점에서

bfs로 해결이 가능하다는 점을 유추할 수 있다.

참고) bfs와 dfs는 각각 queue와 stack 자료구조를 이용하여 구현할 수 있으며, 그림으로 보면 다음과 같다.

왼쪽이 dfs, 오른쪽이 bfs이다.

dfs는 Depth-First-Search의 약자로, 일단 깊게 내려간 다음, 끝을 찍고 이전 노드의 다른 자식 노드를 탐색하는 방식이다.

bfs는 Breadth-First-Search의 약자로, 그 노드의 자식 노드부터 전부 탐색한 다음, 다음 줄의 자식 노드를 탐색한다.

여기서 가까이 있는 노드들부터 방문한다는 점에서 이 문제가 bfs와 연관되어 있다는 점을 알 수 있다.

따라서 이를 구현한 알고리즘에는 bfs가 쓰이며 전반적인 아이디어는 다음과 같다. 

1. m, n값을 입력받는다.
2. 다음 n개 줄에서 토마토가 들어 있는 칸의 입력을 받는다.
3. queue를 만들고, 현재 칸을 한번 돌면서 1인 칸의 좌표를 queue에 추가한다.
4. delay 변수에 현재 queue의 길이만큼을 저장한다.
5. while(queue) : {    (queue에 값이 있는 한 반복한다)
6. temp에 queue에 있는 값 한 개를 뺀다. (현재 위치를 저장)
7. delay값을 1 줄인다.
8. lst[현재위치]의 값을 1로 변경한다.
9. 만약 lst[현재위치]의 상, 하, 좌, 우에 0이 있다면 queue에 추가한다.
10. 만약 delay값이 0이라면 cnt를 1 증가시키고 delay에 queue의 길이만큼을 다시 할당한다.
}
11. lst를 돌며 0이 있는지 찾는다. 만약 0이 있다면 succcess에 -1을 대입한다.
12. 만약 success가 -1이라면 -1을 출력한다.
아니라면 cnt - 1값을 출력한다.

여기서 delay변수의 의미는 다음 줄 노드의 개수를 저장한다.

만약 while문을 한 번 반복할 때마다 cnt값을 1 증가시킨다면 그 수는 전체 노드의 개수만큼 이 될 것이다.

그래서 delay값에 그 줄의 노드 개수만큼의 값을 대입해 그 만큼 counting을 하지 않도록 해서

전체 bfs시 tree에서 몇 줄이 나오는지를 알아본다.

이 문제를 풀며 어려웠던 점은

1. 좌표가 lst[temp[0]][temp[1]]로 표현되어서 x, y 좌표가 헷갈렸음

2. queue에 들어간 값이 또 들어가지 않도록 하기 위해 queue_chk값을 새로 만들어, 이미 방문한 노드를 표시해줘야 했음. 기존 방식은 queue에 그 값이 있는지 반복하며 검사하는 방식, O(k). 이걸로 시간 초과 많이 걸렸음.

3. delay값을 언제 감소시키고 언제 0인지를 검사해서 cnt 값을 증가시킬지 애매했음.

사실 이 점이 가장 어려웠던 게, 처음에 1인 노드부터 시작해서 마지막에 총 cnt를 출력할 때 1을 빼 주어야 하는데, 이를 하다 보니 많이 헷갈렸다.

결국 처음 temp에 queue값을 하나 뺄 때 delay를 1 감소시키고, queue에 값 추가가 끝난 다음 delay값을 검사하는 코드로 완성했다.

전체적인 코드는 다음과 같다.

# 7576 토마토_ver.2
import sys
from collections import deque
m, n = map(int, sys.stdin.readline().split())
lst = []
success = 0
cnt = 0
delay = 0
for i in range(n):
    lst.append(list(map(int, sys.stdin.readline().split())))

queue = deque()
queue_chk = [[0 for j in range(m)]for i in range(n)]

for i in range(n):
    for j in range(m):
        if lst[i][j] == 1 and queue_chk[i][j] == 0:
            queue.append((i, j))
            queue_chk[i][j] = 1

delay = len(queue)
while queue:
    temp = queue.popleft()
    delay -= 1
    
    lst[temp[0]][temp[1]] = 1
    if temp[0] > 0 and lst[temp[0]-1][temp[1]] == 0 and queue_chk[temp[0]-1][temp[1]] == 0:
        queue.append((temp[0]-1, temp[1]))
        queue_chk[temp[0]-1][temp[1]] = 1
    if temp[1] > 0 and lst[temp[0]][temp[1]-1] == 0 and queue_chk[temp[0]][temp[1]-1] == 0:
        queue.append((temp[0], temp[1]-1))
        queue_chk[temp[0]][temp[1]-1] = 1
    if temp[0] < n-1 and lst[temp[0]+1][temp[1]] == 0 and queue_chk[temp[0]+1][temp[1]] == 0:
        queue.append((temp[0]+1, temp[1]))
        queue_chk[temp[0]+1][temp[1]] = 1
    if temp[1] < m-1 and lst[temp[0]][temp[1]+1] == 0 and queue_chk[temp[0]][temp[1]+1] == 0:
        queue.append((temp[0], temp[1]+1))
        queue_chk[temp[0]][temp[1]+1] = 1
    
    if delay == 0:
        cnt += 1
        delay = len(queue)

for i in range(n):
    if 0 in lst[i]:
        success = -1
        break
    
if success == -1:
    print(-1)
else:
    print(cnt-1)

약간 1인 노드로부터 1이 퍼져나가는 느낌으로 총 몇 번 시행되어야 1이 판을 전부 뒤덮는지 알아내는 느낌이다.

만약 queue에 들어갈 수 있는 값이 더 이상 없는데(1 주변에 있는 0만 1이 될 수 있음)

0이 아직 판에 남아 있다면, 그 판은 끝낼 수 없는 판이라고 판단하고 -1을 출력한다.