알고리즘(43)
-
백준 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 -
백준 1057번: 토너먼트 (C++)
https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 kim과 im의 번호를 뺏을 때 1이고 그 중 큰 번호가 짝수일 때 둘이 만나는 라운드다. 이 법칙에 따라 while문의 내용을 넣어주었고 kim과 im을 계속 2로 나누어서 진행시켰다. while문을 탈출하면 둘이 만나는 라운드기 때문에 round를 출력시켰다. 간단하게 구성한 줄 알았는데 문제를 풀고 다른 블로그를 찾아보니 조금 더 간단하게 구성한 while문이 있었다. kim을 2로 나눌때 3..
2023.01.17 -
백준 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