https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 자료구조를 사용하는 그리디 문제이다. 우선해야하는 조건이 2개가 엮여 있어서 난이도가 있는 문제였다. 나는 그리디 알고리즘 강의를 다시 복습해서 보고나서 아래와 같은 사고로 문제를 풀었다. 결국 그리디도 최적해를 구하는 알고리즘 중 하나인데, 이 문제에서 구해야하는 것은 '보석 가치 합의 최대'이다. 그렇다면 일단 보석의 가치만 놓고보면..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 오늘 백준을 들어가보니 AC Rating이 갑자기 50정도 늘어나있었다. 아무 문제도 푼게 없는데 무슨 일인가 싶다...ㅋㅋㅋ 얼떨떨한 기분으로 푼 문제, '도시분할계획'이다. 이 문제는 MST 응용문제인데, 두 MST의 합을 최소로 해야한다는 점이 조금 까다롭게 느껴졌다. 처음에는 두 MST에 속할 노드를 백트레킹이나 조합으로 골라서 매번 MST를 구해야하나..
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 단순 BFS 문제를 구현하기 어렵게 내면 이렇게 나올 수 있다는 걸 보여준 문제이다.. 2048과 비슷하게 그냥 상하좌우 이동을 구현하고, 모든 경우의 수를 세면 된다. 각 이동마다 가능한 경우의 수가 상하좌우 4방향 이고, 10번을 넘는 이동은 의미가 없으므로 진짜 의미로 모든 경우의 수는 4^10 = 약 100만 의 경우의 수겠지만, 이 경우의..
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 보다는 쉬웠습니다..
