프로그래밍 공부 노트

https://www.acmicpc.net/problem/23349 23349번: 졸업 사진 첫째 줄에 학교가 공지할 것으로 예상되는 혼잡 (장소, 시간대) 쌍을 공백으로 구분하여 출력한다. 이때 시간대는 조건을 만족하는 가장 긴 시간대를 의미한다. www.acmicpc.net 각 촬영을 선분, 촬영의 시작 시간과 종료 시간을 시작점과 끝점으로 보면, 이 문제는 라인 스위핑을 이용해 선분이 가장 많이 겹치는 구간을 찾는 문제이다. 이 때 촬영 장소, 즉 선분의 종류가 문자열로 구분되므로, 라인 스위핑을 위해 각 점을 정렬할 때 선분의 종류를 최우선으로 두어 정렬하면 각 종류 별로 선분을 나누어 저장할 필요 없이 빠르게 라인 스위핑을 실행할 수 있다. #include #include #include #in..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net unordered_map을 이용해 도메인과 비밀번호를 연결해 저장한 뒤 각 쿼리마다 도메인의 비밀번호를 출력한다. #include #include #include using namespace std; int main() { //cin, cout 사용 시 필히 사용할 것 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NU..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 수를 모두 입력받아 정렬한 뒤 이분 탐색을 이용해 답을 구하는 방법이 있고, 기수 정렬을 이용해 이분탐색을 사용하지 않는 방법이 있다. - 이분 탐색 #include #include using namespace std; #define MAX_N 500000 int main() { // 입출력 속도 향상 ios::sync_with_stdio(false); cin.t..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 각 테스트 케이스에서 주어진 옷에 대해, 입을 수 있는 옷의 조합의 수는 (각 옷 종류의 개수 + 1)을 모두 곱한 값이 된다. 이 때 알몸이 아닌 경우는 고려하지 않으므로, 모두 곱해 얻은 값에 1을 뺀 값을 출력하면 정답이 된다. #include #include #include using namespa..

https://www.acmicpc.net/problem/9322 9322번: 철벽 보안 알고리즘 소희는 공개키와 개인키 한 쌍으로 보안을 유지하는 것이 매우 불편하다고 생각했다. 그래서 소희는 공개키만을 이용하는 암호화 체계를 개발했다. 이를 "철벽 보안 알고리즘"이라고 부르기로 www.acmicpc.net 단어가 총 1000개 이하이므로 제1 공개키와 제2 공개키, 암호문을 입력받은 뒤, 제1 공개키와 제2 공개키를 비교하면서 암호문을 특정 순서대로 출력한다면 시간 제한 이내에 답을 출력할 수 있다. 또, 제1 공개키를 입력받아 map에 저장한 뒤 제2 공개키를 이용해 암호문의 복호 순서를 저장한 뒤 암호문을 입력받아 구한 순서대로 출력하는 경우에도 시간 제한 이내에 답을 출력할 수 있다. - 공개키..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net string을 저장할 set 두 개를 준비한다. 듣도 못한 사람을 컨테이너 C1에 전부 저장한 뒤, 모든 보도 못한 사람을 각각 C1에서 찾을 수 있으면 C2에 저장한 뒤, C2의 크기와 각 성분을 출력하면 된다. #include #include #include using namespace std; // s: 듣도 못한 사람의 명단, prt: 듣도 못한 사람 중 보도 못한 사람 set s, pr..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문자열을 N번 입력받아 그 인덱스와 매칭시키는 문제이다. i번째 문자열을 입력받을 때마다 문자열을 배열에 저장하고, 또 문자열을 key로 하는 컨테이너에 i를 저장하면 풀 수 있다. #include #include #include using namespace std; #define MAX_N 100000 // 도감번호를 이름으로 전환 string i2s[MAX_N]; ..

https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 다이나믹 프로그래밍을 이용해 수열의 값을 저장하는 문제이다. 이 때 만들어지는 수열의 밀도가 높지 않고, 인덱스와 값의 범위가 int를 넘어갈 수 있으므로 long long을 이용해야 한다. #include #include using namespace std; typedef long long ll; // A[i]: 수열 A를 저장할 공간 map A; // A[k]를 생성할 때 사용할 두 변수 int P, Q; // A[idx]가 호출된 적이 없다면 해당 값을 채운 뒤 그 값을 반환한다 ll get(ll idx) { if (!A[idx]) ..