반응형 전체 글282 백준 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. [Swift] 특정 값으로 초기화 된 특정 크기의 배열 생성하기 알고리즘 문제를 풀다 보면 전부 0으로 초기화된 크기 100짜리 배열 등 특정 값으로 초기화된 특정 크기의 배열을 만들어야 할 때가 많다. 이미 애플에서 이러한 용도의 Array Initializer를 제공하기 때문에 빈 배열에 0을 100번 추가하지 않아도 된다. repeating에는 반복할 값을, count에는 배열 크기를 적어주면 된다. var arr = Array(repeating: 0, count: 5) // [0, 0, 0, 0, 0] + 풀다보니 2차원 배열이 필요할 때도 많은 것 같아 추가한다. repeating value를 단일 값이 아닌 배열로 주면 된다. let twoByThreeMatrix = Array(repeating: Array(repeating: 0, count: 3), co.. 2022. 1. 6. 백준 13334번 철로 - 스위프트(Swift) 풀이 + 그림 설명 전형적인 스위핑 문제이다. 문제에서 보여주는 그림에서 빨간색 철로를 왼쪽부터 오른쪽으로 싹 밀면서 포함되는 사람 수를 훑는다고 생각하면 된다. 이때 0, 1, 2, 3, 4, 5... 이렇게 모든 좌표마다 철로를 멈추면서 탐색할 필요 없이, 집/사무실이 있는 좌표에만 멈춰서 탐색하면 된다. (어차피 집/사무실이 없는 좌표는 카운트 변화가 일어나지 않는 의미 없는 좌표이기 때문에) 철로를 밀 때는 시작점/끝점 둘 중 하나를 기준으로 잡은 뒤, 하나씩 우측으로 이동시켜 나가면서 d를 초과하지 않게 반대점을 선택해서 최대한 길게 철로를 그리면 된다. 나는 끝점을 기준으로 잡고 풀어보았다. 아래는 그림으로 나타낸 과정인데 주황색으로 표시된 것들을 카운트하면서 철로를 밀어야 한다. 따라서 현재 좌표가 몇 번째 사.. 2022. 1. 6. 백준 18870번 좌표 압축 - 스위프트(Swift) 시간초과 해결 O(nlogn)로 풀이했는데도 계속 시간 초과가 났다. 이런 경우 대부분 입출력 문제이다. 이렇게 print 함수를 여러번 부르면 시간이 상당히 많이 소요된다. print 자체가 cost가 큰 것 같다. result.forEach{ print("\($0)", terminator: " ") } 아래와 같이 결과 문자열 하나로 압축해서 1번만 print 하도록 바꾸었더니 해결되었다. var resultString = "" result.forEach{ resultString.write("\($0) ") } print(resultString) 2022. 1. 5. 이전 1 ··· 52 53 54 55 56 57 다음 반응형
