https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 투 포인터 알고리즘을 사용하는 골드4 문제. 문자열의 길이 S가 1e6으로 커서 투 포인터 알고리즘을 사용해야 한다. 구간 [s,e] 안에 있는 알파벳의 종류가 N을 넘지 않도록 관리해주면 된다. 알파벳의 종류를 세주기 위해서, 일반적이라면 map 등을 만들어서 관리하게 될 텐데, char 가 0~255 사이의 숫자 아스키코드에 대응한다는것을 통해 그냥 256개의 배열을 만드는 방법으로 map 를 대체할 ..

https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 비트마스킹을 사용해서 풀었다. 재귀로 풀어도 상관없다. 비트마스킹을 통해서 팀 A와 B를 구분해주었다. i번째 비트가 1으로 켜져있다면 i번째 사람은 A팀에 들어간 것이고 i번째 비트가 0으로 꺼져있다면 i번째 사람이 B팀에 들어간 것이다. 사람 20명으로 만들어 낼 수 있는 모든 경우에 대해서, O(N^2) 로 두 사람을 골라낸 다음 그 두 사람이 같..

https://www.acmicpc.net/problem/16165 16165번: 걸그룹 마스터 준석이 정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 www.acmicpc.net std::map 을 활용해서 해결한 문제. 입력 범위가 작아서 매번 비교대조하면서 해결해도 괜찮겠다만, 편리하고 깔끔하게 풀기 위해서는 std::map을 사용하면 좋다. std::map 으로 문자열과 숫자 인덱스를 서로 매칭시켜 줄 수도 있고, teamName[Name[i]] = i; 어떠한 팀 $M_i$ 에 어떠한 사람이 포함되어있는지도 맵을 사용하면 깔끔하게 판별할 수 있다. if(memb..

https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 이분 탐색 문제. N이 터무니 없이 큰 숫자라서 시뮬레이션 문제로 보면 시간초과를 피할 수 없다. 이분탐색을 통해서 "사람 N명이 탑승하는데 필요한 최소의 시간" 을 구한다. 이 시간을 T라고 하면, 정확히 T 시간에 사람이 N명 탑승하게 될 것이므로, T-1 시간에는 탑승을 하지 못한 사람들이 생기게 된다. 이 사람들 중에서 마지막 아이가 나오게 되므로, T..

https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 자료구조 문제. 차량 번호로 주어지는 문자열을 숫자에 매칭시켜줘야 한다. 처음 N줄에 들어오는 문자열들을 1부터 차례대로 숫자에 매칭시켜주고, 다음 N줄에 들어오는 문자열들을 앞서 매칭시켰던것을 이용해서 하나의 숫자 배열로 바꿔준다. 숫자 배열을 비교하면서 탐색하는데, 자기 자신의 뒤에서 자기 자신보다 적은 번호를 매칭받은 번호판이 있다면 자기 자신이 반드시 그 번호판의 차량을 추..

https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net DP 문제 ( 수열의 유도 및 구현 ) 개념을 알고 모르고의 유무로 난이도가 극명하게 갈린다고 할 수 있는 문제. 이 문제에서 요구하는 수열은 "교란순열" 혹은 "완전순열" 이다. 44라는 숫자가 나오면 한번쯤 의심해볼만할듯. dp[i] = (dp[i-1]+dp[i-2])*(i-1) 교란순열을 구하는 DP 점화식은 다음과 같다. DP[i] : i명끼리 조건에 맞게 선물을 분배하는 경우의 수 유도 각각의 사람의 번호를 $a_i$ , 선물의 번호를 $b_i$ 로 둔다. 어떠한 사람 A가 선물을 하는 경우는 $(N-1..