전공공부

설명 문제 조건을 요약하면 최소가 되는 두 동내의 연결 길의 합을 구하는 것인데 우선 처음 시작이 한 동내에서 두 동내로 끊는것이다. 그렇기 때문에, MST로 모두 연결하고 이때 최대의 값을 가지는 간선을 제외 시켜 버리면 최소합으로 갈 수 있는 두 동내의 연결 길을 만들 수 있다. 코드 package MST; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.StringTokenizer; /** * MST 활용 문제 * 도시 분할 계획 * * 두 동내의..

설명 R로만 이루어진 문자열은 ㅋㅋ루ㅋㅋ 문자열이다. 단, 빈 문자열은 ㅋㅋ루ㅋㅋ 문자열이 아니다. ㅋㅋ루ㅋㅋ 문자열 양 끝에 K를 하나씩 붙인 문자열은 ㅋㅋ루ㅋㅋ 문자열이다. 부분 수열으로 더해지는 것을 생각을 하고 풀어야 이해가 되는 문제다. 처음 이해 자체가 되지 않아서 무슨 문제인지 파악하는 것이 어려웠다. KKK RKRRKRKRKRKR KK 일때, K 갯수가 2이고 여기서 중간의 R은 제외되어서 보여야 한다. 그래서, 이렇게 나누어진 것을 보면 최소 K 2*2 + 중간에 존재하는 R의 갯수 7개를 더하면 값이 나오는데 이런 방식을 투포인터로 반복하면서 나가면서 최댓값을 구하는 것을 코드로 구현하면된다. 다음에는 KK가 최소 값이 나왔으니 r을 줄여서 다음 KRKK 까지 탐색하여 한 번 더 체크하..

설명 2가지의 경우의 수를 먼저 고르고 O(N*N) 그리고 이때 투 포인터로 하나의 경우를 더 찾는 로직으로 눈사람을 설치 할 수 있다. 처음에 for문으로 투 포인터 방식을 생각하다가 잘 못 짜서 S는 무조건 상승하는 방식의 로직으로 구성해서 틀렸습니다가 많이 떴다. 생각해보면 S의 경우도 당연히 조건에 따라서 움직여야 하는데 생각이 얕아 고생을 했던 문제 총 시간 복잡도 : O(N^3) 코드 package two_pointer; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class BOJ_20366 { static int ans = Integer.MAX_VALUE; static L..

설명 같은 로직으로 C++으로 제출하면 맞는 정답이다. 자바의 경우 로직은 같으나 해당 코드로 통과되지는 않는다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static boolean [] visited; static int max; static int[] ans; static List[] graph; public static void main(String[] args) throws Exception{ BufferedReader in = n..

설명 로직을 따라서 폭탄을 설치한다. 그리고, 폭탄 설치시 이미 그 전에 설치된 폭탄이라면 다음번에는 폭발 할 수 있게끔 체크 하는 로직을 추가했다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static char[][] map; static boolean[][] check; static int R, C, N; static int dx[] = {-1, 0, 1, 0}; static int dy[] = {0, -1, 0, 1}; public static void main(String[] a..

설명 시작 지점과 끝지점을 옮겨 가면서 값을 구하려고 했다. 부분합 문제처럼 생각하는 투 포인터는 아니고 두 수 간의 min 값을 개발자 능력치로 빼고 그 사이의 인원수를 곱하는 식으로 식을 짜서 최댓 값을 출력해야 하는 문제다. 그러면 생각해봤을때 서로 간의 최솟값을 기준으로 개발자 능력치를 뽑기 때문에 기준점이 되는 더 작은 수의 값을 가지는 쪽을 계속 움직여서 더 큰 수의 값을 찾게하고 이때의 서로 사이에 존재하는 개발자의 수를 가지고 계산하면 된다. 코드 package two_pointer; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; ..

설명 최단 거리로 가지는 곳을 찍으면 된다. 조건 중 벽에 막혀서 못 가는 부분만 -1으로 출력 하라는 부분을 신경쓴다면 일반적인 미로 탐색 로직 처럼 짜면 된다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static boolean [][] visited; static int map[][] ; static List[] graph; static int dx[] = {-1,0,1,0}; static int dy[] = {0,-1,0,1}; s..

설명 반대로 내가 찾아야 하는 곳에서 트리를 올라간다고 생각하고 방문 여부를 차차 검색하면 쉽게 풀 수 있는 문제였다. 처음에 트리를 구현해서 탐색하는 생각으로 접근 했다가는 뭔가 이상한듯 하여서 다른 풀이들을 참고 하였는데 굉장히 쉬운 방법이 이렇게 있었다. 코드 package tree; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class BOJ_20364 { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System...