SH

https://www.acmicpc.net/problem/1460  접근이 어려워서 포스팅 보고 시작했다.https://magentino.tistory.com/95  1.  씨앗을 최대 두 종류 포함했는지 판별 농장을 범위를 선택하고, 포함된 과일 씨앗를 체크한다. X씨앗을 두 개 뽑은채로 농장 범위를 선택한다. O m[i][j]가 두 개의 씨앗 중 하나라면 dp[i][j] = 1로 놓는다.그러면 dp가 0-1 값으로 초기화된다. 2. 씨앗 두 개씩 뽑기씨앗은 8가지 밖에 없고, 순서도 상관 없으므로 조합으로 뽑는다.  3. dp 도출dp[i][j] = 좌표 (0,0)부터 (i,j)까지 고려했을 때, 준규가 가져갈 수 있는 농장의 최대 길이 dp[i][j] = 0이라면, 0번 씨앗 or 선택하지 않은 씨..

https://www.acmicpc.net/problem/1197 MST 기본 문제 (크루스칼 사용함)  가중치 오름차순 정렬된 edges를 순회하며,  V-1개의 간선을 만들면 종료한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer;class Main { static class Edge impl..

https://www.acmicpc.net/problem/24391 유니온-파인드를 통해 분리 집합을 구성하고,주어진 경로를 탐색하며 부모(== 분리 집합 대표자)가 바뀐 횟수를 구하는 문제다. 단, 첫 원소 (맨 처음 강의를 들으러 이동)는 세지 않는다. 간만에 푸는 문제 분류라 첫 ac에 빵꾸가 많았다. 이후 수정해서 700 -> 400ms로 줄였다. 1. find에서 좌표 압축2. parent 최신화하고 탐색 -> find()로 탐색3 priority 배열 제거(문제에서 강의 순서가 존재한다. 유니온 대표자를 정하는 기준으로 사용했는데, 결과적으로 불필요했다.)4. 간선(edge)안만들고 바로 union (심지어 양방향으로 만들어서 union 두 번씩 함)5. path 배열 제거 이전 코드더보기im..

https://www.acmicpc.net/problem/1887 비트마스킹 문제 i for 0 to MAX(== 0bT):   bit for 0 to N - 1: 까지 탐색하며, [i AND bit != bit]를 만족하는 i 개수를 찾는 문제다. 문제 유형만 깨달으면 구현은 쉬웠고, 소가 진짜로 피자를 좋아하는진 모르겠다.  + 흥미로운 내용 : bit 배열 오름차순 정렬하면, 앞의 원소가 뒤의 원소에 포함될 확률이 높아지므로 약간의 성능향상을 노려볼 수 있다.   import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;class Main..

https://www.acmicpc.net/problem/1361 브루트포스 + 문자열 처리 문제 핵심 조건1. 그리디 or 많은 조건 분기로 푸는 방법은 없거나 매우 까다롭다.2. A 혹은 B보다 더 긴 문자열을 집어넣어서 최적인 경우는 없다. 접근법 세우기1번에 의해 브루트포스를 해야하며,2번에 의해 N=50일 때 복잡도를 O( 50(50-1)/2 * 50(50-1)/2) == O(150만) 정도로 잡아서 적용할 수 있다고 생각했다. 아이디어1. str1, str2에 대해 *을 기준으로 head와 tail을 나눈다. 2.String comp1 = head1 + sub2 + tail1;String comp2 = head2 + sub1 + tail2; comp1 == comp2라면, 정답을 갱신한다.  ..

https://www.acmicpc.net/problem/1277 1번째 노드 -> N 번째 노드 (발전소) 의 최단경로(전선 길이)를 구하는 다익스트라 문제 모호한 조건, 조건을 무시해야 ac인 기이함, BFS로 비비기 시도가 겹쳐서 한 페이지 다 채울정도로 틀렸다.https://www.acmicpc.net/board/view/156457 "연결된 발전소"의 처리가 중요하다. 연결된 발전소란, 현재 발전소에서 전선 길이 0으로 도달할 수 있으며, x/y좌표 값이 바뀜을 의미한다. 두 가지 탐색을 진행한다. 1. "연결된 발전소"에 대해 비용 갱신이 발생한다면, (현재 값)을 기록하고 pq에 넣는다.2. "자신이 아닌 모든 발전소"에 대해 비용 갱신이 발생한다면, (현재 값 + 필요한 전선 길이)을 ..

https://www.acmicpc.net/problem/1238 다익스트라 문제그래프가 단방향이므로, X에 가는 경우와 갔다가 돌아오는 경우 두 번을 탐색해야 한다. 접근법 1. 돌아오는 경로 X -> ALL 탐색을 한 번 한다.2. 가는 경로 모든N -> ALL 탐색을 N번 한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer;class Main ..

https://www.acmicpc.net/problem/1240 일반적인 그래프탐색 문제다. 플로이드-워셜도 시간복잡도 아슬하게 적용 가능하다.(단, 트리이므로 경로가 유일해서 최단 경로 알고리즘은 비효율적이다.) 그래프 탐색간 틀린 이유cost[][] 배열을 썼는데, 메모리 제한이 짠 문제여서 초과함 (경로가 유일하므로 min cost 배열 필요 없음) 풀이 1. BFSimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queu..

https://www.acmicpc.net/problem/1132 기본 아이디어1. 알파벳별로 자릿수 가중치를 기록한다. (dp로 기록했는데, 하나의 변수만 써도 충분할 것 같다.)2. 가중치가 높은 순서대로 9, 8, ... 1을 곱해서 정답에 더한다. (그리디)  0으로 시작하는 수는 없다. 이 조건을 "입력에 0으로 시작하는 수는 주어지지 않는다."로 잘못 해석했다.문제의 의도는 "0으로 시작하는 수는 사용하면 안된다." 이다. (예제랑 입력 조건으로 유추가능) 기댓값이 높은 것부터 탐색하면, 0만 남았을 때 0을 쓸 수 없으면(앞자리가 0인 수가 존재하게 되면) 답이 아니게 된다. 따라서, 기댓값이 낮은 것부터 탐색하는게 낫다. 나는 조건을 잘못봐서 전처리로 0체크만 따로 추가했다. (그래서 스파..

https://www.acmicpc.net/problem/1068 트리에서 노드를 하나 끊었을 때 리프 노드의 개수를 구하는 문제 1. 루트 노드 정하기트리에서 부모가 없는 노드는 유일하며, 루트 노드가 된다 (루트 노드를 어디로 잡냐에 따라 리프 노드 개수 또한 달라진다.)(어디던 루트로 잡아도 되지않나 해서 모호했는데, 문제에서 "연결된 노드" 가 아니라 "부모 노드" 목록이 주어진다.) 2. 노드 끊는법 정하기단순히 방문처리(vst[REMOVE] = true)한다.이러면 끊은 노드 및 서브 트리를 방문하지 않게된다. + 문제에선 한 개의 노드만 끊는다. 3. 리프 노드 기준 정하기vst[next] = false 일 때만 다음 탐색을 진행한다.다음 탐색을 한 번도 하지 않았다면 이는 곧 리프 노드다...