ABC 337 D번 복기 - 2차원 배열에서 행,열로 연속한 O의 개수를 빠르게 세는 방법(sliding window + prefix sum)

D - Cheating Gomoku Narabe (atcoder.jp) D - Cheating Gomoku Narabe AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp . o x로 이루어진 2차원 배열에서 .을 o로 바꿀 수 있다. 이 때 행이나 열로 연속한 o의 개수가 k개가 되도록 최소로 바꾸는 횟수 처음에 DFS로 o의 좌표에서 시작해서 .을 o로 바꿔서 해보다가 당연히 시간초과났고 그러다가 행이나 열 각각에서 모두 조사해보면 된다는 생각이 들었다 여기까지는 좋았음 행 한줄에서 어떻게 .을 o로 바꿔야 연속한 o의 ..

• format_list_bulleted Atcoder
• · 2024. 1. 21.
• textsms

ABC 335 C번 복기 - 놓치기 쉬운 deque를 사용할 때 주의할 점(deque indexing is O(N)) + 배열과 연결리스트 접근 시간복잡도 차이

1. 문제 C - Loong Tracking (atcoder.jp) C - Loong Tracking AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 1번부터 N번까지 좌표가 있고, 1번 좌표는 쿼리에 의해 움직이게 된다. 1번 좌표가 움직이면, 2번,3번,4번,...,N번 좌표는 각각 1번,2번,3번,...,N-1번 좌표가 된다. 쿼리가 20만개이고 좌표수도 최대 100만개라 단순하게 접근하면 시간초과를 받을 것인데 그림으로 생각해보면 접근법을 생각할 수 있다 처음에 배열에 1번부터 N번까지 좌표가 있는데, ..

• format_list_bulleted Atcoder
• · 2024. 1. 7.
• textsms

ABC 333 D번 복기 - 리프 노드부터 특정 노드까지 최소로 지우는 법

1. 문제 D - Erase Leaves (atcoder.jp) D - Erase Leaves AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 리프 노드부터 차례대로 지울 수 있을때, 1번 노드를 지우기 위해서 최소로 지워야하는 노드의 개수는 몇개인가? 평소에 골드3정도 트리 DP 문제를 연습했더니.. 해법이 보이긴 하더라 리프 노드라는 것은 자식이 없는 노드인데, 목표로 하는 노드가 1번 노드니까, 1번 노드를 루트라고 생각한다면.. 다음과 같은 트리는 다음과 같이 바꿀 수 있는데, 이런 경우에 리프 노드부터..

• format_list_bulleted Atcoder
• · 2023. 12. 17.
• textsms

ABC 332 D번 복기 - 행,열 바꿔서 다른 2차원 배열과 똑같이 만드는법(BFS가 된다고?)

1. 문제 D - Swapping Puzzle (atcoder.jp) D - Swapping Puzzle AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 비슷한 문제들이 그리디로 풀려가지고... 숫자 다르면 무조건 바꾸는 그리디인가도 생각해봤는데.. 제한이 H,W가 5 이하라서 완전탐색이 가능할 것 같다고 생각을하고, 생각까진 하더라도 완전탐색을 어떻게 해야할지.. 근데 그 전에 문제부터 제대로 못읽었던것도 문제.. Choose an integer i satisfying 1≤i≤H−1 and swap the i..

• format_list_bulleted Atcoder
• · 2023. 12. 11.
• textsms

ABC329 F번 복기 - 당연하지만 어려운 '작은 집합에서 큰 집합으로 합치는 테크닉(smaller to larger)' 배우기

1. 문제 다음과 같은 문제를 생각해보자. 크기가 1인 집합이 N개 있고 각 집합은 1부터 N까지 각각을 원소로 갖는 집합이다. {1}, {2}, {3}, ... , {N} 이 집합을 합치는 연산을 반복하여 최종적으로 {1,2,3,...,N}이 되게 하고 싶다. 생각할 수 있는 방법은 {1}을 {2}에 넣어서 {1,2}로 만들고, {1,2}를 {3}에 넣어서 {1,2,3}으로 만들고.. {1,2,3}을 {4}에 넣어서 {1,2,3,4},...를 반복하면 {1,2,3,4,..,N}이 된다. 결국 i번 집합을 i+1번 집합에 넣는 과정을 N-1번 반복하면 되는 것이다. ------------------------------------------------------------------------------..

• format_list_bulleted Atcoder
• · 2023. 11. 20.
• textsms

ABC 328 C번 복기 - 문자열에서 누적합을 떠올려야 할 때

1. 문제 C - Consecutive (atcoder.jp) C - Consecutive AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 매번 부분 문자열을 찾고, 거기서 연속해서 발생하는 문자의 수를 찾으면 당연히 시간초과가 날 것인데, 주어진 문자열에서 0번부터 어떤 위치 i까지 나타나는 연속해서 발생하는 문자의 개수를 누적합 배열로 미리 구해놓는다 예를 들어 mississippi라고 한다면, count = [0]*(n+1), before = ''으로 초기화해두고, i = 1부터 n까지 순회해서, s[i-..

• format_list_bulleted Atcoder
• · 2023. 11. 12.
• textsms