onaeonae1

www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 설명 어떤 집합(1~20까지 있음)이 있다고 가정할 때, 그 집합에 대한 일련의 연산들을 처리하는 문제이다. 문제 풀이 집합이라는 이름만 듣고 허겁지겁 다른 집합 관련 알고리즘들을 떠올렸던 것 같다. 사실 직접 비슷한 집합 구조를 구현하고 문제를 풀어도 틀리지는 않을 것 같다. 다만 그렇게 구현하려면 많이 귀찮기도 하고 요소가 20개 정도인 집합에 적용하기에는 비효율적이다. 집합의 요소가 20개로 한정되어 있고, 그것이 있거나(1) 없거나(..

www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 문제 설명 두 사람의 키를 비교한 관계들이 쭉 주어질 때 (가능한) 키 순서를 출력하면 되는 문제 문제 풀이 -그래프에서 정해진 노드끼리의 간선등 정해진 순서가 있을 때, 이를 위반하지 않으면서 그래프 전체의 노드를 방문하는 경우를 가져오는게 위상정렬 문제의 특징이다. -위의 문제는 기본적인 위상정렬 문제라서 크게 변형할 것이 없었다. 바로 연결 관계 받고, 위상 정렬 구현해..

https://www.acmicpc.net/problem/17827 17827번: 달팽이 리스트 첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 C1, C2, …, CN이 공백 www.acmicpc.net 굉장히 쉽고 힌트에 나와있는 부분에 대한 예외처리(민달팽이)를 해줄 필요 없이 바로 일반항을 구해줄 수 있다. N M V가 주어지고, num번째 수가 궁금할때, num=N인 경우의 정답을 target이라고 했을 때, target = (num-N) % gap + V 이다. 이때 gap은 (N-V+1) 이다. 말로 이렇게 쓰니까 상당히 직..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 이번에도 위상정렬을 쓰는 문제다. 위상정렬을 쓰는 문제들은 그래프에서 순서가 주어지는데, 이 문제에서는 하나의 조건이 더 추가된다. 일단 문제를 풀어 써보자. 1~N까지 총 N개의 문제들로 구성된 문제집이 있다. 1이 가장 쉽고, N이 가장 어렵다.(=번호가 낮을 수록 쉬운 문제이다.) 그리고 주어지는 조건은 다음과 같다. N개의 문제를 모두 풀어야 한다. 주어진 순..

문제 링크 https://www.acmicpc.net/problem/10769 10769번: 행복한지 슬픈지 문제 승엽이는 자신의 감정을 표현하기 위해서 종종 문자 메시지에 이모티콘을 넣어 보내곤 한다. 승엽이가 보내는 이모티콘은 세 개의 문자가 붙어있는 구조로 이루어져 있으며, 행복한 얼굴을 나타내는 :-) 와 슬픈 얼굴을 나타내는 :-( 가 있다. 혜성이는 승엽이의 이모티콘을 귀여운 척이라고 생각해 매우 싫어하므로, 승엽이의 문자가 오면 전체적인 분위기만 판단해서 알려주는 프로그램을 작성하고 싶다. 입력 첫 줄에 최소 1개에서 최대 255개의 문자들이 입력된 www.acmicpc.net 문제 설명 문자열 ":-)" 가 등장한 횟수와 문자열 ":-(" 가 등장한 횟수를 세서 비교해주는 문제 풀이 -문자..