https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름: 노드와 노드 사이의 거리가 가장 긴 거리 이 문제에서의 트리는 가중치가 있는 트리이므로 거리를 구할때 그냥 +1씩 하는 것이 아니라 가중치를 저장했다가 가중치를 더해주어야한다. 이 문제에서 중요한 개념이 하나 있다 "임의의 노드에서 가장 긴 경로로 연결되어 있는 노드는 트리의 지름에 해당하는 두 노드중 하나이다." 위의 개념을 이용하여 단 2번의 탐색으로도 가장 긴 ..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 스택을 이용하는 문제로 이전에 포스팅했던 스카이라인 쉬운거와 오큰수하고 비슷한 문제이다. 자신만만하게 들어갔는데 한번pop한 탑은 다시 넣어줄필요가 없는데(어차피 뒤에 더 큰 탑이 있어서 거기에 걸림) 왠지 모르겠지만 다시 넣어버려서 시간초과좀 걸렸다. 아쉽다. 그리고 파이썬을 사용할때는 튜플이 익숙해서 편하게 사용했지만 C++에서는 아직 pair쓰는게 익숙하지 않아서 그냥 인덱스용 벡터 하나 ..

https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 처음보면 문제가 무슨 말인지 알아먹기가 힘들다. 문제를 풀긴 했지만 문제 뜻을 정확히 이해하고 푼건 아니고, 예시를 보고 했다. 구하라는 것은 스카이라인 좌표를 보고 최소 건물의 개수를 구하라는 것이다. 푸는 방법은 이전에 포스팅 했던 오큰수하고 비슷하다.(거의 똑같음) x좌표는 필요없어서 안썼고, y좌표의 높낮이가 중요한데 y좌표를 입력받고 ..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net Greedy한 유형으로 핵심은 문자에 숫자를 대응하기 전에 모든 단어에 같은 알파벳이 얼마나 있는지가 중요하다. 처음에는 가장 왼쪽에 있는 알파벳부터 9를 대입하는 방식을 고안했는데 바로 틀렸다. 반례를 이러하다. ABBBBBB B BBB.....위으 경우와 같이 특정 개수이상 B가 계속 나오는 경우에는 A보다 B의 숫자가 더 커야지 최댓값이 되기 때문에 문자와 숫자를 대응하기 전에 자릿수를..

https://www.acmicpc.net/problem/1325 > n >> m; bool* visited = new bool[n+1]; memset(visited,false,sizeof(visited)); int* ans = new int[n+1]; vector com(n+1,vector()); for(int i = 0; i > a >> b; com[b].push_back(a); } for(int i = 1; i < n+1 ; i++){ BFS(i, com, visited, ans); fill_n(visited, n+1, false); } int max_val = *max_element(ans+1, ans + n+1); for(int i = 1; i < n+1; i++){..

https://www.acmicpc.net/problem/18114 18114번: 블랙 프라이데이첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ 108, N과 C는 양의 정수) 다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진www.acmicpc.net알고리즘 분류에 보면 이분탐색이 들어가 있지만 본인은 투포인터 + 브루트포스로 풀었다.일단 정렬한 배열의 처음과 끝을 투포인터로 잡았다.그리고 투포인터로 잡은 상태에서 브루트포스를 돌려서 변수 3개를 설정했다.x(처음), y(끝), i(for문)투포인터는 고정시키고 for문을 돌려서 각각 하나, 둘, 셋의 합이 C와 같으면 ans = 1로 설정했다.그리고 for문이..