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

0 ~ 9 까지 숫자 카드 스티커들을 한 번씩만 사용해 n = a + b 의 a와 b를 만들어야 한다.

여러 풀이 중에 내 생각에 제일 기똥찬 풀이는,

a와 b중에 작은 수를 b라고 하면, b의 가능 범위가 작아지므로, 완탐으로 때릴 수 있다는 것이다.

b에 스티커 5장을 쓰면 a도 5장이 되므로 b엔 최대 5장까지만 쓸 수 있다.

또한 b의 맨 앞자리는 끽 해야 8이므로, 1~87654가 b의 가능범위이다.

b가 정해지면 a도 정해지므로, 구만번 만에 풀리는 문제.

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

구현이지만 논리력에 따라 // 관찰력에 따라 코드가 짧아질 수 있는 문제

다음을 관찰하면 코드가 짧아진다.

한 큐브가 [a b c] 였다면, 반드시 나머지 일곱 개 중에 윗 그림과 같은 세 개의 큐브가 존재해야 한다.

헌데 큐브는 요리 조리 돌려도 똑같기 때문에

한 큐브 마다 -> 세 가지 방향으로 -> 나머지 7가지 큐브 중에 -> 두면이 맞닿고 같은 큐브가 존재(중요) -> 그것도 1개만

같은 조건을 전부 만족한다면 조립할 수 있다.

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

1. 트리

트리의 루트에 쿼리가 가해지면 자식들의 점수가 모두 더해진다.

-> 트리를 dfs 돌면서 번호를 매기면, 루트 노드 부터 자식들이 연속해서 들어있는 배열을 만들 수 있다. = 트리 순회 배열이라고 한단다.

2. 쿼리

트리 순회 배열에 쿼리가 가해진다.

이제 쿼리는 배열의 일부 구간을 증가시키는 쿼리가 된다.

-> 일부 구간을 빠르게 증가시키는 방법이 필요하다.

-> 증가시켰으면 값이 얼마인지도 빠르게 알아낼 방법이 필요하다. = 펜윅트리의 ( range update & point query ) 모드를 사용하자.

3. 펜윅 트리

이 자료구조는 다음 두 기능을 로그시간에 제공하는 자료구조다.

1) update(p, v) : p번째 원소를 v만큼 증가시킨다.

2) query(p) : 첫번째 원소부터 p번째 원소까지의 합을 알려준다.

즉 point update & range query를 로그시간에 수행한다.

이를 조금만 응용하면 range update & point query 모드로 바꿀 수 있다.

원래 배열을 a라고 하고, 배열 b[x] = a[x] - a[x - 1] 이라고 정의해보자.

그러면 이제 a의 입장에서, a[x]는 b[x] + b[x - 1] + ... 즉 누적합이 된다.

이제 두 기능을 b에 대고 수행한다고 생각해보자.

1) update(p, v)

-> 예를 들어 update(3, v)라면, a[1]과 a[2]는 가만히 있고, a[3]부터 v씩 늘어난 것이다. 왜냐하면 b의 정의 때문에.

따라서 [from, to] 구간을 v만큼 증가시키고 싶다면, update(from, v) 와 update(to + 1, v) 두 번으로 배열 a를 다 조질수 있다.

2) query(p)

-> b[1] + b[2] + ... + b[p] = a[p] 이니까, a의 p번째 원소 값을 구하는 쿼리로 변경되었다.

이처럼 펜윅트리는

1) point update & range query

2) range update & point query

3) range update & range query

총 3가지 모드를 제공한다. 3번째 모드는 차후에 설명하는 것으로.. ㅎㅎ

이제 트리에 가해지는 쿼리를, 펜윅트리에서 로그시간에 수행할 수 있게 되었다.

하지만

1) 모든 쿼리를 수행해보면서 매번 모든 가수가 평균 점수를 넘는지 확인

2) 모든 가수마다 쿼릐를 수행해보면서 언제 평균 점수를 넘는지 확인

어떤 방법으로도 N * K * log(N)으로 시간이 오바된다.

