알고리즘(42)
-
백준 1292번: 쉽게 푸는 문제 (C++)
https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 풀이 최대 1000번이어서 백터를 이용해 전체 수열을 만들어주었다. 그리고 A 부터 B 까지 전부 sum에 더하여 출력했다. 전체 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int A, B; vector v; int sum = 0; cin >> A >> B; for (int i ..
2023.01.18 -
백준 1652번: 누울 자리를 찾아라 (C++)
https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 최대 시간복잡도가 100*100이어서 완전 탐색으로 진행했다. 우선, ver, hor 변수를 선언해서 빈 공간일 때 카운트를 했다. 그리고 ' X ' 를 만나거나 끝 부분에 도착했을 때 ver, hor가 2보다 크다면 누울 공간이 나온다는 뜻이므로 ver_cnt 와 hor_cnt 에 1씩 더해주고 ver, hor를 0으로 초기화해주었다. 가로와 세로는 i 와 j를 바꿔 이중 for문..
2023.01.18 -
백준 1111번: IQ Test (C++)
https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 풀이 풀어보려고 시도했으나 접근법을 몰라 풀이 방법만 찾아봤다. 그리고 나름대로 다시 분석하여 풀어봤다. 케이스를 나누어서 구하는 방식이었는데 공식을 보니 고등학교때 풀었던 변수의 범위에 따라 케이스를 나누어서 계산하는 문제가 생각났다. 우선 차례대로 식을 쓰면 이런 느낌이다. 그리고 여기서 첫번째 식과 두번째 식을 연립해서 a와 b에 대한 식으로 나타내면 이런식으로 나타낼 수 있다. 이제 N과 X항에 따라 각 케이스를 구할 수 있다. N = 1 , 먼저 X1 밖..
2023.01.18 -
백준 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