분류 전체보기150 5856 Party Invitations (C++) 이게... 왜... 됨? 어려운 문제를 풀고 싶지 않아서 과거의 USACO Silver 문제 중 티어가 낮은 문제를 하나 골라 풀었다. 정말 생각없이 읽고 생각하고 코드 짜서 제출했더니 정답이 나와서 당황스러웠다. BFS + set 을 통해서 친구 집합을 만들어놓고 k-1개의 조건이 충족된 경우 나머지 한 마리를 제거하며 queue에 push 해 BFS를 진행시켜주었다. 소 자체를 chk 배열에 확인하는 것이 아닌 cow group 단위로 chk 배열을 확인해주며 BFS를 진행할 수 있는가에 대해 고민해보면 좋을 것 같다. 시간 복잡도 : $O(n\log n)$ 소요 시간 : 5분? 아쉬운 점 머리가 너무 안돌아가서 시간 복잡도를 제대로 적었는지조차 잘 모르겠다. 전체적인 감상 USACO 문제는 티어에 .. 2022. 10. 6. 2162 선분 그룹 (C++) 재밌는 기하학 문제 하하하 풀이 선분 교차 알고리즘을 활용한다 이중 for문을 통해 두 선분이 교차하는지 선분 교차 알고리즘을 활용해 확인해준다. 만약 교차한다면 union 해준다 이때 집합의 크기를 알기 위해 sz 배열을 관리해주는 것이 중요하다. 만들어진 집합들의 개수와 최대 사이즈를 확인하여 출력한다. 선분 교차 알고리즘은 선분 교차 2 의 구현을 그대로 가져다 사용하였다. 시간 복잡도 : $O(n^2)$ 소요 시간 : 측정 불가 아쉬운 점 요즘 이런 거 구현하는 게 너무 귀찮다. 사춘기인가? 전체적인 감상 내가 나가는 대회에는 기하학 문제는 안 나왔으면 좋겠다. /* basic setup {{{ */ #include #define ff first #define ss second #define pb.. 2022. 10. 5. 9328 열쇠 (C++) 물 흐르듯이 한 구현에 실수 하나가 끼어서 많은 틀렸습니다를 받았다. 풀이 입력으로 주어지는 평면도를 둘러싸는 길을 추가하여 bfs를 진행한다. 모든 위치에 최대 한 번씩만 방문하기 위해 방문 시 vis 배열에 체크되어있거나 해당 위치가 벽이라면 continue 해주고 아니라면 로직을 진행하고. 해당 위치의 vis 배열을 1 처리해준다. 로직은 다음과 같다 위치 하나가 있을 때 해당 위치의 상, 하, 좌, 우를 탐색하여 준다. 상, 하, 좌, 우에 방문하였을 때 이동한 위치를 해당 위치라고 하자 해당 위치에 "문서"가 있다면 [출력 결과에 1을 더해준다] [queue에 해당 위치를 push 해준다] 해당 위치에 "열쇠"가 있다면 [queue에 해당 위치를 push 해준다] [열쇠를 얻었음을 col 배열에.. 2022. 10. 4. 17143 낚시왕 (C++) 맞왜틀의 지옥 시뮬레이션 풀이 상어에 대해 입력으로 주어지는 초기 정보 5개(r, c, s, d, z)와 상어가 낚시왕에게 잡혔거나 다른 상어에게 먹혔는지 확인하는 bool을 하나로 묶어 shark 구조체를 만들어 주었다 낚시왕이 m번 움직이며 잡을 상어를 확인한다. 초기 정보와 현재 몇 번째 이동인지 알고 있으면 현재 상어가 있어야 할 위치를 알 수 있다. 이를 토대로 mapper 배열에 상어의 바뀐 위치를 표시해주고 가까이 있는 상어를 잡아준다. mapper 배열을 확인하며 상어가 잡히거나 먹혔는지 확인해준다 사실 그냥 시뮬레이션 문제이기 때문에 크게 따로 풀이를 소개할만한 부분이 없다. 시간 복잡도 : $O(mc)$ 소요 시간 : 측정 불가 아쉬운 점 구현하는데 1을 11로 적어놓고 틀린부분을 찾지.. 2022. 10. 3. 5719 거의 최단 경로 (C++) 문제 티어를 가리고 풀었더니 플래티넘 문제가 평소보다 더 쉽게 풀리는 느낌... 풀이 코드의 전체적인 순서 1. m개의 간선을 입력받을 때 정방향 간선과 함께 역방향 간선 또한 입력받아준다. 2. 정방향 간선의 기본 그래프에 대해(문제에서 제시하는 기본 형태) dijkstra's algorithm을 사용하여 모든 정점의 시작노드로부터의 거리를 구한다 3. 역방향 간선을 통해 종료노드부터 조건이 있는 BFS 탐색을 하며 사용된 간선들을 used 배열에 표시해준다(모든 노드에 대해 새 번호를 부여해 최단 경로에 포함되는 간선인지 체크해줬다) 4. 정방향 간선의 기본 그래프에 대해 조건문으로 간선의 used 배열 체크와 함께 dijkstra's algorithm을 사용하여 모든 정점의 시작 노드로부터의 거리를.. 2022. 10. 2. 이전 1 ··· 24 25 26 27 28 29 30 다음
