본문 바로가기
반응형

PS 문제 풀이/SWEA75

[SWEA] 3816 아나그램 출처: [SWEA] SW 문제해결 심화 - Ad Hoc Algorithms Input 4 aba ababababa abra abracadabra anan bananaparanabrazil ab abba Output #1 4 #2 2 #3 2 #4 2 ① S1을 문자를 int형 배열에 저장한다. (Alphabet 빈도 수를 저장) ② S2를 S1의 길이만큼 부분문자열 구해서 int형 배열로 변환한다. ③ 알파벳 개수를 통해 Anagram 여부를 판단. import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // TestCase 개수 i.. 2021. 3. 1.
[SWEA] 3819 최대 부분 배열 출처: [SWEA] SW 문제해결 심화 - Ad Hoc Algorithms Input 2 1 3 5 1 3 -5 3 6 Output #1 3 #2 9 연속되는 부분 배열의 최대합을 구하는 문제 import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = Integer.parseInt(sc.next()); for(int tc=1; tc 2021. 2. 28.
[SWEA] 2814 최장경로 출처: [SWEA] 문제 링크 Input 2 1 0 3 2 1 2 3 2 Output #1 1 #2 3 첫번째 Case는 간선 없이 정점 한개 존재하므로, 최장 경로의 길이 = 1 두번째 Case는 [3] - [2] - [1] or [1] - [2] - [3], 최장 경로의 길이 = 3 출발 정점을 [1] ~ [N]으로 해서 연결된 모든 간선을 DFS 탐색하여 최장 경로의 길이를 구합니다. private static void DFS(int current, int cost, boolean[] visited) { visited[current] = true; // 정점 [current]와 연결된 정점 리스트 List to = adList.get(current); for(int i = 0; i < to.size.. 2021. 2. 27.
[SWEA] 1768 숫자야구게임 출처: swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4su3xKXFUDFAUf& Input 5 8975 6142 5047 1860 5419 Output #1 6 #2 8 #3 7 #4 8 #5 7 total score = 100 total query = 36 player2가 제시한 player1이 생각하는 수와 일치하는지는 0234~9876까지 완전탐색하며 확인할 수 있습니다. 하지만 그렇게 되면 일치하는지 확인하는 query 함수 호출은 최대 9876 - 0234번 필요합니다. for (int i = 123; i 2021. 2. 27.
[SWEA] 4006 고속도로 건설 2 출처: [SWEA] SW 문제해결 심화 - 그래프 Input 1 5 8 1 2 4 1 3 9 1 4 21 2 3 8 2 4 17 3 4 16 5 2 20 5 4 30 Output #1 48 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소 신장 트리(MST, Minimum Spanning Tree) ; 사이클을 형성하지 않으면서 모든 간선(Edge)가 최소로 연결된 그래프. ※ 신장 트리(Spanning Tree); 사이클을 형성하지 않지만 모든 노드가 간선(Edge)로 연결. zoosso.tistory.com 최소 신장 트리를 구현하는 알고리즘은 크루스칼과 프림 알고리즘이 존재하는데 해당 문제는 크루스칼 알고리즘 이용. i.. 2021. 2. 27.
[SWEA] 3947 가장 짧은 길 전부 청소하기 출처: [SWEA] SW 문제해결 심화 - 증명의 중요성 Input 2 5 5 1 2 1 4 3 2 1 3 1 2 4 2 5 4 3 4 4 1 2 1000 2 3 100 3 4 500 1 4 600 Output #1 7 #2 1700 [1] - [2], [2] - [4], [4] - [5], [1] - [3] 가중치 합: 1 + 2 + 3 + 1 = 7 위의 예제로만 보면 최소 신장 트리를 구성하는 Prim's Algorithm을 적용하면 되지만, [Test Case #2] 가중치 합: 1000 + 600 + 100 = 1700 입니다. [정점 [1] 기준 Prim's Algorithm 결과] 이는 최소신장트리 ≠ 최단 경로이기 때문입니다. 최소신장트리에서는 정점[1] → [2]까지 600 + 500 +.. 2021. 2. 25.
[SWEA] 4007 간담회 참석 출처: [SWEA] SW 문제해결 심화 - 그래프 Input 1 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 Output #1 10 임의의 정점 [x]과 나머지 정점들을 [i]라고 했을 때, [i] → [x] → [i]까지의 최단 거리 비용이 가장 큰 비용을 구하는 문제입니다. 구현 플로이드 와셜 알고리즘을 이용해서 모든 정점들의 최단 거리 비용을 구할 수 있지만, [1 ≤ N ≤ 50,000, 1 ≤ M ≤ 500,000]이기에 TLE 발생 그렇기에 다익스트라(Dijkstra) 이용 다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로.. 2021. 2. 25.
[SWEA] 4066 All Pair Shortest Path 출처: [SWEA] SW 문제해결 심화 - 동적 계획법 Input 1 3 3 1 2 1 2 3 2 3 1 3 Output #1 0 1 3 5 0 2 3 4 0 모든 정점에 대해 최단 거리 비용을 구해야 하므로 플로이드 와샬 (Floyd Warshall)을 이용합니다. 플로이드 와샬 (Floyd Warshall) 개념 아래와 같은 가중 그래프에서 최단 경로를 찾는 알고리즘. ex) 정점 ③ → ⑤로 가는 최단 경로는 다음과 같습니다. 경로Path: ③ → ② → ④ → ① → ⑤ 비용Cost: +4 +1 +2 -4 = 3.. zoosso.tistory.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStre.. 2021. 2. 25.
[SWEA] 3260 두 수의 덧셈 출처: SWEA Input 2 1 2 100000000000000000000000001 9 Output #1 3 #2 100000000000000000000000010 자릿수가 작지 않기 때문에 문자열 배열을 이용해서 처리 #include #include #include using namespace std; int main(){ int testCase; cin >> testCase; for (int tc = 1; tc > A >> B; // 더 작은 숫자 자릿수 채워주기 int n = A.size(), m = B.size(), len = max(n, m); if (n > m) for (int i = 0; i < n - m; i++) B = "0" + B; else for (int i = 0; i < m .. 2021. 2. 24.
[SWEA] 9780 외계인 침공 출처: SWEA Input 2 2 10 20 6 5 9 1 3 7 2 Output #1 20 #2 16 DP 관점에서 문제를 해결할 수 있습니다. (부분문제 해결) ex) 도시 = [1 2 3 4 5]가 있을 때, (도시에 사는 개구리 수와 상관없이) 많은 도시를 침공할 수 있는 경우? 1 → 3 → 5를 차례로 공격하는 경우입니다. 문제 규칙에 따르면 침공한 도시의 양옆은 납치할 수 있는 개구리가 없습니다. 결국, 도시에 사는 개구리 수에 따라 도시를 공격할 지, 아니면 다른 도시를 공격할 지 결정해야 합니다. ▶ DP[i] = max(DP[i - 2] + A[i], DP[i - 1]) : i번째 도시까지 침공했을 때 납치할 수 있는 개구리의 최대값 도시가 1개인 경우, 개구리 수와 상관없이 침공. →.. 2021. 2. 24.
반응형

티스토리툴바