SH

https://www.acmicpc.net/problem/1743 그래프 탐색 문제 인접한 '#'끼리 붙여 도형을 만들었을 때, 넓이가 가장 큰 것(의 넓이) 출력 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Queue;import java.util.StringTokenizer;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamR..

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체크만 따로 추가했다. (그래서 스파..