Algorithm (4) 썸네일형 리스트형 Monotone Queue Optimization 동적계획법 최적화 전략이다. 이런게 있는줄도 몰랐다는게 좀 충격이다. 좀더 생각해봤으면 영감이 떠올랐을텐데,, 문제를 풀때 떠올리지 못했던게 너무 아쉽다. Deque를 이용하여 최적화 하는 전략이다. O(N^2)의 시간복잡도를 가지를 로직을 O(N)~O(NlongN)으로 줄일 수 있다. 자바 StringBuilder vs String plus 차이 String을 붙일때 +를 이용하여 붙이면 새로 만들어진 String에 객체가 생기고 jvm에서 해당하는 스트링에 대한 메모리 영역을 사용한다. 또한 지워주는 GC 작업도 생기게 된다. 따라서 스트링 연산이 빈번하다면 StringBuilder를 사용해야 한다. 보통 뒤에 붙이는 경우가 대부분이고, 이때는 append(String)를 사용하면 된다. 앞에 붙일때는 insert(0, String)을 사용하면 된다. 프로그래머스 기준으로 성능차이를 비교해봤다. StringBuilder를 쓰는 경우 그냥 + 연산을 통하여 스트링을 붙인 경우 평균적으로 30배정도 차이난다. 알고리즘이 깔끔하면 String plus 연산도 통과되기도 하지만 간혹 이거 하나때문에 성능테스트를 통과하지 못하는 경우도 생긴다. 프로그래머스 고득점 키트 고득점 키트 문제 1. 해시 1) 완주하지 못한 선수 - 완벽 2) 전화번호 목록 - 최적의 답으로 풀지 못함 3) 위장 - 최적의 답으로 풀었지만 stream을 사용한 풀이도 숙지 필요 4) 베스트앨범 - 최적의 답으로 풀었지만 stream을 사용한 풀이도 숙지 필요 2. 스택/큐 1) 기능개발 - 최적의 답으로 풀지 못함 2) 프린터 - 완벽 3) 다리를 지나는 트럭 - 완벽 4) 주식가격 - 최적의 답으로 풀지 못함 3. 힙 1) 더 맵게 - PQ를 활용안해서 최적의 답으로 풀지 못함 2) 디스크 컨트롤러 - 힌트를 얻어서 품 3) 이중우선순위큐 - 최적의 답으로 풀지 못함 4. 정렬 1) K번째수 - 완벽 2) 가장 큰 수 - 완벽 3) H-Index - 최적의 답으로 풀지 못함 5. 완전탐색 1.. 알고리즘 GIT 백준 알고리즘 문제 정리해서 푼것 git으로 엑셀과 함께 관리중이다. 완료한 TASK - 알고리즘 초급 - 알고리즘 DP 기본 엑셀에 정리한 문제 (목표 2020안) - DP 중급, 고급 들을 예정인 강의 (목표 2020안) - 알고리즘 중급 - 알고리즘 고급 https://github.com/SeongJinSong/Algorithm SeongJinSong/Algorithm Contribute to SeongJinSong/Algorithm development by creating an account on GitHub. github.com 이전 1 다음
