![]()
문제 https://www.acmicpc.net/problem/27498 27498번: 연애 혁명 신촌고등학교 학생회장 기령이는 최근 학생들의 복잡한 사랑관계로 인해 고민이 많다. 학생들이 공부에 집중하지 못해 전반적인 성적이 하락하고 있는 것이다. 이에 기령이는 학생들의 복잡한 www.acmicpc.net 문제 풀이 저번 포스팅인 1197 최소 스패닝 트리를 풀면 아주 수월하게 풀 수 있습니다. 우선 문제가 굉장히 복잡해 보이지만, 핵심은 포기하도록 만드는 애정도의 합을 최소화하는것이 우리의 목표입니다. 우선 사랑관계는 여기서 정점들끼리의 간선으로 연결되어야한다는 뜻입니다. 문제에서 사랑관계가 이미 이루어진 관계는 반드시 포함되어야 한다고 정의했으므로, 사랑관계가 이루어진 관계는 반드시 간선에 포함시켜..
![]()
문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 풀이 MST를 구현하는 기본적인 문제이다. 우선 MST가 무엇인지에 대해서 알아야 한다. MST는 Minimum Spanning Tree이다. Spanning Tree의 조건은 V개의 정점이 있다면 V-1개의 간선을 이용해서 모든 정점을 연결할 수 있어야 한다. 그렇다면 MST는 모든 정점을 연결하면서 가중치의 합이 최소가 되어야 한다. 물..
![]()
문제 https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 문제 풀이 우선 내용이 굉장히 길고 문제를 이해하는데 너무 오래 걸렸던 문제이다. 만약 본인의 코드가 틀렸거나 막혔다면 내 해석이 도움이 되었으면 좋겠다. 우선 보드는 빨간색, 파란색, 초록색 3가지의 보드가 있다. 하나의 배열로 관리하는것이 아닌 3가지의 보드라는 클래스를 생성해서 관리하도록 했다. data class Block(val id: String) { lateinit v..
![]()
문제 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 문제 풀이 골드 3이라는 난이도 치고는 접근방법을 빨리 생각해 낸 문제였던 거 같다. 배낭문제와 비슷하다고 생각하고 접근했었는데, 문제를 풀고 다른사람의 풀이과정을 보니 다들 배낭과 비슷하다고 생각했던 것 같다. 그 정도로 접근하기가 쉬웠던 문제였던것 같다. 추를 사용해서 만들 수 있는 모든 무게를 검사해 주면 된다. 추를 사용해서 만들 수 있는 무게에 대한 방법은 크게 3가지 방법이 있을 것..
![]()
문제 https://www.acmicpc.net/problem/20542 20542번: 받아쓰기 세계적인 기업 CTP(Chickens Threaten Programming)에 입사하기 위해서는 영어 받아쓰기 테스트를 통과해야 한다. 영어 받아쓰기는 채용 담당자가 불러주는 단어를 지원자가 받아쓰는 시험이다. CTP에서는 www.acmicpc.net 문제 풀이 우선 문제가 굉장히 길고 비슷한 말이 많아서 문제에 대한 정확한 파악이 필요하다. 입력은 크게 답변과 정답이다. 이 두 가지를 구분하는 것이 굉장히 중요하다. 우리는 답변을 수정,삭제,변환을 통해서 정답과 같은 문자열을 만들어야 한다. 그리고 날려쓰기라는 정보가 등장한다. i를 날려썼다면 i, j, l v를 나르였으면 v, w로 인식된다. 즉 우리가 ..
![]()
문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 풀이 난이도 있는 DFS, BFS 문제의 특징이라고 할 수 있다. DP와 같이 사용하거나, 삼차원 배열을 통한 방문 체크, 우선순위 큐 같은 경우가 있다. 해당 문제는 삼차원 배열을 통해서 벽을 부순 여부를 가지고 방문을 체크하는 것이 중요하다. 일반적인 이차원 배열로 방문처리를 할 경우 똑같은 좌표를 방문했지만, 해당 좌표를 이동하기 위해서 벽을 부순건지, 부..
![]()
문제 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 문제 풀이 나는 해당 문제를 전형적인 bfs 문제라고 생각한다. 하지만 bfs 문제에서도 조금 더 진화한 문제이다. 우선 문제 초기에는 DP를 사용해서 주변에 존재하는 쓰레기를 저장해서 방문 처리를 하려고 했지만, 결과적으로 도착지점에 도착한 경우에 최적의 도착을 해야하기 때문에, 도착한 시점에 우리는 가장 적은 쓰레기를 마주치고 밟아야 한다. 그렇기 때문에 DP..
![]()
문제 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 문제 풀이 항상 높은 난도의 BFS, DFS를 풀면 알 수 있듯이 최적화에 가장 신경을 써야 한다. 그렇지 않다면 무수히 많은 시간초과를 볼 수 있을 것이다... 문제의 핵심은 빈칸을 선택해서 사각형으로 바꾸고, 가장 길게 연결된 사각형의 크기를 구하는 것이다. 그렇다면 우리는 기존의 배열에서 사각형들을 라벨링 하는 것이 필요하다. 왜 라벨링을 해야하는가에 대해서 작업의 흐름을 판..
![]()
문제 https://www.acmicpc.net/problem/15659 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 풀이 정말 까다로운 문제였다. 연산자들의 우선순위를 해결해줘야 했기에, 그 부분에서 사람들이 많이 어려움을 느꼈을 것이라고 생각한다. dfs를 이용해서 모든 경우의 수를 탐색하고, 해당 식의 최솟값과 최댓값을 구한다. 초기 풀이 방식에서는 숫자와 연산자들을 모두 포함하는 배열을 하나 생성했지만, 숫자들은 고정이고, 연산자들의..
