0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 일년마다 주위(상하좌우)에 물이 있는 개수만큼 빙산이 녹는 방식인데, 빙산이 두개이상으로 분리되는 시간을 구하는 문제이다! (빙산이 다 녹을 때까지 분리되지 않으면 0 출력) 먼저 2차원 배열을 입력받고 1. 4방향 탐색 후 물이 있는개수만큼 빼주기 2. 빙산이 분리되었는지 확인 3. 빙산이 다 녹았는지 확인 을 반복한다. 1. 4방향 탐색 후 물이 있는개수만큼 빼주기 처..

문제 출처 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 백트래킹을 사용하여 쉽게 해결할 수 있다. dfs로 가장 간단하게 탐색을 진행할 수 있다. 그러나 dfs로 4칸을 모두 찾는 단순한 문제인줄 알았는데, ㅓ ㅜ ㅓ ㅗ와 같은 케이스가 있다. 이 경우는 따로 처리하여 해결하였다. 코드 #include #include using namespace std; int N, M; int dx[4] = {1, -1, 0 , 0}; int d..

문제 출처 : https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 dfs, bfs 모두 사용 가능하며 bfs로 해결하였다. 코드 #include #include #include using namespace std; int w, h; int arr[50 + 1][50 + 1]; bool check[50 + 1][50 + 1]; queue q; int dx[8] = {-1, 1, 0, 0, 1, 1, -1, -1}; int dy[8] = {..

문제 출처 : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 dfs를 사용하여 해결한 문제이다. 그래프 문제에서 자주 쓰는 dx, dy 배열을 선언해 4방향 탐색을 돌려주면 된다. 여기서 주의할 점이 다음 dfs를 호출할때 cnt + 1, cnt++, ++cnt 에 따라 결과값이 달라진다는 것에 유의하자. dfs(row + dy[i], col + dx[i], cnt + 1); 코드 #include #include using nam..

문제 출처 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 dfs를 사용하여 해결한 문제이다. 현재 위치인 idx, 합을 나타내는 sum, 현재 수열 개수 cnt, 부분수열의 크기 size 를 넘겨주었고 size == cnt인 순간 합이 S인 경우를 체크하였다. 코드 #include #include using namespace std; int N, S; int answer; void dfs(vecto..

문제 출처 : https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 dfs를 사용하여 해결한 문제이다. dfs에서 알파벳을 하나씩 추가한뒤, L개가 되면 모음 조건 && 자음 조건을 확인해 처리하였다. str.push_back(v[now]); if(v[now] == 'a' || v[now] == 'e' || v[now] == 'i' || v[now] == 'o' || v[now] == 'u') vowel++; else conso++; if(str.l..

문제 출처 : https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 수가 주어졌을때 6개를 골라 모든 방법을 출력하는 조합 문제이다. 이 문제를 푸는 방법은 크게 2가지가 있다. 백트래킹(dfs)를 사용하여 풀이 순열(next_permutation)을 사용하여 풀이 두 가지 모두 적용할 수 있는 좋은 문제이며, 하나씩 확인해보자! 1. 백트래킹(dfs)를 사용하는 방법 우선 처음 K를 입력받고, K개 수는 vector (V) 에 저장..

문제 출처 : https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 간단한 브루트포스 문제이다. 100 미만의 수는 모두 한수이므로 그대로 출력하고, 세 자리 수는 각 자리 수를 구해준다. ex) 216 : c= 2, b = 1, a = 6 등차수열은 연속된 두 개의 수의 차이가 일정한 수열 이므로 c - b = b - a 일 경우 한수이다. 코드 #include #include using namespace std; int main(){ ios::..

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 풀이 완전탐색 문제이며, 조합 / 중복제거 / 에라토스테네스의 체를 활용하여 해결하였다. 해결한 방법은 다음과 같다. 1. 종이 조각으로 만들 수 있는 모든 경우의 수 구하기 (next_permutation 활용) 2. 경우의 수에서 중복 제거하기 (erase, unique 활용) 3. 소수 판별하기 1. 모든 경우의 수 구하기 모든..

문제 출처 : https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP로 해결하는 문제이다. P1~PN은 card 배열에 넣어주고, dp[i]를 카드 i개를 갖기 위해 지불한 최댓값 이라고 하였다. 모든 경우의 수를 고려해야 할 것 같아서, 각 dp(1부터 N)마다 1부터 i장 이하의 카드팩을 구매하는 경우를 고려하였다. ex) 1장 카드팩을 구매할 경우 dp[N] = dp[N - 1] + card[1] 이다. 2장 카드팩을 구매할 경우 dp[N] ..