알고리즘

(C++) 백준 7785번 - 회사에 있는 사람

문제 링크 : https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제 풀이 해시를 이용한 풀이이다. unordered_set이라는 다소 생소한 STL을 사용하였다. 정렬은 cmp라는 cutom 비교 함수를 만들어서 사전순의 역순으로 정렬하였다. #include #include #include #include using namespace std; int n; string person, act; unordere..

(C++) 백준 1806번 - 부분합

문제 링크 : https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 풀이 투 포인터를 이용하여 풀이하면 된다. 여기서는 st와 en 두 개의 포인터를 사용한다. 1. 배열 A를 입력받는다. 2. en을 1씩 증가시키면서 total의 값이 S 이상일 경우, 그때 그 값이 최솟값인지 체크를 한다. 만약 en이 N이 되면 배열 끝까지 다 순회한 것이므로 더 이상 체크할 것이 없기 때문에 break 한다. 3. st를 1만큼 증가시키고,..

(C++) 백준 2230번 - 수 고르기

문제 링크 : https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 문제 풀이 투 포인터를 사용하여 풀이할 수 있다. 여기서는 st와 en 두 개의 포인터를 사용한다. 1. 배열 A를 입력받은 후, 정렬을 한다. 2. en을 1씩 증가시키면서 A[en] - A[st]의 값이 M 이상일 경우, 그때 그 값이 최솟값인지 체크를 한다. 만약 en이 N이 되면 배열 끝까지 다 순회한 것이므로 더 이상 체크할 것이 없기 때문에 break ..

(C++) 백준 1541번 - 잃어버린 괄호

문제 링크 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 풀이 그리디 알고리즘을 사용한 풀이이다. '-' 이후로 오는 수는 모두 빼기 처리해 주면 최솟값을 구할 수 있다. #include #include using namespace std; string raw, num; int result; int main() { cin >> raw; bool isMinus = false; for(int i = 0; i

(C++) 백준 11051번 - 이항 계수 2

문제 링크 : https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 풀이 이항 계수의 성질 중 다음의 파스칼의 삼각형을 사용하여 풀었다. 처음에 재귀함수를 사용하여 풀이하였으나 그럼 시간 초과가 발생하기에 다음과 같이 dp로 풀이하였다. #include using namespace std; int n, k; int bicos[1005][1005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; bicos[0][0] = bi..

(C++) 6064번 - 카잉 달력

문제 링크 : https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 풀이 문제에 나온 예시를 들어보면 M = 10이고 N = 12일 때 첫 번째 해는 , 11번째 해는 , 13번째 해는 , 는 마지막인 60번째 해를 나타낸다. 이들의 규칙을 찾아보면 n번째 해는 임을 알 수 있다. 그리고 당연히 마지막 해는 규칙에 의해 최소공배수 즉 60번째 해임을 알 수 있다. 이를 이용하여 풀이하였다. #include using namespace std; in..

(C++) 백준 11653번 - 소인수분해

문제 링크 : https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 풀이 소인수분해는 가장 작은 소수인 2부터 시작하여 합성수가 나눠지지 않을 때까지 계속해서 나눠주면 된다. #include using namespace std; int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 2; i*i

(C++) 백준 1929번 - 소수 구하기

문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 풀이 에라토스테네스의 체를 사용한 풀이이다. #include #include using namespace std; int m, n; vector state(1000005, true); void prime(int n){ state[1] = false; for(int i = 2; i*i m >> n; prime(n); for(int i = m; i

(C++) 백준 1978번 - 소수 찾기

문제 링크 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 풀이 만일 N이 2부터 √n의 수까지 나누어 떨어지는 경우가 있으면 이는 소수가 아니다. 이를 활용하여 풀이하였다. #include using namespace std; int A[102]; int n, cnt; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i > A[i]; for(int i = 0; i < ..

(C++) 백준 1026번 - 보물

문제 링크 : https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 여러 수들의 곱의 최솟값을 구하고 싶다면 최댓값에 최솟값을 곱해주면 되고, 곱의 최댓값을 구하고 싶다면 최댓값끼리 곱해주면 된다. 그렇기에 우선 오름차순으로 정렬을 진행하고, 한 배열에선 값이 작은 앞의 원소를, 다른 배열에서는 값이 큰 뒤의 원소를 차례대로 곱하면 최솟값을 구할 수 있다. #include #include usin..