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번 더해주는 상황이 일어나기 때문에 더하지 않도..
Algorithm/Beakjoon
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/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 1. Logic 범위가 10억이기 때문에 이분탐색을 사용하여 풀이했다. 처음 승률은 y * 100 / 2이고 이분탐색으로 이긴 횟수를 바꿔가면서 카운팅 할 때는 (y + mid) * 100 / (x + mid)이다. mid를 바꾸면서 승률이 변경되지 않으면 start를 mid로 올려 게임 수를 증가시키면서 처음 변경되는 end값을 찾아주면 된다. 승률을 구할 때 100을 곱해주기 때문에 i..
https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1. Logic - 메모리 제한이 12MB밖에 안되기 때문에 자료구조에 들어가는 데이터의 갯수를 최대한 적게 넣어야한다. 우선순위 큐를 활용해 -를 붙혀서 오름차순으로 정리해 주고 갯수는 N개 만큼 가지고 있는다. 우선순위 큐의 가장 앞에 있는 수는 -를 떼고 나면 가장 작은 숫자이기 때문에 N개만큼 유지하면서 가장 작은 숫자인 -pq.top보다 큰 숫자가 오면 pq.top을 pop하고 새로운 숫자를 p..
https://www.acmicpc.net/problem/1497 1497번: 기타콘서트 첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 www.acmicpc.net 1. Logic 입력 자체가 n = 1; } return cnt; } void solve(int idx, long long bit, int cnt) { int bitToSong = countBit(bit); if(bitToSong > maxCnt) { maxCnt = bitToSong; ans = cnt; } else if(bitToSong == maxCnt) { ans = min(ans,..
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..
