https://www.acmicpc.net/problem/16165 16165번: 걸그룹 마스터 준석이 정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 www.acmicpc.net std::map 을 활용해서 해결한 문제. 입력 범위가 작아서 매번 비교대조하면서 해결해도 괜찮겠다만, 편리하고 깔끔하게 풀기 위해서는 std::map을 사용하면 좋다. std::map 으로 문자열과 숫자 인덱스를 서로 매칭시켜 줄 수도 있고, teamName[Name[i]] = i; 어떠한 팀 $M_i$ 에 어떠한 사람이 포함되어있는지도 맵을 사용하면 깔끔하게 판별할 수 있다. if(memb..
유니온 파인드 == disjoint set 문제 소프트웨어 마에스트로 코테에 나왔다고 들어서 한번 다시 풀어보는 중이다. https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행이 가능한지 안 가능한지만 묻고 있고, 여행 경로의 길이에 제한이 없기 때문에 특정 여행 경로로 두 도시가 이어질 수 있는지, 즉 모든 여행 계획에 속한 도시가 같은 도시집합 상에 포함되는지를 판별하면 되는 문제다. 여행 계획에 속한 도시들에 대해서 find() 를 진행하고..
재활 3일차 시뻘건 문제를 잡아보았다. https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 트라이 자료구조형을 활용해야 하는데 단순히 포함여부만을 물어보는 문제가 아니라서 티어가 좀 높게 책정된 것 같다. 사용자의 입력이 필요한 경우가 1. 트라이 자료구조 내부의 트리에서 자식노드가 두개 이상 있을때 2. 자식노드가 한개 있는데 해당 노드가 문자열의 끝인 경우 2번 경우가 좀 비 직관적일수도 있을것 같은데 음 원하는 문자열의 끝까지 온 경우 / 다른 문..
알고리즘 재활 2일차. https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 랜덤으로 집어온 문제. trie 자료구조를 통해 해결할 수 있다. 전에 아호코라식 기초문제 풀면서 분명 다뤘던거같은데 까먹어서 다시 배웠다 https://rebro.kr/86 [자료구조] 트라이(Trie) 자료구조 [목차] 1. 트라이(Trie) 자료구조란? 2. 트라이(Trie)의 작동 원리 3. 트라이(Trie) 자료구조의 장/단점 4. 트라이(T..
우선순위 큐 문제 매워요 ㅠㅠ 일단 당장 보고 생각난건 우선순위 큐와 위상정렬이다. 근데 다시 :thinking: 과정을 한번 거쳐보고 위상정렬처럼 얘가 정확히 여기 들어간다는 보장이 없어서 우선순위큐로 풀었다. struct people에는 계산시간, 회원번호, 계산대번호 세가지를 저장하고 cmp_pq는 pq를 정렬하기 위한 비교함수, cmp_v 는 벡터를 정렬하기위한 비교함수이다. pq에다 카트를 넣음으로써 계산대가 다 찬 뒤 다음으로 나올 카트를 고를때 pq.top()으로 꺼낼 수 있게 했고, 계산을 마칠때 나오는 순서가 우선 시간순, 시간이 같을때는 안내되는 순서 = 계산대번호가 작은순으로 pq에 넣어서 뽑아주고, pq에 계산대의 갯수만큼의 사람이 들어간 경우 모두 계산중인 상황이므로 pq에서 한명..
세그멘트 트리 레이지 프로퍼게이션 문제. 이것 역시 겨울학교에서 복붙했다 ㅋㅋ www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 레이지세그는 갱신을 필요할때만 하게끔 따로 propergate()라는 함수를 작성해주는데, 이것이 구간쿼리를 더 빠르게 처리할 수 있게 해준다. #include #include #include #define MID ((s+e)/2) using namespace std; int seg[456789..