AtCoder Beginner Contest 296 후기 (ABC 296 3솔)

D번이 생소한 정수론 문제로 나와서 많이 말렸다. E번은 확실한 아이디어까지 냈는데 푸는 데 실패함

 

추가로, Atcoder 문제의 난이도를 대략적으로 알려 주는 사이트를 발견했다.

https://kenkoooo.com/atcoder/#/table/

AtCoder Problems

 

여태까지 풀었던 문제들과 풀지 못했던 문제들을 보면 이러하다

이에 대한 분석은 이러하다

1. 민트 문제까지는 어찌저찌 풀 수 있다는 생각이 든다
2. 정수론에 약하다. 정수론은 Green난이도도 버겁다.
3. 여타 코딩테스트에서는 bfs나 그리디가 흔하게 출제되었지만, 앳코더는 그렇지 않고 정수론/기하학/수학 문제가 오히려 많이 보인다
4. 난이도 분포를 보면, 풀수 있든 없든 F까지는 문제를 살펴볼 필요가 있다

그런데 조금 고민이 되는 부분이다. 내가 알고리즘을 파는 건 취미생활의 영역이지, 내 진로로 연결될 가능성은 적다고 생각한다.

정수론, 기하학, 세그먼트 트리 등 중상급 난이도의 알고리즘을 공부하는 것이 그만큼의 가치가 있을까? 라는 고민이 든다

그래도 당분간은 계속 공부해 볼 예정임

 

아무튼 리뷰

 

A - Alternately

문자열 / 1차원 배열

A - Alternately

M이나 F가 연속으로 나오는 순간을 탐지하기 위해 a라는 변수를 사용했다.

 

B - Chessboard

2차원 배열 / 문자열

B - Chessboard

문자열을 입력받고 *이 등장한 인덱스를 알파벳과 숫자로 나타낼 수 있으면 된다

 

C - Gap Existence

set 쓰면 그냥 풀림

C - Gap Existence

원하는 조건의 숫자가 set안에 있는지 확인하고, 없다면 그 숫자를 set안에 넣어 놓으면 된다

 

 

D - M<=ab

정수론

D - M<=ab

위의 코드는 정답이 아니고 마지막으로 제출한 코드이다

 

풀이의 근거는 이러하다.

M<=N*N인 경우에, M부터 (sqrt(M)+1)^2 까지 완전탐색해 가능한 경우를 찾아내면 된다고 생각했으나,

 

보다시피 WA와 TLE가 발생하므로 이 방법으로는 답을 찾을 수 없었음

 

정수론 문제를 풀다 보면 자꾸만 이런 생각이 든다

아!! 또 나만 모르는 어떤 잘 알려진 정수론 공식이 있구나

이 문제의 경우 코시-슈바르츠 부등식처럼, 항상 성립하는 어떤 부등식 조건이 있고 그것으로 답을 찾아내는 문제이고 난이도도 높을 것이라고 예상함

 

근데 보니깐 난이도가 그리 높은 문제는 아니더라

내가 수학에 약한가 보다

 

E - Transition Game

사이클 판별, 게임 이론

 

근데 게임 이론이라기엔 너무 쉽고 그냥 사이클만 찾으면 된다

시간만 더 있었으면 이 문제는 무조건 풀었다

 

문제의 조건 :

N번의 라운드가 있음.

아오키는 1~N사이의 숫자를 선택하고 그만큼 숫자를 바꿔치기?하는 과정을 거침

타카하시는 마지막에 자신이 고른 숫자의 인덱스? 에 위치하면 승리함

아오키와 타카하시는 게임 이론 문제의 흔한 조건처럼, 항상 최적의 수만을 생각함

 

이때 타카하시가 승리하기 위한 조건은, 목표로 하는 숫자에 사이클이 형성되는 것이다. 아오키가 1~N사이 어떤 숫자를 고르든 사이클이 생기기만 하면 타카하시는 목표로 하는 인덱스로 갈 수 있다

그러니 1차원의 parent[N] 배열을 만들고 유니온파인드를 이용해 그녀석에 사이클이 형성되는지만 판단하면 타카하시가 몇 번의 라운드를 승리할 수 있는지 알 수 있다.

 

 

---

 

몇 주간 앳코더를 꾸준히 하면서 나 자신에 대한 데이터가 충분히 모였다고 생각한다.

부족한 부분과 향상시켜야 할 부분, 목표로 할 레벨을 대략적으로 정할 수 있다

 

우선의 목표)

앳코더 민트 --> 에 도달하려면 쉬운 블루 문제까지는 풀 수 있어야 함

1. uf와 bfs dfs, gcd, 분할정복 pow의 템플릿화
   >> 어쩌피 다 아는 부분인데 템플릿화를 통해 문제 푸는 시간을 줄이고 다른 문제에 시간을 더 투자하기
2. Atcoder D~E 정수론 빈출 패턴 분석/백준 수학문제 풀이 및 <블로그에 잘 정리>
3. 다음 Atcoder부터는 A~F번 문제까지 읽어보기