![]()
문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 문제 풀이 앞에서 풀었던 1197 최소 스패닝 트리에서 입력형식만 바뀐 거지 문제 풀이는 똑같다. 앞선 문제에서 주어졌던 입력 형식인 from->to->value가 배열 형식으로 i -> j -> input값으로 바뀐것이다. 따라서 해당 입력형식에 따라 노드를 생성하고, 크루스칼 알고리즘을 사용하면 쉽게 풀 수 있다. 전체 코드 package MST.`16398_행성_연결`.LJH impor..
![]()
문제 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는 모든 정점을 연결하면서 가중치의 합이 최소가 되어야 한다. 물..
![]()
코틀린 Collection에는 대표적으로 List, Set, Map이 있다. 자바와는 다르게 코틀린에서는 불변형, 가변형 Collection이 있다. 불변형은 읽기 전용, 가변형은 읽고 쓰기 전용 각각의 Collection마다 고유의 기능이 있다. 불변형의 공통적인 기능 size : 컬렉션의 크기 isEmpty() : 컬렉션이 비어있는지 확인. 비어있다면 True, 아니라면 False contains(element) : 특정 요소가 있다면 true, 아니라면 false 가반형의 공통적인 기능 add(element) : 추가 remove(element) : 삭제 addAll(Collection ) : 인자로 받은 컬렉션의 모든 요소 추가 removeAll(Collection) : 인자로 받은 컬렉션의 모든..
![]()
문제 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와 같이 사용하거나, 삼차원 배열을 통한 방문 체크, 우선순위 큐 같은 경우가 있다. 해당 문제는 삼차원 배열을 통해서 벽을 부순 여부를 가지고 방문을 체크하는 것이 중요하다. 일반적인 이차원 배열로 방문처리를 할 경우 똑같은 좌표를 방문했지만, 해당 좌표를 이동하기 위해서 벽을 부순건지, 부..
