전체 글
-
-
20230811 업다운 랜디Study/PS 2023. 8. 11. 20:47
s#100.. !solved_by:p_jun *P3 30분 3문제 P3 13504 XOR 합 패스 그리디, DP, 세그 트리 등 고민 했는데 쉽지 않다 트라이가 정해인데 모르는 알고리즘이다 공부하고 추후 작성하자 P4 20532 정점 간 통신 네트워크 - 6분 3초 dfs를 잘 돌리면서 개수를 세주면 된다 약수의 개수는 많지 않으니 그냥 다 세주자 중복된 수는 배수, 약수에서 공통으로 세지니 빼줘야 한다 int를 넘을 수 있다는 것에 유의하자 더보기 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long..
-
20230808 업다운 랜디Study/PS 2023. 8. 9. 02:46
s#100.. !solved_by:p_jun *P5 30분 2문제 오늘은 놀아버려서 2문제만 풀었다 P5 5551 쇼핑몰 + 2분 6초 문제를 보자마자 다익스트라로 최솟값에서 어떻게 잘하면 될거 같은데... 라는 생각이 들었다 고민하다 거리를 반으로 나누어 두는 방식으로 구현해서 맞았다 그런데 처음 맞은 풀이는 인덱싱 실수를 해서 틀려야 하는데... 데이터가 약한가보다 더보기 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; #define MOD 1000000007 const ll INF..
-
20230807 업다운 랜디Study/PS 2023. 8. 7. 18:15
s#100.. !solved_by:p_jun *g1 30분 3문제 G1 1242 소풍 +10분 6초 이건 억까지 15분 쯤 풀이를 세우고, 25분 쯤 구현 완료해서 제출 했다 제출을 계속 하는데도 틀리거나, div by zero, overflow가 떠서 0으로 나눌 부분이 대체 어디있을지 계속 찾앗다 K가 N보다 작다면서요.... 사실 예제를 안 보고 제출한 내 잘못이 크다 ㅎ 무지성 제출하는 걸 고쳐야하나 대회에선 안 그러니 괜찮을지도? 더보기 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long l..
-
20230806 업다운 랜디Study/PS 2023. 8. 6. 21:56
s#100.. !solved_by:p_jun *g4 30분 3문제 G4 16472 고냥이 - 7분 두 포인터 좀 헷걸려서 시간을 많이 날렸다 더보기 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; #define MOD 1000000007 const ll INF = 987654321; const int MX = 500005; int arr[30]; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int n; cin >> n;..
-
20230805 업다운 랜디Study/PS 2023. 8. 5. 20:19
s#100.. !solved_by:p_jun *g5 30분 3문제 G5 16925 문자열 추측 + 22분 19초 내가 너무 싫어하는 구현, 문자열 문제 접미사와 접두사 S, P 인걸 반대로 출력해 시간을 너무 날렸다 맞왜틀로 시간만 태웠다 그냥 나온대로 구현하면 된다 더보기 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; #define MOD 1000000007 const ll INF = 987654321; const int MX = 500005; int n; vector v; int ..
-
3. 강화 학습으로 사과를 지워보자Project/Fruit Box 2023. 3. 27. 00:35
강화학습과 함께라면 높은 점수가 가능하지 않을까? 이미지를 저장하기엔 용량이 부족할 것으로 예상되어 txt로 배열을 처리해서 저장하고자 하였다 pyautogui를 이용하여, 판을 읽어서 txt에 저장 새로 고침 후 저장을 반복하였다 그 게임판에서 나오는 최대 점수를 알아내기는 어렵고 또한 방법이 항상 하나만 있기는 어렵다고 생각하여 지운 사과 개수 최대화로 무지성 강화학습을 돌려보았다 이때 DQN알고리즘을 가져와서 사용하였다 현재의 게임판을 state Q로 하고, 점수를 높이기를 목표로 학습을 돌렸다 이건 검색하면 그냥 나오기에 코드는 패스하겠다 결론만 알아보자 생각보다 점수 상승이 크지 않다 정확히 말하면, 평균 점수는 높은 것 같다는 생각이 들었다 학습된 판들을 바탕으로 돌린 결과, 무지성 삭제보단 ..
-
2. 전략적으로 사과를 지워보자Project/Fruit Box 2023. 3. 27. 00:28
임시 저장한 글을 등록하는 걸 잊어 한번에 풀어버리자 전략을 찾기 위해 열심히 게임을 해봤다 게임을 해보다 보니 더 나은 전략이 생각났다 해당 패턴은 직접 찾기 어려우니 아래 표에 있는 예시로 살펴보자 9 1 3 3 9 1 위와 같이 사과가 있다고 생각해 보자 딱 보니 (1, 9) 쌍을 지우는 모습이 보인다 그런데 그냥 무지성으로 지우면 안 된다 9 1 3 3 9 1 위와 같은 경우를 지운 경우를 생각해 보자 주변에 사과에 따라 다르겠지만, 왼쪽 위와 오른쪽 아래 쌍 제거가 불가능하다 아래와 같이 제거하는 경우가 유리하다 9 1 3 3 9 1 위와 같이 지운다면 가능한 모든 사과를 지울 수 있다 몇몇 패턴을 더 찾았는데, 한 가지만 더 소개해주면 아래와 같은 T자 형이 있다 9 1 1 3 9 3 9 1 ..