Algorithm/SWEA (SW Expert Academy) (4) 썸네일형 리스트형 [SWEA] 4038. [Professional] 단어가 등장하는 횟수 (with JAVA) 문제 4038 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 처음에는 정말 단순한 방법으로 하나씩 비교해가며 풀었습니다. 당연하게 시간초과가 났고, 좀 더 효율적으로 푸는 알고리즘인 KMP 알고리즘을 활용하여 해결하였습니다. KMP 알고리즘을 살펴보기에 앞서, 단순하게 비교하며 푸는 방법에서 어떤 부분을 효율적으로 개선시켜야 하는지에 대해 알아보겠습니다. 탐색할 문자열이 "ababa" 일 때, "aba" 가 몇 번 들어가는지를 알아보려고 합니다. 아래는 제가 처음에 풀었던 방식입니다. 이렇게 해서 총 2번이 들어가는 것을 확인할 수 있지만, 총 7번에 걸쳐서 찾을 수 있었습니다. 즉, 찾으려는 단어의 길이가 .. [SWEA] 3000. 중간값 구하기 (with JAVA) 문제 3000 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 중간값을 구하는 방법 중에서 우선순위 큐 (Priority Queue)를 사용해보겠습니다. 삽입할 때마다 중간값을 구하는 문제로, Heap 으로 구성된 Priority Queue 를 사용합니다. 시간 복잡도는 O(nlogn) 입니다. 중간값을 구하기 위해서는 아래와 같은 규칙을 따라야 합니다. 1. 제일 처음에는 최대 힙에 삽입 2. 최대 힙의 크기는 최소 힙의 크기와 같거나 하나 더 큼 3. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같음. 즉, 최대 힙의 루트 노드 [SWEA] 4006. 고속도로 건설 2 (with JAVA) 문제 4006 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [ 접근 과정 ] 문제에서 이미 '최소 비용' 이라는 말이 나와있어서, 가중치를 계산하는 문제라는 것을 알 수 있었습니다. '최소 비용으로 모든 도시 간을 이동할 수 있게' 라는 부분에서 크루스칼 알고리즘을 사용하면 좋을 것 같다는 생각을 했습니다. 여기서의 간선은 도로이기 때문에 무향 그래프로 이해했고, 도로를 기준으로 최소 비용의 도로들을 선택해서 모든 도시를 이을 수 있어야 하기 때문에, 사이클이 없어야 하는 크루스칼 알고리즘으로 해결했습니다. 크루스칼 알고리즘을 공부하기에 앞서 서로소 집합을 트리로 표현하는 부분에 대해 먼저 알고 있어야 합니.. [SWEA] 1251. 하나로 (with JAVA) 문제 1251 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [ 접근 과정 ] 문제를 보면, 섬들 간의 거리를 간선의 가중치로 볼 수 있습니다. 가중치 하면 기본적으로 떠오르는 알고리즘이 다익스트라였기에 다익스트라 알고리즘을 이용해서 풀었습니다. 다만, 이전까지 다익스트라 알고리즘 기본 문제들을 풀었을 때는 간선들의 가중치가 주어졌었지만, 이번 문제는 가중치도 직접 구해야 했습니다. [ 고민했던 부분 ] 1. 각 섬들의 위치를 어떻게 저장할 것인가? 각 섬들의 위치를 저장할 때 ArrayList() 를 써야하나 고민했지만, 문제에 나온 x, y 의 범위를 고려했을 때 2차원 배열로 해도 충분할 것이라 생각해서.. 이전 1 다음
