0m1n's Develog

문제 출처 :https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 bfs로 생각할 수 있으나 다익스트라 개념을 도입해 풀어야하는 문제이다. 벽을 부수는 최소 수를 저장하는 dist 배열을 선언해 조건에 달아주면 된다. 코드 #include #include #include #include using namespace std; int M, N; int arr[101][101]; vector dist(101, vector(101..

문제 출처 : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 풀이 이 문제는 불과 지훈이의 이동경로를 비교를 해야한다. 따라서 먼저 불의 시간 별 이동경로를 저장하는 배열을 만들어 계산한 뒤, 지훈이가 이동 가능한지 비교한다. 불 이동 경로 초기 입력 시 fire 배열은 INF로 초기화하고, 처음 불이 있던 자리만 0으로 저장한다. bfs로 기존 배열 값보다 값이 작으면 갱신하고 큐에 푸시해준다. int fire[1000][10..

문제 출처 :https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이 불쌍한 준석이,,, 우선 완전탐색으로 생각했으나 유니온 파인드로 해결해야하는 문제임을 깨달았다. 유니온 파인드는 아래 패턴을 기억해야 할 것 같다. 1. 같은 집합으로 묶어주는 함수(unionParent) root를 찾아주는 함수(getParent)로 가져온 후 서로의 부모를 지정해준다. void unionPar..

문제 출처 : https://www.acmicpc.net/problem/2195 2195번: 문자열 복사 첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 www.acmicpc.net 풀이 최소한의 copy를 사용해 s를 p로 만들 때, 사용 횟수를 출력하는 문제이다. p를 반복문을 돌며 s에서 같은 부분을 찾은 후, 만약 같다면 그 뒤에도 같은지 계속 검사한다. 가장 길게 검사한 부분을 저장해 idx에 더해준다. 코드 #include using namespace std; string s, p; int main(void) { ios::s..

문제 출처 : https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 문제가 길고 영어 번역본이라 거부감이 들 수 있겠으나.. 결론은 연결되어 있는 그래프를 탐색하는 대표적인 그래프 탐색 문제이다. 이런 그래프 문제는 보통 아래와 같은 방법으로 처리한다. vector를 배열로 선언한다. a b가 연결되어 있을 경우 서로 푸시한다. v[a].push_back(값), v[b].push_back(값)..

문제 출처 : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 두 집합 a와 b가 같은 집합에 포함되어 있는지 확인하는 문제이다. 처음에 bfs로 완전탐색으로 구현하였으나, 시간초과가 발생하였다. 따라서 유니온 파인드를 통해 해결해야 한다. 처음 모든 수의 부모를 나타내는 배열 parent를 선언한다. 이 parent 배열은 항상 부모중 가장 작은 값을 가진 노드로 갱신해준다. getParent 부..

문제 출처 : https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 풀이 박스를 배로 옮기는 시간의 최솟값을 출력하는 문제이다. 크레인과 박스를 내림차순으로 정렬한 후 박스를 담을 수 있는 경우 vector를 삭제해주면 된다. (그리디 알고리즘) 코드 #include using namespace std; int N, M; int ans; int main(void) { ios::sync_with_stdio(false); cin.tie(..

문제 출처 : https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 이동하는 벨트에서 로봇 공정이 얼마나 진행될 수 있는지 판단하는 구현 문제이다. 처음 내구도, 로봇 여부를 pair vector로 받아 구현하였고 문제에서 제시된 단계대로 구현하였다. 1. 벨트 이동 deque등으로 직접 옮기는 방법도 있으나, idx를 옮기는 방식으로 구현하였다. 시계방향으로 벨트가 이동하므로 idx를 왼쪽으로 한칸 옮기면 된다. 여기서 ..

문제 출처 : https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 알파벳을 숫자로 치환했을때, 주어진 단어의 합의 최댓값을 구하는 문제이다. 브루트포스 방식으로 모든 숫자를 대입(dfs)해 정답을 구하는 방식도 있으나, 그리디 알고리즘으로 정답을 구하는 방법이 빠르다. 그리디 알고리즘 + @? 그렇다면 어떤 방식으로 해결해야 할까? 단순히 큰 자리수에 큰 숫자를 대입한다고 생각하면 아래와 같은 상황에서는 처리할 방법이 애매해진다. ABC..

문제 출처 : https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 연속된 수의 부분합 중 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제이다. 단순하게 합을 구한다고 해서 정렬이나 priority_queue를 쓰면 안된다. 연속된 수의 부분합이기 때문이다. 그렇다고 브루트포스로 구현하면 시간초과가 발생한다. 어떻게 해야 할까? 바로 투포인터 알고리즘을 사용하면 된다. 투포인터 알고리즘 이름 그대로 배열을 이동하는 포..