랄뚜기의 코딩일기

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 메모리를 4MB만 주어지기 때문에 비트마스킹으로 풀어야 하는 문제이다. 비트마스킹의 개념을 알고 싶다면 꼭 풀어야할 문제. 코드 #include #include using namespace std; int M, num, BIT=0; string s; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>M; while(M--){ cin>>s; //비스마스킹에서 1n..

https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 오랜만에 보는 매우 쉬운 문제. 자식 노드를 N이라고 할 때, 부모 노드는 (N-1)/K라는 것을 이용하면 금방 풀린다. 단, 출력이 많으므로 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);을 하는 것을 잊지말자!(개고생함) #include using namespace std; long long..

https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 이진트리에서 전위순회와 중위 순회가 주어졌을 때, 후위 순회를 구하는 문제이다. 저번에 후위 순회와 중위 순회가 주어졌을 때 전위 순회를 구하는 문제를 풀어서 쉽게 풀 수 있었다. https://coderecord.tistory.com/5 [BOJ] 2263 트리의 순회 C++ https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 알고리즘의 분류에 트리, dp 이렇게 적혀 있길래 한참 고민했다. BFS를 이용하여 각 depth마다 최소로 필요한 얼리어답터들을 저장하며 풀었는데 예외상황이 발생했다. 그래서 그냥 dfs에 조건을 넣어서 풀었다. 조건 1. 자식에 리프노드가 존재한다면 무조건 얼리어답터가 되야 한다. 2. 자식 중에 얼리어답터가 아닌 사람이 한 명이라도 존재한다면 부모는 얼리어답터가 돼야 한다. 이 조건을 ..

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트리라고 적혀있어서 들어갔는데 그리디가 먼저 보여서 그리디로 풀었다. C++의 STL을 활용하면 아주 쉽게 풀 수 있는 문제이다. 전화번호가 12345 12 1589 98 159 이렇게 주어졌다고 하자. string으로 값을 받고 배열 arr에 저장 후 sort를 해주면 사전 순으로 sort를 해주는데 그럼 12 12345 1589 159 98 이렇게 sort가 된다. 여기..

https://www.acmicpc.net/problem/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 트리의 지름을 구하는 것을 응용한 문제이다. 아래 문제를 먼저 풀고 들어오면 괜찮을 것 같다. https://coderecord.tistory.com/9 [BOJ] 1167 트리의 지름 C++ https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 1..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 이 문제를 대충 요약하자면 트리에서 정점->정점까지 가장 긴 거리를 구하는 것이다. 내가 이 문제를 보고 무조건 시작 또는 끝에는 트리의 리프노드일 것을 알았다. 그래서 모든 리프노드(연결 된 노드가 하나밖에 없는 노드)를 구해서 dfs를 각각 돌려 그 중 최댓값을 구하면 되겠다고 생각했는데 바로 시간초과가 떴다. 고민을 하다가 다른 분의 코딩을 참조 했는데 알고리즘은 다음과 같다..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이 문제는 숫자가 추가로 저장 될 때마다 저장된 숫자 중 가운데 값을 말하는 문제이다. 주어진 시간이 단 0.1초이므로 sort를 쓰게 되면 무조건 시간초과가 나게 된다. 나는 중간이라는 말을 듣고 최대 힙과 최소 힙을 사용하면 되겠다고 생각했다. 중간값을 최대 힙의 탑으로 정하고 중간값 보다 값이 작으면 최대 힙에 값이 크면 최소 힙에 넣어주고 최소 힙의 탑의 값이 바뀌는 경우 ..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 일반적인 계산식(중위 표기식)이 주어졌을 때, 이를 후위 표기식으로 바꾸는 문제이다. 괄호가 들어가서 예외 처리를 많이 해야 하는 문제이지만 다행히 사람들이 많은 반례를 구해놓아서 쉽게 구할 수 있었다. 후위->중위, 중위->후위로 변환할 때는 stack을 이용하면 된다. 또, 이 문제를 풀 때 개념은 계산순서의 우위를 이용해야 한다는 것이다. 1. * , / 이 올 경우 자신보다 계산순..

https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 후위 표기식이 주어졌을 때 이를 계산하는 문제이다. 스택을 만들고 연산기호( * , / , + , - )가 오는 경우는 위에서 두개를 계산하고 push 그 외에는 그냥 push해주면 된다. 코드 #include #include #include #include #define ch 65 using namespace std; string s; double alpa[26]; int main()..