전체 글

https://www.acmicpc.net/problem/25556 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 문제가 스택을 이용해야할거 같지만 풀이과정에서 굳이 스택이 필요한가 싶다. (물론 스택 자료구조에 대한 이해는 필요하다)4개의 스택이 있다고 했으니 크기가 4인 벡터를 만들어서 각각 스택의 최상위 값만 벡터에 담는 식으로 하여 스택없이 문제를 해결하였다.Greedy한 문제인데 풀이는 별로 어렵지 않다. 순열에서 숫자를 하나씩 꺼내서 벡터에 넣는데, 4개의 스택이라고 정해놓은 곳의 숫자보다 큰 값만 들어와야지 다시 일렬로 낼 수 있다.그 뜻은 순열이 숫자가 감소하는 부분이 5번 이상 나오면 스택에 넣을 자리가 없다는 ..

https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net C++ 연습을 위해 C++로 하려고 했는데 문자열 = 파이썬이라는 명언을 기억하고 파이썬으로 풀었다. 맨처음에는 최대로 문자열을 줄였을때 P가되면 PPAP문자열이다.라고 생각하고 코드를 짰더니 O(n^2)이 나와서 다시 지우고 다시했다. O(n)으로 즉 한번의 탐색만으로 문자열을 최대로 줄이기 위해 스택을 이용하였다.예를들어 PPPAPAP가 있다고 하면하나씩 스택에 넣다가 마지막 4개의 문자가 'P', 'P', 'A', 'P'이면 'P'로 만들어야..

https://www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 이런 형식의 문제를 처음 접한것은 아마 초등학교 5학년때 였을 것이다. 작은 숫자를 손으로 풀려고 하면 쉽지만 코드로 구현하려면 최대공약수와 최소공배수를 잘 활용해야한다.주어진 비율의 숫자들의 최소공배수를 구하여 특정 숫자하나를 최소공배수로 잡는다.그리고 주어진 비율에 따라 다른 숫자들도 모두 비율에 맞춰 구한다.그리고 구해진 질량들의 최대 공약수로 나누어주면 된다. import sys input..

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좌표를 입력받고 ..