알고리즘

https://www.acmicpc.net/problem/2441 2441번: 별 찍기 - 4 첫째 줄에는 별 N개, 둘째 줄에는 별 N-1개, ..., N번째 줄에는 별 1개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. www.acmicpc.net 1. Logic 구현,,, 쉬운 구현,,, i만큼 공백 출력 i-공백만큼 별 출력 2. Code #include using namespace std; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { cout

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 1. Logic unordered_map을 사용해서 이름을 저장해준다. union find알고리즘을 사용하기 위해서 몇번째 노드인지 같이 넣어줬다. 즉 key값은 이름 value값은 고유 번호이다. 노드의 부모를 찾아서 merge해 줄 때 부모 노드의 친구 수를 더해주면 된다. 주의해야 할 점은 사람1의 부모와 사람2의 부모가 같을 경우 2번 더해주는 상황이 일어나기 때문에 더하지 않도..

https://www.acmicpc.net/problem/20310 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 1. Logic 사전순으로 가장 빠른 것을 구하라고 했기 때문에 0은 뒤에서부터 없애주고 1은 앞에서 부터 없애주는게 가장 작은 숫자를 구할 수 있는 방법이다. 2. Code #include using namespace std; int zero; int one; int checkErase[501]; int main() { string str; string ans = ""; cin >..

https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 1. Logic 처음에 unordered_map으로 접근했다가 시간초과를 받았다. 키워드 입력을 받을 때 중복이 없기 때문에 삽입, 삭제 모드 O(1)을 시간복잡도로 가지는 unordered_set을 활용하여 풀이했다. 2. Code #include using namespace std; unordered_set us; unordered_set::iterator i..

https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 1. Logic 재료의 갯수 n이 10밖에 안되기 때문에 완전탐색으로 해결 가능하다. 조합 탐색을 하며 선택을 하는 경우 안하는 경우를 구해서 값을 선택 해 주면 된다. 2. Code #include using namespace std; vector taste; long long ans = LLONG_MAX; long long n; void solve(long long idx..

https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 1. Logic 여기서 비트는 한 물병으로 얼마나 물이 모였는지를 나타낸다. 항상 물은 똑같은 양끼리 합칠 수 있고 1부터 시작하기 때문에 1 > 2 > 4 > 8 > 16 등등 이렇게 2의 제곱수로 늘어나게 된다. 즉 1의 갯수는 물이 담긴 물병의 갯수를 의미한다. 테스트케이스인 13, 2를 예시로 들어보면 13을 2진수로 변환하면 1101이다. (8 + 4 + 1) 1이 먼저 나오는 위치는 0번째이..

https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 1. Logic 1부터 계속 더하다가 처음으로 N을 넘는 숫자가 나오면 그 숫자에 -1 한 값이 정답이 된다. 2. Code #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); long long S; cin >> S; long long sum = 0, num = 1; int cnt = 0; while (1) { sum += num; cnt++; if (sum > S) { cnt--; break; } num++; } cout

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 1. Logic 0~n-1까지 순회하면서 각 시작 위치보다 큰 숫자만 더해주면서 최댓값을 구해주면 된다. 코드를 보면 이해가 쉬울 것 이다. 2. Code #include using namespace std; int n; vector input; //증가하는 부분수열의 합 int dp[1001][1001]; int solve(int id..

https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 1. Logic 중복을 포함하지 않는다고 했기 때문에 map대신 unordered_map을 사용했다. 그리고 입려이 50만이기 때문에 logN을 시간복잡도로 가지는 map에 비해 O(1)을 가지는 unordered_map을 사용하는게 좋을 것 이라고 생각했따. unordered_map의 key:학번 value:클릭한 순서 로 설정하고 입력은 받은 후 vector 로 설정하여 원소를 넣..

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 1. Logic 입력이 1000000이기 때문에 시간복잡도가 logN인 map을 사용해서 입력을 받았다. 2. Code #include using namespace std; map m; int n; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int ..