본문 바로가기
반응형

Problem Solving242

백준 3015번 오아시스 재결합 - 스위프트(Swift) 풀이 + 그림 설명 어디서 많이 본 것 같은 느낌이 나면서도 중복 처리가 힘들었던 문제. 일단 기본 아이디어는, X보다 더 큰 사람 Y가 나오는 순간, 이제 Y보다 뒤에 있는 사람들은 X를 볼 수 없으므로 X를 더 이상 고려하지 않아도 된다는 것이다. 배열을 순차 탐색하면서 증가 때마다 무슨 일이 일어나고.. 왠지 스택을 쓰면 뭔가 될 것 같은 느낌이다. 아래와 같이 [3, 2, 2, 1, 2]로 주어진 상황이라고 하자. 손으로 풀어보면 그림과 같이 8쌍이 서로 볼 수 있다. 왼쪽부터 순차 탐색할 것이므로 A와 B가 서로 볼 수 있다면, 더 우측에 있는 B차례에서 카운트+1을 해줄 것이다. 아까 말했던 기본 아이디어, 더 큰 사람이 올 때까지 이제 스택에 일단 한 명씩 담자. 계속 더 작은 사람만 담다보면 스택 내부는 항상.. 2022. 1. 8.
백준 16287번 Parcel - 스위프트(Swift) 풀이 + 그림 설명 아이디어가 생각이 안 나서 결국 검색으로 해결한 문제ㅠㅠ DP라는 것은 감이 왔는데 지금까지 풀었던 DP 방식은 시간 초과 때문에 적용할 수가 없었다. 처음에 떠올렸던 방식은 dp(count, index, targetWeight) = weights[index...] 에서 count개의 소포를 뽑아 targetWeight를 딱 맞출 수 있는지 여부로 두고, index번째 item을 뽑는 경우 & 뽑지 않는 경우를 모두 고려하여 아래와 같은 식으로 푸는 것이었다. 하지만 count는 4, index는 5000, targetWeight는 무려 799,994여서 4*5000*799,994로 시간 안에 풀어낼 수가 없다.. dp(count, index, targetWeight) = dp(count - 1, ind.. 2022. 1. 7.
백준 14725번 개미굴 - 스위프트(Swift) 풀이 + 그림 설명 solved.ac CLASS 6 따려고 시작한 문제인데, 문제 조건에 제대로 명시되지 않은 것이 있어 도대체 무슨 문제인지 헤맸다. 첫 번째 입력 예를 보면서 아래 두 가지 모두 가능하다고 생각했다. 루트-리프로 가는 경로들 만으로는 절대 트리를 하나로 특정할 수가 없는데... 근데 또 정답 비율은 66%나 돼서 나만 이해를 못 하고 있구나 싶었다. 예제 입출력 2개를 한참 보고 나서야 설마 이건가? 하는 규칙을 찾았는데, 트라이 문제인 것 같았다. (너무 오랜만에 PS를 해서 트라이의 존재를 잊고 있었다ㅠㅠ) 풀고 나서 질문/검색에 가보니 https://www.acmicpc.net/board/view/18583 역시나 조건 추가 요청 글이 올라와있었다. 문제 오류가 맞는 것 같다. 66%의 사람들도 아.. 2022. 1. 6.
백준 2533번 사회망 서비스(SNS) - C++(cpp) 풀이 DP 문제이다. dp(idx, isParentEarly) = 부모의 얼리어답터 여부가 isParentEarly일 때, idx번 노드를 루트로 하는 부분 트리를 완성하기 위한 얼리어답터의 수로 두고 풀었다. 부모의 얼리어답터 여부를 파라미터에 둔 이유는 이것이 자식인 idx번 노드의 얼리어답터 여부에 영향을 미치기 때문이다. 1. 부모가 얼리어답터인 경우 : idx는 얼리어답터여도 되고, 아니어도 된다. 둘 중 min값을 취하면 된다. 2. 부모가 얼리어답터가 아닌 경우 : idx번은 무조건 얼리어답터여야 한다. 부모의 인접한 노드는 모두 얼리어답터야 하기 때문에 자식인 idx는 선택권이 없다. 따라서 아래와 같은 로직을 세울 수 있다. 최종적으로는 dp(루트, true)를 출력하면 된다. 루트는 부모가 .. 2022. 1. 6.
백준 2533번 사회망 서비스(SNS) - 스위프트(Swift) 시간초과 해결 이번에도 또 알 수 없는 시간 초과가 발생해서 해결하는 데 애를 먹었다. 아무래도 Swift로는 PS는 하지 않는 게 정신 건강에 좋을 것 같다ㅠ 이번 범인은 고차함수였다. 아래 글을 발견했는데, map은 확실히 반복문으로 직접 구현하는 것보다 성능이 좋았고, filter는 비슷하고, reduce는 오히려 반복문으로 직접 구현하는 게 더 빨랐다고 한다. 다만 이건 전부 체이닝 하지 않고 고차 함수를 1번만 쓰는 경우에만! 여러 고차 함수를 체이닝 하면 오히려 직접 구현보다 심각하게 성능이 좋지 않다고 한다..;;; 문제에서 reduce랑 체이닝을 남발한 부분이 있었는데 for문으로 고쳐주었더니 시간 안에 통과가 됐다. https://www.skoumal.com/en/performance-of-built-.. 2022. 1. 6.
반응형

티스토리툴바