4. 시간 줄이기

포인트는 가수들의 평균점수는 쿼리들이 수행되는 동안 절대 내려가지 않는다는 점이다.

따라서 단조증가하고, 이는 이분 탐색을 떠올리게 해준다.

하지만 가수마다 이분 탐색으로 조지는 것 보다, 모든 가수들의 구간을 줄여나가는 방법이 있단다. -> 병렬 이분 탐색

이 알고리즘의 구조를 보면, 가수마다 구간이 있고 구간의 중앙값은 타겟이 된다.

이제 쿼리를 순차적으로 수행할 텐데, 현재 수행하는 쿼리가 타겟과 같다면 그 가수는 구간을 반으로 줄일 수 있다.

쿼리를 전부 수행하고 나서, 구간이 변화한 가수가 있다면, 다시 처음부터 쿼리를 수행하는 짓을 반복한다.

말로는 머가 개선된건지 모르겠지만, 나중에 코드로 보면 더 빠르겠구나 할 꺼다.

A를 6분에 풀고

B에서 너무 시간을 오래 잡아먹었다.

관찰결과, (x,y)에서 |x|==|y| 이거나 절대값 차이가 홀수냐 짝수냐에 따라 다 다르길래 마음만 급해서 구현실수하구....

C에서 너무 수학적으로 생각하느라 또 시간 소비.

D는 그나마 빨리 풀었다. 그리디하게 생각한게 적중.

다시 C로 돌아와서 허어ㅓㅓㅓㅓㅓ 하다가 끝나버렸다.

문제의 C문제는 

0이 아닌 자릿수가 3개 이하인 자연수 = Classy number 가 [L, R] 구간에 몇 개나 있는지 세는 문제였다.

조합으로 수식 세우고 구현하면 되기도 하지만, 나처럼 구현상의 실수를 할 수 있다.

그래서 미리 Classy number를 다 구해놓고, (10^18 이하에서) 이분탐색으로 구간 상의 개수를 세면 되는 문제였다고 한다. ㅎㅎ

솔직히 이런 유형의 문제를 처음봤다. 미리 다 구해노코 빠박하는게 좀 더 컴퓨터적인 사고인거 같은데,

수학적으로만 접근 한걸 보면 백준만 허구헌날 해서 그런가 싶기도 하고...

다음에 길게 길게 설명하기로 하고,

문제 풀면서 느낌 감상만 먼저 옮기려고 합니당.

학교 수업시간에 배운 두번의 DFS로 SCC들을 구하는 방법과,

한 번의 dfs로 SCC들을 구하는 방법을 비교해 봤는데, 확실히 후자의 방법이 두 배 정도 더 빨랐다.

두 번의 dfs는 간단해서 짜는데 빠르게 짤 수 있는 반면, 한 번의 dfs는 이해한지 얼마 안돼서 그런가 코드가 길긴하다.

간단히 설명하면,

전자의 방법은 먼저 dfs를 돌긴하는데 finish되는 순으로 stack에 push 해두었다가,

pop하면서 역간선 그래프에 대해 dfs를 다시 돌면서 scc로 묶는 방법이다. (a->b로 갈 수 있으면, b->a로도 갈 수 있어야 한다.)

후자의 방법은 dfs 트리를 활용하는데, 방문하는 순서대로 노드들에게 번호를 매기면서 stack에 push하고, 지금의 dfs가 어떤 노드로부터 

시작되었는지를 활용하여 scc로 묶는 방법이다. 후자는 확실히 코드를 봐야 이해가 빠르다.

Strongly Connected Component

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

1. 2150 은 기본 문제로 scc들을 구하는 문제였다.

도미노

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

2. 4196은 scc를 구한 다음에 더 풀어야 되는 문제였다.

scc내에선 하나만 무너지면 다른 노드들도 다 넘어진다. 따라서 그래프를 scc들 끼리의 그래프로 재편집한다음에,

scc들의 indegree를 계산하고, indegree가 0인 scc들의 갯수를 세면 풀 수 있다.

