🐸 Problem Solving

🔗 문제 링크 : https://www.acmicpc.net/problem/14503  ☁ 로봇 청소기 감시하기로봇 청소기의 작동 방식 그대로 코드로 구현하면서, 술술 풀리는 줄 알았지만.. 테스트 케이스 2번에서 문제가 터지고 11 x 10 사이즈의 맵에서의 디버깅을 시작하였다. 청소하는 경로를 추적하는 방법은 문제해결에 아주아주 큰 도움이 된다. 간절한 분에게 비교문서로서 도움 되길 바라며.. 이 본문의 마지막 부분에 테스트케이스 2번의 정상적인 청소 경로를 포함하였다.  참고로 테스트 케이스 2번의 결과는 모든 빈칸을 청소한 결과가 아니다.즉, 청소되지 않은 칸이 존재한다.   나의 망가진 로봇 청소기의 경로는 기가막혔다.    문제로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를..

🔗 문제 링크 : https://www.acmicpc.net/problem/1325  문제해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹할 수 있는 컴퓨터를 해킹하려고 한다. 이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다. 이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.     입출력 예시입력첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보..

🔗 문제 링크 : https://www.acmicpc.net/problem/1012  ☁ BFS에서 자주 사용하는, 방문 여부를 저장할 변수의 이름을 visited로 사용했었지만, 불리언(boolen) 변수임을 명확하게 하기 위해 접두사 is를 붙여서 isVisited로 사용하는 습관을 들이려고 한다.   문제차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추 근처에 서식하며 해충을 잡아먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 ..

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]  💣 단순한 탐색으로는 효율성 테스트를 통과하지 못한다!  시추관의 위치를 옮길 때마다 BFS 수행했던 첫 코드는 정확성 테스트는 통과하지만 효율성 테스트에서 처참히 실패하게 되는데.. 결국 BFS를 한 번만 수행하는 게 요점인 것 같다. 수행하는 동안 최대한 많은 (석유)데이터를 뽑아먹을 궁리를 해야 한다!   문제세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습..

🔗 문제 링크 : https://www.acmicpc.net/problem/1926  문제어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.     입출력 예시입력첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한..

🔗 문제 링크 : https://www.acmicpc.net/problem/2798       문제카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 ..

문제수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세..

문제한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.    입출력 예시     풀이 완전 탐색(Brute Force)을 이용해 모든 가능한 조합을 생성하고, int형으로 변환하여 set 에 담았다.set에 저장함으로서, 중복(예: 011과 11은 동일한 숫자로 취급)을 제거했다.#include #include #include using namespace std;set combinations;/* 숫자 조합 */void generateCombination(stri..

🔗 문제 링크 : https://www.acmicpc.net/problem/1260  문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.       입출력 예시입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.  출력첫째 줄에 DFS를 수행..

🔗 문제 링크 : https://www.acmicpc.net/problem/10814  문제온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.     입출력 예시     풀이 sort()는 기본적으로 안정 정렬을 지원하지 않기 때문에, 사용하면 틀리게 된다.결국, 입력을 받을 때 인덱스를 같이 저장하거나, 안정 정렬을 지원하는 stable_sort()를 사용해야한다. 아래 코드는 stable_sort()를 사용한 풀이다.#include #include #include using namespace std;struct Member { int age; ..