컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 해결 알고리즘 백트래킹으로 네 개의 칸까지 가는 경우의 합들의 최댓값을 구한다. 이 부분은 백트래킹으로는 탐색이 불가능하므로 따로 완전탐색을 실행해주어야한다. 소스 코드 #include using namespace std; int N, M, result = 0; int arr[501][501]; bool visited[501][501]; int dir[4][2] = {{0, 1}, {0, -..

https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 문제 해결 알고리즘 $a_1 + a_2 + a_3 = a_4$ 이렇게 구하려고하면 $O(n^4)$의 시간복잡도가 나오기 때문에 시간초과가 발생한다. 그렇기 때문에 $a_1 + a_2 = a_4 - a_3$로 두 항의 값이 같은 걸 구하기 위해 이분 탐색을 하면 $O(n^2 \log n)$으로 해야 정답을 받는다. 소스 코드 #include using..

문제 해결 알고리즘 문자열을 세 부분으로 나눠 준 후 각각을 뒤집어 주고 합친 후, 배열에 저장해준다. 그러고 난 후에 정렬을 해서 맨 앞에 있는 원소를 출력해준다. 소스 코드 #include using namespace std; int main(){ string str; cin >> str; vector v; for(int i=1;i

https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 문제 해결 알고리즘 전형적인 백트래킹 문제인데 거기에 인접해 있는 모든 문자가 같지 않은 문자열이라는 조건만 추가해준다. 소스 코드 #include using namespace std; int arr[26]; int result = 0; int N; bool isTrue(string str){ bool flag = true; for(int i=0;i str; N = str.size(); for(int ..

https://www.acmicpc.net/problem/1105 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 알고리즘 L부터 R까지 수에 8이 들어있는 개수 중 최솟값을 출력해준다. (이 때, 최솟값이 0이면 더 이상의 연산은 불필요하므로 바로 출력해준다.) 소스 코드 #include using namespace std; int main(){ long long L, R; cin >> L >> R; int result = 99; for(long long i=L;i

https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 문제 해결 알고리즘 문자열의 맨 끝 두 번째부터 시작해서 첫번째 문자를 붙여가면서 각각 팰린드롬인지 확인한다. 다음부터는 시작하는 문자열을 앞으로 한 칸 당겨서 진행해준다. 그렇게 첫번째까지 완료한 후 팰린드롬인 문장 중 가장 작은 길이를 출력한다. 소스 코드 #include using namespace std; bool isPalindrome(string str){ bool flag = true; f..

https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 문제 해결 알고리즘 숫자를 순열로 완전탐색해주고 B보다 작고 맨 앞 숫자가 0이 아닌 수중에 가장 큰 값을 출력해준다. 소스 코드 #include using namespace std; int main(){ int cnt = 0; int result = -1; int A, B; cin >> A >> B; vector v; while(A != 0){ v.push_back(A %..

https://www.acmicpc.net/problem/1198 1198번: 삼각형으로 자르기 볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 www.acmicpc.net 문제 해결 알고리즘 세 점을 선택해 고를 수 있는 삼각형의 넓이를 모두 골라 가장 큰 삼각형의 넓이를 출력한다. 소스 코드 #include using namespace std; int result = 0; int triangle_area(int x_1, int y_1, int x_2, int y_2, int x_3, int y_3){ return abs((x_1*y_2 + x_2*y_3 +..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제 해결 알고리즘 BFS를 해주는데 육지인 모든 칸들을 전부 한 번씩 BFS를 해준다. 소스 코드 #include using namespace std; int R, C, result = 0; int arr[51][51]; int visited[51][51]; int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; void Clear(){ for(int i=0;i

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 문제 해결 알고리즘 string으로 숫자를 입력 받아 앞자리 수와 비교 한 후에 long long으로 배열에 입력해 백트래킹이 끝나면 배열을 정렬해 그에 해당하는 감소하는 숫자를 출력한다. 소스 코드 #include using namespace std; int N; vector v; void dfs(string str){ if(str != "") { long long n = stol..