https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 개인적으로 solved.ac 난이도에 비해 힘들게 푼 DP 문제이다. 이 문제는 1가지만 떠올리면 정말 정말 쉽게 풀린다. 현재 문제에서 요구하는게 '없애야 하는 전깃줄 개수의 최솟값'이다. 하지만 전체 전깃줄의 개수가 고정되어 있다는 점에서 이를 뒤집어 생각하면 '남겨야 하는 전깃줄 개수의 최댓값'을 구해서 이 문제를 풀 수도 있다. 이렇게 발상의 전환만 성공했다면, 이 문제는 단순한 LIS 문제로 바..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이 문제는 그래프 탐색 문제를 조금 꼬아낸 문제이다. 제일 나이브한 풀이는 각 벽에 대해 BFS를 수행하는 것인데, 아무리 봐도 이건 시간 초과 풀이이다. 전체 영역이 최대 100만 칸짜리 2차원 배열인데, 이를 중복해서 순회하면 시간 초과가 안날 수 없다. 2차원배열을 한번만 순회하여, 그 결과를 이용해 답을 도출해야 한다. 그래서 나는 비어있는 영역에 대해 BFS를 수행하..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048 게임의 타일 이동을 구현하는 문제이다. 최대 이동 횟수가 5회로 매우 작은데, 한번에 이동에서 선택할 수 있는 경우의 수가 '상하좌우' 4가지 이므로 모든 경우의 수가 4^5 = 1024 이다. 모든 경우의 수를 저장하기 위해서 각 경우마다 최대 20*20 사이즈 판을 순회해야 하므로 한 경우의 수당 연산횟수는 400이다. 1024 * 400 은 굳이 계산해보..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 여러가지 방법으로 풀 수 있는 세 용액 문제이다. 나는 처음에 이분탐색을 시도 했다가 막혔는데, 구현을 쓸데없이 복잡하게 하다가 실수를 했던 것 같다. 2시간 고민하다가 다른 이분탐색 풀이 알고리즘을 보고 수정하여 맞았다. 이 문제를 투 포인터로 풀 수 있겠다는 생각까진 해봤는데, 구체적으로 어떻게 투 포인터를 써야할 지 떠오르지가 않았다. 그렇게 공부하여 알게된 알고리즘이 ..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 스티커 문제를 발전 시킨다면 이 파이프 옮기기 문제가 될 것 같다. 좋은 DP 연습문제이다. 처음에는 당연히 BFS를 이용해서 풀어야겠다고 생각했는데, BFS로는 최단경로를 찾아보기만 했지, 최단경로의 '개수'를 세어보진 않아서 백준님의 표현을 빌리자면, BFS의 형태를 모방한 브루트포스 풀이로 밖에 짜지지가 않았다. (그리고 이 방식은 당연하게도 시간초과를 받는다..) ..
https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 어렵지 않은 구현 & 시뮬레이션 문제. 꼼꼼하게 구현만 하면 풀 수 있다. 판의 사이즈가 크지 않기 때문에 문제에서 시키는 그대로 알고리즘을 짜서 돌리고, 그 결과값을 출력하면 된다. 이 문제를 풀 때는 2가지만 떠올리면 되었다. 1. 어떻게 확산을 겹치지 않게 시킬 수 있을지 2. 공기청정기의 확산을 어떻게 구현할 것인지 어떻게 확산을 겹치지 않게 시킬 수 있을지 가령, 문제의 조건과는 맞지 ..
생각보다 정말 많이 어려웠던 대회, 신촌지역 대학교 프로그래밍 동아리 연합 여름 대회(SUAPC 2021 Summer) 후기입니다. 플레티넘에서 군림하고 있던 팀원(버스기사) 두 분과 함께 대회를 준비하고 참가하게 되었습니다. 대회 준비 우선 전략을 짜기에 앞서 서로 자신있는 알고리즘에 대해 이야기를 나누었습니다. 한 분은 DP와 그리디에 집중해주셨고, 다른 한분은 올라운더이셔서(운전대 담당) 나머지 커버를 해주시고 저는 수학에 약해 그리디와 그래프, 구현 위주로 보자고 이야기를 나눴습니다. 대회 전에는 연습을 3번 했습니다. 경북대학교 대회 Gricon 2019, 2020 을 풀었는데, 2019는 생각보다 너무 쉬웠고, 2020은 2019보다 어려웠지만 SUAPC 2020 Winter 보다는 쉬웠습니다..
문제 소개 https://www.acmicpc.net/problem/17081 17081번: RPG Extreme 요즘 택희는 RPG 게임을 하고 있다. 던전을 헤쳐나가며 몬스터를 물리치고, 아이템을 모으고, 레벨 업을 하여 보스 몬스터를 물리치는 전형적인 RPG 게임이다. 이 게임은 N×M 2차원 그리드 위에서 www.acmicpc.net 지문 길이부터 정신이 나갈 것 같은 문제.. RPG Extreme 문제입니다. 윷놀이 문제도 굉장히 스트레스 받는 문제라고 생각했는데, 이건 진짜 장난아니네요 그래도 윷놀이보다 출력형식은 양심적이라 좋았습니다.. 또 이 문제를 만들면서 진짜 게임 만드는 기분이라 꽤 재밌기도 했습니다. 디버깅은 짜증났지만요 ㅋㅋ 문제를 풀기 위해 노트에 "요약해서" 정리한 위 문제의 ..
이 앱의 메인 기능인 악보에 대한 CRUD 구현이 모두 끝나서 주변 기능들을 구현하기 시작했다. 1. '좋아요', Key 조절 기능 추가 악보 뷰어 페이지에서 악보에 좋아요를 누를 수 있도록 버튼을 만들고, 마이페이지에서는 내가 좋아요 표시한 악보를 모아서 볼 수 있도록 했다. 이를 위해서 자동 스크롤 UI 위치를 하단으로 수정했다. 좋아요 버튼을 상단 앱바에 넣고 싶었기 때문이다. 그리고 하단에 자동 스크롤 UI만 덩그러니 넣으니 허전해서 마침 구현하려고 했었던 악보 키를 조절하는 버튼도 넣었다. UI가 나름 괜찮아졌다 ㅎㅎ 지금 악보는 내가 미리 좋아요 표시를 해두어서 색이 칠해진 하트 모양이다. 좋아요를 표시하지 않은 악보는 색이 칠해져 있지 않다. 지금 포스팅을 쓰면서 생각해보니 하트 색을 빨간색..
문제 소개 https://www.acmicpc.net/problem/20936 20936번: 우선순위 계산기 국렬이는 두 번씩이나 계산기 문제를 내놓고 또 계산기 문제를 냈다. 이대로라면 죽을 때까지 계산기를 우려먹을 생각이고, 당신은 귀찮지만 상금을 얻기 위해서 주어진 수식을 규칙에 맞게 계 www.acmicpc.net 2021 WINTER 신촌 연합 대학생 프로그래밍 대회(SAUPC)의 A번으로 나왔던 문제이다. 당시에는 너무 복잡해서 그냥 넘겨버렸는데, 아니나 다를까 플레티넘 문제였다ㅋㅋ 이번 SAUPC에서 구현문제를 담당하게 되어서 연습을 위해 풀어보았다. 전에 풀었던 뒤집힌 계산기와 비슷한 유형이지만, 좀 더 복잡하다. 알고리즘을 어떤 걸 써야할지 감이 잡힐 듯 말듯 해서, 결국 알고리즘 분류를..