ATM

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

3. 4013은 scc를 구하고 indegree를 구하고 더 풀어야 되는 문제였다.

scc를 구할 때 각 scc들의 value 합을 구해놓고 scc들 끼리의 그래프로 재편집해야 한다.

이후 indegree를 계산한 다음에, 위상정렬로 출발점이 속한 scc에서 레스토랑이 있는 scc까지의 최대 value 합을 각각 구하면 된다.

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

예산

아 parametric search 구나

라고는 빨리 알았지만, 이분탐색의 늪에 빠졌다가 뭔가 깨달음을 얻어서 여기에 옮기고자 한다.

k번째 숫자(https://www.acmicpc.net/problem/7469)를 parametric search로 풀고, 이 문제도 parametric search로 풀었다.

전자는

후자는

와 같다.

전자의 경우 mid가 성공했다면, 그 값을 포함한채 오른쪽을 좁혀야 하고,

(k번째 숫자를 찾아야 하므로, 더 큰 값은 의미가 없고, mid는 정답일 수 있으므로 버리면 안된다.)

후자의 경우 mid가 성공했으면, 그 값을 포함한채 왼쪽을 좁혀야 한다.

(최대 예산액을 찾아야 하므로, 작은 값은 의미가 없으며, mid는 정답일 수 있으므로 버리면 안된다.)

따라서 left와 right로 mid를 정하는 기준이 달라지는데, 이유를 말로 하긴 복잡하니까 그림으로 설명해보겠다.

mid 를 (left + right) / 2 로 하느냐, (left + right + 1) / 2로 하느냐의 차이점은, (성공했을 때 좌우를 변경하는 로직이 완벽했을 때)

결국엔 range가 2일 때 선명하게 드러나는데,

이번 예산 문제의 경우 mid 를 (left + right) / 2 로 하고 성공했을 경우, 

위 그림과 같이 무한루프에 빠지게 된다. 

반대로 k번째 숫자 문제는,

mid 를 (left + right + 1) / 2 로 한다면 성공했을 경우 무한루프에 빠지게 된다.

따라서 좌우를 버리는 로직을 완벽히 세워놨다면, 모든 parametric search를 위 두 케이스 중에 알맞은 케이스로 풀면 된다

라는게 내린 결론인데, 평소 while(left <= right)인 코드를 많이 봐왔던지라 차이점이 궁금해지긴 한다.

정파말고 사파식 공부를 하는 중이라 깊이가 모자른걸 요새 크게 통감하고 있다 ㅎㅎ;

풀 코드는 다음과 같다.

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

정수 배열에 대해, 각 인덱스로 자신이 부분수열의 끝이고 길이가 L인 부분수열을 만들 수 있다.

각 부분수열의 최소값을 구해야 한다. (정수 배열의 길이 <= 오백만)

처음엔 세그먼트 트리 풀이만 생각이 났다. 근데 오백만이라 nlogn만 해도 오억이라 시간안에 풀 수 없었다.

복잡한 세그먼트 트리로만 헤매고 있었던 이유는,

각 부분수열의 최소값을 구할 때, 전 인덱스로 구한 최소값을 활용하는게 어려웠기 때문이다.

최소값이 부분수열의 맨 처음에 있었다면, 이번에 최소값을 구할 땐, 이전의 최소값은 구간에 포함이 안되고 새로 구해야 했다.

이러한 최악의 경우는 계속 일어날 수 있고(오름차순 정렬된 배열이라면), 좋은 풀이가 아니었다.

결국 이렇게 최악의 경우에서, 다음으로 작은 최소값을 알고 있으면 해결할 수 있다.

이 최소값도 다시 구간에서 벗어날 수 있으므로, 최소값들 후보를 죄다 갖고 있으면 된다!

이러한 자료구조를 고민하다가 덱을 쓰기로 했다.

덱의 맨 앞은 최소값을 가지고, 뒤로 갈수록 다음 최소값 후보들이 이어진다.

따라서 덱의 front에선 최소값들을 활용하고, 뒤로는 최소값 후보들을 집어넣으면 된다.

작업후에는 L-i ~ i 까지 최소값들 후보들이 덱에 들어가 있을 것이다.

현실에선 사칙연산과 괄호가 포함된 수식을 중위 표기법으로 기술한다.

예를들어 3 + 4 와 같은 꼴이다.

하지만 3 + ( 4 - 7 ) * 8 + 3 * 4 와 같이 우선순위가 꼬여버린 수식은 컴퓨터가 알아먹기 힘들다.

하지만 수식계산은 연산 순서만 잘 정리되면 술술 풀린다.

목표는 숫자(피연산자)는 가만히 냅두고, 연산자들의 서열만 정리시켜주려는 것이다.

위 수식의 연산순서를 그래프로 나타내면 다음과 같다.

위 그래프를 중위순회하면 원래의 수식이 나온다. 위 그래프를 후위순회하면 후위표기법대로 기술된다.

3 4 7 - 8 * + 3 4 * +

우리가 보기엔 해괴한 수식이지만, 컴퓨터가 보기엔 앞에서 부터 계산만 하면 되는 편한 식이다.(괄호가 없다)

어떻게 계산 하냐면, 앞에서부터 보면서 연산자가 나오면 앞의 두 피연산자를 뽑아 연산하는 것이다. 다음과 같다.

1. - 때문에 4와 7을 뺀 -3을 기록한다.

2. * 때문에 (1)의 -3과 8을 곱한 -24를 기록한다.

3. + 때문에 (2)의 -24와 3을 더한 -21을 기록한다.

4. * 때문에 3과 4를 곱한 12를 기록한다.

5. + 때문에 (3)과 (4)의 -21과 12를 더한 -9를 기록한다.

6. 최종기록 -9가 결과다.

따라서 계산하는데 O(n) 걸린다.

따라서 중위식을 후위식으로 변환하는데 O(n)만 걸리면 아름다운 알고리즘이 될 것이다.

이제부터 중위식을 후위식으로 변환하는 과정을 설명하고자 한다.

하려는 짓은 결국엔 연산순서를 잘 일렬로 세워주는 것이다. 숫자는 앞에서 부터 잘 기억만 하면 된다.

아이디어는 다음의 생각들을 잘 섞으면 된다.

1. +와 -는 당연히 *와 /보다 나중에 계산해야 한다.

2. (는 수식안에 새로운 수식이 생기게 한다.

3. )는 그 새로운 수식을 닫는 역할을 한다.

4. 따라서 곱하기 > 더하기 > 괄호질로 연산 우선순위가 높다. ( 다음을 생각해보자. (1+2)*3 ) 

이제 이 아이디어로 중위식을 앞에서부터 보면서 후위식으로 바꿔보자

1. 현재 문자가 ( 라면 스택에 ( 를 넣어준다. 새로운 수식이 언제 시작되었는지 기억하기 위함이다.

2. 현재 문자가 ) 라면 수식이 끝난 것이다. 스택에 ( 가 보일 때 까지 파내면서 후위식에 기록한다. ( 는 버린다.

괄호질은 서열이 제일 낮기때문이다.

3. 현재 문자가 연산자라면, 서열을 정해야 한다. 스택에 나보다 쎈 연산자가 있다면 파내고 후위식에 기록한다.

나와 우선순위가 같은 연산자라면, 수식의 왼쪽이 우선순위가 더 높으므로 사실 나보다 쎈 연산자다. 파내고 기록해야한다.

4. 숫자라면 그냥 후위식에 기록한다.

숫자가 여러자리라면 고통스럽겠지만 역량에 맡긴다. 코드를 보면서 이해해보자.

calc 함수는 문자열을 받아 계산결과를 리턴해준다.

화학식량

2 -> 임시변수에 숫자를 곱해 TOP에 더해준다. 다만 1과 4에서 이미 TOP에 한 번 더해줬으므로 1만큼 덜 곱해야 한다

소스로 옮기면 다음과 같다.

외계인의 기타 연주