![]()
안녕하세요. 알고리즘 1051번 숫자 정사각형문제를 풀어보도록 하겠습니다. 브루트포스의 전형적인 NM문제네여. N,M이 50이하의 자연수이고 가장 큰 정사각형을 찾는 부분에서 min(N,M)이 반복되니까 대략 50*50*50번의 연산이 필요합니다. 이를 통해 완전탐색으로 풀 수 있다는 것을 알 수 있습니다! 그래서 저는 삼중 for문을 사용하여 구현을 해보았습니다. 코드는 다음과 같아요. #include #include #include #include #include using namespace std; int n = 0; int m = 0; int max_size = 1 ; int main (void){ cin>>n>>m; string arr[n]; for (int i = 0 ; i < n ; i++..
링크 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 1. 주어진 보드에서 8x8 크기의 체스판을 뽑아낸다. 2. 뽑아낸 체스판을 이용해서, 가장 왼쪽 위가 검은색으로 시작해야 최소한으로 다시 칠해야 하는지 하얀색으로 시작해야 최소한으로 다시 칠해야 하는지 확인한다. 3. 이렇게 만들 수 있는 체스판을 모두 확인해서 다시 칠해야 하는 정사각형의 최소 개수를 구한다. 단순무식하게 모든 경우의 수를 확인하는 완전 탐색의 기본적인 문제로..
1. [BOJ 4435] 중간계 전쟁 https://www.acmicpc.net/problem/4435 4435번: 중간계 전쟁 첫째 줄에 전투의 개수 T가 주어진다. 각 전투는 두 줄로 이루어져 있다. 첫째 줄에 간달프 군대에 참여한 종족의 수가 주어진다. 이 값은 공백으로 구분되어 있으며, 호빗, 인간, 엘프, 드워프, www.acmicpc.net 문제에서 요구한 대로 아래 내용에 맞게 점수를 곱해 더해주면 되는 문제입니다. 간달프 호빗 - 1 인간 - 2 엘프 - 3 드워프 - 3 독수리 - 4 마법사 - 10 사우론 오크 - 1 인간 - 2 워그(늑대) - 2 고블린 - 2 우럭하이 - 3 트롤 - 5 마법사 - 10 t = int(input()) for i in range(t): a1, a2, ..
![]()
https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 문제 풀이 첫번째 줄에 얻은 값들을 num이라는 리스트에 저장하고, 두번째 줄부터 입력되는 정사각형의 각 숫자들을 rec라는 2차원 리스트를 생성하여 값을 저장한다. 네 꼭짓점의 수가 모두 같은 가장 큰 정사각형의 크기를 출력해야 하므로, 해당 정사각형 내에서 만들 수 있는 가장 큰 정사각형 변의 길이에서 시작하여 변의 길이를 하나씩 줄여가는 반복문을 만든다. 반복문을 사용하여 위와 같은 방식으로..
https://www.acmicpc.net/problem/10178 10178번: 할로윈의 사탕 할로윈데이에 한신이네는 아부지가 사탕을 나눠주신다. 하지만 한신이의 형제들은 서로 사이가 좋지않아 서른이 넘어서도 사탕을 공정하게 나누어 주지 않으면 서로 싸움이 난다. 매년 할로윈 www.acmicpc.net 문제분석 정수 입력을 받아 그 정수만큼 loop 문을 돌려서 2개의 정수를 입력 받고 그 몫과 나머지를 출력하는 문제이다. 몫과 나머지를 출력할 때, 문자열을 함께 출력해야 한다. C++ 언어에서는 단순히 입출력 함수를 쓰면 되지만, 파이썬에서 이 문제를 풀기 위해서는 format이나 print(f) 함수를 사용해야 한다. 코드 a = int(input()) for _ in range(a): n, m ..
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 해당 문제는 주어진 k개의 숫자를 사용해서 6개의 숫자 조합을 만들어 내는 것이 포인트입니다. 6가지의 숫자 조합을 만들기 위해서 두가지 방식으로 접근을 해봤습니다. ① C++ STL의 prev_permutation() 함수를 이용한 조합 만들기 더보기 더보기 더보기 변수 k의 범위가 6 < k < 13 으로 작은 편이어서 prev_permutation 알고리즘을 사용해도 시간제한 1초..
링크 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 키가 같은 사람이 연속해서 줄을 설 경우를 생각하는데 오래 걸려서 많이 고민한 문제였습니다. 5555 (4C2) 65555 같은 경우만 생각해서 33332333 같은 경우를 고려하지 못했습니다. 스택에 차례대로 줄에 선 사람들을 넣으면서 1. top 보다 작으면 push를 하고 2. top 과 같으면 push 할 때 second를 top의 second += 1 (..
![]()
링크 https://www.acmicpc.net/problem/15654 문제 풀이 입력받은 수를 사전 순으로 출력하는 것이 문제의 조건이다. 수 들이 임의의 순서로 주어지므로 이를 정렬하고, 완전 탐색을 이용한다. j 번째 인덱스를 참조할 때마다 visit[j]를 true로 설정하여, 중복으로 입력되는 것을 방지한다. 재귀가 끝난 이후 false로 설정하여, 해당 index를 참조할 수 있도록 한다. 코드 결과
![]()
링크 https://www.acmicpc.net/problem/2798 풀이 N개의 카드중 3개를 뽑아 더하여 구하는 조합 문제이다. 이번에 배운 next_permutation을 이용한 조합알고리즘을 사용해보았다. 3중첩 for문, next_permutation, dfs를 이용하여 구현하였으며 이중 for문의 성능이 가장 우수하였고 dfs는 시간초과로 인하여 틀렸다. 코드 for문을 이용한 코드 #include using namespace std; int main() { int n,m; int card[100]; cin >> n>>m; for (int i = 0; i > card[i]; } int result = 0; for (int i = 0; i < n; i++) { f..
링크 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 채널 N으로 이동할 때 100번에서 +, - 로만 이동하는 방법과 고장나지 않은 버튼으로 누를 수 있는 번호를 누르고 필요시 +, -로 이동하는 방법 중 최소의 값을 구했습니다. 처음 제출할 때 초기 ans값을 초기화 하는 과정에서 아무 생각 없이 0으로 잡아 틀렸는데 문제를 풀 때 멍때리지 말고 차근 차근 생각하면서 풀어야 겠다고 느꼈습니다 (자의적인 해석 ❌ 문제 꼼..
링크 https://www.acmicpc.net/problem/13423 13423번: Three Dots 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 www.acmicpc.net 풀이 문제를 처음 보자마자 떠올린 풀이는 nC3으로 세 점을 뽑는 방법이였지만 시간복잡도 때문에 두 점을 뽑고 이진탐색으로 나머지 한 점이 찍혀있는지 확인하는 방법으로 풀었습니다. 하지만 위 방법으로 풀어도 시간초과가 떠서 이리저리 코드를 바꿔보면서 한참 해맸는데 (분명 시간복잡도 계산해 보면 시간 초과가 뜰리가 없는데...) 이진 탐색을 구현하는 함수 코드에서 ..
링크 : https://www.acmicpc.net/problem/1969 입력 첫 줄에 DNA의 수 N과 문자열의 길이 M 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 출력 첫째 줄에 Hamming Distance의 합이 가장 작은 DNA를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다. 예제 입력 : 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 예제 출력 : TAAGATAC 7 첫째 줄 T T A T T T4개, A1개 T출력 후 Hamming Dist..
