기타(비트마스크, 누적합, 모름)

● (유형은 뭔지 모르겠음, 리트코드 2170) https://leetcode.com/contest/weekly-contest-280/problems/minimum-operations-to-make-the-array-alternating/

일단 매우 아깝게 못맞춘거, 그리고 정답률이 무려 14~15%밖에 안되는 엄청난 문제임... 살면서 본 문제 중 가장 정답률이 낮음.

나의 경우는 시간 초과로 못맞췄는데, if문이 너무 많이 들어간게 문제였음. 다른 풀이들이랑 비교했을 때 좀 미세한 차이로 시간 초과에 걸린 것으로 보임. 글고 미처 알지 못한 것 중 하나는, 예를 들어 홀수번째 배열에 3 3개, 2 2개, 1 1개 이렇게 있고 짝수번쨰도 이와 똑같은 구성을 갖고 있다 치면, 홀과 짝 둘다 못쓰는게 아니고 둘중 하나만 양보하면 된다는 점. 마치 홀, 짝의 최대인 원소가 모두 3이고 count 값만 다를 때 더 작은 개수의 3을 갖고 있는 애의 값만 다시 정하면 되는 것처럼 말이다. 상상력이 부족했다...

카운터 활용하는 방법(풀이)도 공부하자!(2170_2) https://www.daleseo.com/python-collections-counter/

 

 

리트코드 2220: https://leetcode.com/contest/biweekly-contest-75/problems/minimum-bit-flips-to-convert-number/

비트마스크다. 나도 bit_count() 함수 찾아내갖고 이거 써서 한방에 풀려했는데 계속 없는 함수라 나오고 알고보니 파썬 3.10 부터 되는 모양이더라고.? 하지만 진법 변환이라고 생각하고 나올 가능성이 있는 문제이며 그때 bit_count() 를 안쓰고도 효율적으로 풀 수 있어야겠지? 그 풀이를 공부해라.

 

 

- 11660: https://www.acmicpc.net/problem/11660

dp+누적 합 유형 문제. 영역에서 a-b-c+d 식의 연산을 해서 답 구한다는 아이디어는 맞춤. 그러나 그 원소의 누적합 자체를 뭘로 구할지가 어리둥절. for 및 sum 함수는 시간 느릴 것 같은... 그렇다고 현재 내 상태로 시간 복잡도가 명확히 계산되는 것도 아니었다. 그래서 딴 풀이 보니 이걸 바로 dp로 구하는 것이더군. 구하고 나면 답변 출력 식에서는 또 인덱스가 그렇게 헷갈림. 거기서 자꾸 틀려서 제출 포기하고 여기에 메모 한 거임. https://jominseoo.tistory.com/101

 

 

- 20438: https://www.acmicpc.net/problem/20438

왜 누적합으로 구해야 하는지? 어떤 부분이 누적합 개념이 적용되는 건지를 도저히 캐치할 수 없어서 풀이 보고 이해함.

M번에 걸쳐서 답을 구하도록 묻기 때문에, 누적합으로 범위 내 구간에 대해 답을 미리 구해놔야 하는 거였음.

https://dreamtreeits.tistory.com/161