PS/공부
-
23.06.04 - 23.06.10 공부 (그래프 파트 3 : MST)PS/공부 2023. 6. 10. 18:37
이번 그래프 파트는 '최소 신장(스패닝) 트리'라 불리는 MST이다. 바킹독 MST 문제집은 다 풀어놓은 상태라 라이 블로그 추천 문제집을 활용하였다. https://www.acmicpc.net/workbook/view/5057 문제 수가 그렇게 많지 않은데 공부 기간이 저렇게 길게 적혀있는 이유는.. 9373번 덕분이다. 나머지 문제는 하루만에 다 풀었는데, 9373번은 없는 시간 쪼개가며 고민하다보니 조금 오래 걸렸다. (사실 그마저도 풀어내지 못해서 해설을 봤다 ㅠ) 1. 백준 1922번 - 네트워크 연결 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. w..
-
23.06.02 - 23.06.03 공부 (그래프 파트2 : 데이크스트라)PS/공부 2023. 6. 4. 13:04
이번 파트는 [데이크스트라 알고리즘]이다. 역시 바킹독 문제집을 이용했다. 이전에 풀어놓은 게 좀 있어서 저번 [플로이드 알고리즘] 때보다 문제 수는 적지만, 난이도 분포는 살짝 더 높다. https://www.acmicpc.net/workbook/view/10433 1. 백준 1854번 - K번째 최단경로 찾기https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에www.acmicpc.net사실 이 문제의 접근은 예전부터 알..
-
23.05.29 - 23.05.31 공부(그래프 파트 1 : 플로이드)PS/공부 2023. 6. 1. 23:02
아직 남은 대회 후기가 몇 개 있긴 한데, 아무래도 조금 밀릴 듯 싶다.. 글 한 편 적는 데에도 적지 않은 노력이 필요하다는 것을 알아버렸기 때문에.. 종만북에서 그래프 파트를 파고 있는 중이다. 플로이드, 데이크스트라, 벨만-포드, 아직 조금 부족하지만 플로우까지 계속해서 반복 공부하고 있다. 배운 내용을 문제에 적용해볼 필요를 느껴서 오랜만에 바킹독 문제집을 정주행 해보기로 했다. 첫 파트는 [플로이드 알고리즘]이다. https://www.acmicpc.net/workbook/view/103181) 13168 내일로 여행 - UCPC를 위해 아껴놓기로.. 2) 13314 플로이드에 오타가? - 폰에서 cpp 파일을 열기 어려워서.. 1. 백준 17182번 - 우주 탐사선https://www.acmi..
-
23.05.02 - 23.05.03 공부 (2/2)PS/공부 2023. 5. 5. 10:40
그리고 그 외 잡다한 것들. shake! 2018 B번. 변신 이동 게임https://www.acmicpc.net/problem/15906 15906번: 변신 이동 게임첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에www.acmicpc.net알고리즘 분류로는 '데이크스트라'로 되어 있지만, 단순 bfs로도 충분히 풀 수 있다. [벽 부수고 이동하기] 시리즈(ex. https://www.acmicpc.net/problem/2206)에서 쓰이는 테크닉을 사용하여 보자. 일반 모드로 이동하는 방법은 기존 bfs 돌리듯이..
-
23.05.02 - 23.05.03 공부 (1/2)PS/공부 2023. 5. 3. 22:51
군휴가가 얼마 안 남았던지라, 개인 대회 연습을 좀 해봤다. 현실적으로, 지금 내 수준에서 입상을 노려볼만한 ps/알고리즘 대회는 shake!(경인지역 6개대학 연합 프로그래밍 대회)라는 생각이 들어서 2019 본선, 2020 본선을 쭉 돌아보았다. shake! 2019 A번. 패턴https://www.acmicpc.net/problem/17300 17300번: 패턴안드로이드 OS에는 휴대폰의 잠금을 풀기 위한 방법 중 패턴을 암호로 사용하는 방법이 있다. 3×3의 9개 점에 번호를 매겨 그중 일부로 하나의 수열을 만들었을 때, 수열에서 인접한 번호의 점을 www.acmicpc.net단순 구현. 다음의 두 가지 조건에만 유의하면 된다.수열의 어떤 수가 두 번 이상 나타나서는 안 된다.두 점(수열에서 연속..