본문 바로가기

C++ 코딩 문제 풀이151

[Programmers] 섬 연결하기 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 문제에서 요구하는 결과값이 최소 신장 트리(minimum spanning tree)의 간선의 가중치의 총합이므로, 최소 신장 트리 알고리즘을 활용하여 문제를 해결하고자 하였다. 구현 간선 데이터가 주어지므로, 유니온-파인드(union-find) 연산을 구현한 다음 크루스칼 알고리즘(Kruskal's algorithm)을 통해 최소 신장 트리를 만들어 가중치의 총합을 구하였다... 2023. 12. 11.
[Baekjoon] 동전 뒤집기 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 해결 과정 착안 $N^2$ 개의 동전의 초기 상태로부터 뒷면(T)인 동전의 갯수가 최소가 되도록 행 또는 열을 뒤집는 경우를 찾기 위해서는 가능한 모든 경우를 확인해보아야 한다. 이때, 행이나 열을 뒤집는 동작을 수행할 때 선택된 행과 열 중에서 어느 것을 먼저 뒤집더라도 결과가 동일하므로, 편의상 항상 행을 먼저 다 뒤집은 다음에 열을 뒤집는 경우만 살펴볼 수 있다. 행 또는 열을 뒤집.. 2023. 12. 9.
[Programmers] 마법의 엘리베이터 https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 10의 거듭제곱에 해당하는 만큼씩 층을 올라가거나 내려갈 수 있으므로 0층에 도착하기 위해 모든 자릿수의 숫자를 0으로 만들도록 이동하며, 이때 이동 횟수를 줄이기 위해 각 자릿수 별로 층을 오르는 것과 내려가는 것 중에서 어느 것이 유리한지를 판단하면 문제를 해결할 수 있다. 단, 자릿수 별로 이동할 때 층을 올라가서 해당 자릿수를 0으로 만드는 경우는 현재 자릿수보다 큰.. 2023. 12. 8.
[Baekjoon] 9084번: 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 서로 다른 $n$ 가지 동전의 가치를 $c_1, c_2, \cdots, c_n$, 특정한 금액 $m$을 만들기 위한 경우의 수는 1) $c_1$ 짜리 동전만 사용하여 만드는 경우 (가능하다면) 2) $c_2$ 짜리 동전을 추가로 사용하여 만드는 경우 (가능하다면) 3) $c_3$ 짜리 동전을 추가로 사용하여 만드는 경우 (가능하다면) $\cdo.. 2023. 12. 7.
[Programmers] 귤 고르기 https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 각각 크기 별로 귤을 분류하여 저장할 배열을 만들어, 같은 크기의 귤마다 몇 개씩 있는지를 파악한 다음 배열을 내림차순으로 정렬하면 탐욕 알고리즘에 기반하여 문제를 쉽게 해결할 수 있다. 구현 std::unordered_map 클래스를 활용하면 귤을 크기 별로 몇 개씩 있는지 쉽게 파악할 수 있다. 이때 std::sort() 메서드를 사용해 정렬하기 위해서는 std::uno.. 2023. 12. 6.
[Baekjoon] 1063번: 킹 https://www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 문제 해결 과정 착안 킹을 움직였을 때, 돌과 위치가 겹쳐지는지의 여부에 따라 조건문 분기를 처리하는 데에 주의하여 문제에서 주어진 조건을 구현하고자 하였다. 구현 킹과 돌을 나타내는 구조체를 만들어 이동을 위한 메서드를 정의할 때 먼저 이동 여부를 판단하고, 이동 가능하다면 해당 위치로 이동시키는 메서드를 구현하였다. 이때 킹 또는 돌이 체스판 밖으로 밀려나는 경우는 이동을 수행하지 않으므로, 편의상 원위.. 2023. 12. 5.

티스토리툴바