본문 바로가기
반응형

알고리즘207

백준 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.
백준 13334번 철로 - 스위프트(Swift) 풀이 + 그림 설명 전형적인 스위핑 문제이다. 문제에서 보여주는 그림에서 빨간색 철로를 왼쪽부터 오른쪽으로 싹 밀면서 포함되는 사람 수를 훑는다고 생각하면 된다. 이때 0, 1, 2, 3, 4, 5... 이렇게 모든 좌표마다 철로를 멈추면서 탐색할 필요 없이, 집/사무실이 있는 좌표에만 멈춰서 탐색하면 된다. (어차피 집/사무실이 없는 좌표는 카운트 변화가 일어나지 않는 의미 없는 좌표이기 때문에) 철로를 밀 때는 시작점/끝점 둘 중 하나를 기준으로 잡은 뒤, 하나씩 우측으로 이동시켜 나가면서 d를 초과하지 않게 반대점을 선택해서 최대한 길게 철로를 그리면 된다. 나는 끝점을 기준으로 잡고 풀어보았다. 아래는 그림으로 나타낸 과정인데 주황색으로 표시된 것들을 카운트하면서 철로를 밀어야 한다. 따라서 현재 좌표가 몇 번째 사.. 2022. 1. 6.
반응형

티스토리툴바