전체 글(45)
-
백준 1051번: 숫자 정사각형 (C++)
https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 풀이 완전 탐색인 듯해서 시간복잡도를 계산해보니 50*50*50정도 밖에 나오지 않았다. 그냥 완전 탐색을 돌려주었다. 전체 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, M; int ans = 1; int board[51][51]..
2023.01.17 -
백준 2231번: 분해합 (C++)
https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 풀이 숫자가 주어졌을때 숫자 -> 분해합은 쉽지만 그 반대는 생성자가 여러개이기 때문에 완전 탐색을 통해 찾아야겠다고 생각했다. 우선, n을 인수로 받아 n-1까지 탐색하는 Generator 함수를 만들었다. 생성자는 n보다는 항상 작기 때문에 1부터 n-1번까지 탐색을 진행시켰다. 문자열로 변환해서 각 자리수를 더해가며 생성자를 찾는 알고리즘을 구성했는데 성공은 했지..
2023.01.16 -
백준 1764번: 듣보잡 (C++)
https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 set 컨테이너를 활용하면 간단하게 풀 수 있다. 사전순 출력이기 때문에 번거롭게 정렬하지 않아도 된다. (set은 원소 자동 오름차순 정렬) 우선, 듣도 못한 사람을 s1에 저장한다. 그리고 보도 못한 사람을 입력 받을 때, s1에 있는 요소랑 같다면 s2에 저장한다. 그 후 s2 사이즈와 s2의 요소들을 출력한다. + 다른 사람 풀이를 보니 map으로 구현한 방법이 더 빠른 듯 하여 m..
2023.01.16