![]()
문제 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://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음 볼 때 DP 문제라고 생각을 하지 못했는데, 손으로 써 내려가면서 DP문제라는 것을 깨달았다. 우선 우리는 목표 숫자를 N이라는 숫자를 여러번 사용해서 표현해야 한다. 여기서 왜 DP이냐에 대해서 생각을 해보자. 만약 5를 3번 쓸 경우 만들수 있는 숫자의 조합은 무엇일까? 이걸 구하기 위해서는 5를 1번 쓸 경우, 5를 2번 쓸 경우에 대해서 구해야 한다. 이유는 써 내려가..
![]()
문제 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://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 풀고 나서 Lv3가 맞나..? 싶은 문제였다. 인접행렬을 사용해서 풀면 쉽게 풀 수 있는 문제지만 Lv3라서 뭔가 복잡하게 풀어야 될 거 같아서 나름대로 복잡하게(?) 풀었다. 문제에서 요구하는 바는 연결할 수 있을 만큼 최대한으로 연결하고, 연결된 그룹의 수를 구하는 것이다. 여러 가지 방법이 있겠지만, 나는 노드를 구현해서 풀어보고 싶어서 해당 방식으로 풀었다. 우선 크게 노드..
![]()
문제 https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 문제 풀이 나는 해당 문제를 전형적인 bfs 문제라고 생각한다. 하지만 bfs 문제에서도 조금 더 진화한 문제이다. 우선 문제 초기에는 DP를 사용해서 주변에 존재하는 쓰레기를 저장해서 방문 처리를 하려고 했지만, 결과적으로 도착지점에 도착한 경우에 최적의 도착을 해야하기 때문에, 도착한 시점에 우리는 가장 적은 쓰레기를 마주치고 밟아야 한다. 그렇기 때문에 DP..
