Algorithm
그래프
그래프
2022.05.12자료구조에서 그래프는 정점 + 간선 방향의 유무 / 가중치의 유무에 따라 그래프의 종류가 나뉜다. 차수 (deg) : 정점에 연결된 간선의 수 / 모든 정점들의 차수 합 = 간선 수 * 2 (시간복잡도 계산에 사용됨) 그래프 문제를 풀기 위해 컴퓨터에게 그래프 자료구조를 저장하는 방법을 알아야 한다. 1. 인접 행렬 그래프가 연결된 상태를 이차원 배열으로 표현한다. 가중치가 있는 경우는 1이 아니고 가중치로 표현 할 수 있다. 구현하기는 쉽지만, 메모리를 효과적으로 사용하기 힘들다. 2. 인접 리스트 List자료구조를 활용해 연결된 요소들만 저장한다. 주어진 조건에 따라 효과적인 방법으로 그래프를 구현하자. 그래프 문제에서 가장 중요한 요소는 이 문제가 그래프 문제인걸 아는 것이다. 문제를 보고 그래프 ..
[백준] 1394 암호 - Java
[백준] 1394 암호 - Java
2022.05.09암호에 쓰이는 문자들의 후보의 길이와 암호의 길이를 잘 살펴보자. 후보의 길이에 따라 시도하는 횟수가 점점 증가한다. abcd가 후보라고 생각해보자. 길이가 1인 암호 : a b c d (4) 길이가 2인 암호 : aa ab ac ad / ba bb bc bd / ca cb cc cd / da db dc dd (4 * 4) ... 이런 식으로 후보문자열의 길이만큼 계속 곱해지는 형태를 보인다. 그렇다면, 주어진 암호의 길이를 통해 답을 어느정도 유추할 수 있을 것 같다. 그런데, 암호의 처음부터 계산해서 세기 시작하면 해당 자릿수 전까지의 시도 횟수는 쉽게 구할 수 있지만, 그 다음 처리가 힘들어진다. 암호의 뒤에서부터 역순으로 시도 횟수를 구해보자. 이를 위해 문자열 후보가 입력되는 순서를 알아야한다...
[백준] 1644 소수의 연속합 - Java
[백준] 1644 소수의 연속합 - Java
2022.05.09에라토스테네스의 체 방식으로 입력받은 N 이하의 소수 배열을 만든 후 항상 하던대로 투포인터 방법을 활용해 풀 수 있는 문제이다. R을 조작할때는 조건식에 합이 N이 넘어가는 조건을 포함시켜 작성하는게 좀 더 깔끔해 보인다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); boolean[] prime_chk = new boolean[N + 1..
[백준] 15565 귀여운 라이언 - Java
[백준] 15565 귀여운 라이언 - Java
2022.05.08투 포인터를 사용해서 풀 수 있는 문제이다. 정형화 된 방법을 익히고 언제 어디서든 사용할 수 있도록 하자. 1. 배열 인덱스의 시작은 1부터 시작하도록 설정하자. 2. L과 R을 조작할 때 L은 1부터, R은 0부터 시작하고 while로 R을 조작할 때 R을 1증가시키면서 시작하자. 3. 항상 문제를 잘 읽자. 배열 인덱스의 시작을 1부터 시작하도록 설정하는거는 단순히 편의를 위해서이다. 이분 탐색을 진행할 때는 mid값을 제대로 구하기 위해 1부터 설정했었는데.. 이게 손에 익어서 계속 쓰게 됐다. 위의 형식은 문제 조건에 따라서 얼마든지 바뀔 수 있지만, 그래도 풀이의 틀을 잡아놓으면 접근하기 편한 것 같다. import java.util.*; import java.io.*; public class..
[백준] 2559 수열- Java
[백준] 2559 수열- Java
2022.05.08범위 나누고 계산해 최댓값을 계속 갱신해주면 된다. 입력이 음수로 들어올 수 있으니 ans의 초기값을 Integer.minvalue로 설정해줬다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(..
[백준] 2003 수들의 합2- Java
[백준] 2003 수들의 합2- Java
2022.05.08연속적인 합의 결과를 구하는 문제이니.. 딱 투 포인터로 풀면 되겠다고 생각된다. 처음 작성한 코드에서는 수열의 첫 번째 항이 구하려는 수와 같을 때를 잡아내지 못해서 헤멨다. 맞게 푼 것 같은데 틀리면 놓치기 쉬운 부분을 체크해보고, 극단적인 상황을 가정해서 테스트케이스를 유추해보자. import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.rea..
[백준] 16472 고냥이 - Java
[백준] 16472 고냥이 - Java
2022.05.08지난번에 풀었던 List of Unique Numbers문제와 유사한 방식으로 풀 수 있다. R을 가능한 만큼 보내고, R이 더 이상 갈 수 없으면 L을 움직이면서 계속해서 값을 누적시키는 방식으로 풀이하자. import java.util.*; import java.io.*; public class Main{ static int[] alpha; static int N; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); String str = br.read..
[백준] 1253 좋다 - Java
[백준] 1253 좋다 - Java
2022.05.08지난번에 풀었던 두 용액의 투 포인터 풀이와 유사한 방식으로 풀 수 있다. 배열을 정렬한 후 최소값과 최대값의 결과에 따라 포인터를 이동시키며 풀 수 있는데, 여기서 찾으려고 하는 요소는 포함되면 안된다. 이 부분만 따로 처리해 주면 쉽게 풀 수 있다. import java.util.*; import java.io.*; public class Main{ static int[] arr; static int N; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()..
[백준] 13144 List of Unique Numbers - Java
[백준] 13144 List of Unique Numbers - Java
2022.05.08L과 R을 설정하고 빠르게 중복되는 수가 있는지 확인하자. 중복 여부를 빠르게 확인하기 위해 count배열을 사용했다. import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] arr = new int[N+1]; StringTokenizer st = new StringTokenizer(br.readLine()); for(int i=1; i
[백준] 1431 시리얼 번호 - Java
[백준] 1431 시리얼 번호 - Java
2022.05.06클래스 만들고 조건대로 CompareTo 메서드를 오버라이딩 해 주면 된다. 개인적으로 Comparable을 구현하는게 Comparator구현하는거보다 깔끔해 보이는 것 같다.. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); Serial[] arr = new Serial[N]; for(int i=0; i
[백준] 2866 문자열 잘라내기 - Java
[백준] 2866 문자열 잘라내기 - Java
2022.05.06인덱스 0부터 시작해서 문자열을 잘라내면서 접근하면 시간 초과가 발생한다. 빠르게 탐색할 수 있는 방법을 생각해야 한다. 임의의 k번째 인덱스부터 탐색을 시작한다고 생각해보자. k번째 인덱스에서 중복이 발생하면, 그 이후 인덱스에 대해서도 당연히 중복이 발생한다. 즉, 중복이 발생한 이후에는 쭉 중복이 발생한다. 이 부분에 집중하면, 이분 탐색으로 해결할 수 있다는 결론이 나온다. import java.util.*; import java.io.*; public class Main { static char[][] arr; static int R; static int C; static HashMap hm = new HashMap(); public static void main(String[] args) th..
[백준] 1637 날카로운 눈 - Java
[백준] 1637 날카로운 눈 - Java
2022.05.06입력으로 들어온 수 중 홀수 개 존재하는 수는 하나 뿐이다. 모든 경우를 싹다 찾아보며 문제를 풀려고 하면 당연히 시간 초과가 날 테니까.. 다른 방법을 생각해보자. 특정 정수 하나만 홀수 개 존재하고, 나머지 수는 모두 짝수개를 가진다.. 홀수 개 존재하는 정수보다 큰 정수에 대해서 개수의 합을 구하면 홀수 개가 나오고, 홀수 개 존재하는 정수보다 작은 정수에 대해서 개수의 합을 구하면 짝수 개가 나온다. 이 부분에 집중해서 매개 변수 탐색을 수행하자. import java.util.*; import java.io.*; public class Main { static int N; static int[][] input; //static long ans_num; static int max = Integer..