Algorithm
[백준] 2468 안전 영역 - Java
[백준] 2468 안전 영역 - Java
2022.07.28안전 영역의 정의를 제대로 알고 풀자. 안전 영역은 덩어리의 수이다. 안전 영역은 위와 같이 정의된다. bfs함수 만들고 인자를 하나씩 늘려가면서 풀자. import java.io.*; import java.util.*; public class Main { static int N; static int[][] map; static int max; static int highest; static int[] dr = {-1,1,0,0}; static int[] dc = {0,0,-1,1}; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(Syst..
[백준] 25332 수들의 합 8 - Java
[백준] 25332 수들의 합 8 - Java
2022.07.28두 수열의 길이가 왜 같을까? 이 부분을 잘 생각해보자.. 길이가 같은 두 수열을 입력받고, 두 수열의 값을 뺀 값을 가지는 새로운 수열을 정의하자. 새로 만들어진 수열에 대해 누적 합 배열을 구하고, 이 배열의 구간합이 0인 부분수열의 수를 구하자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int N = Integer.parseInt(b..
[백준] 2015 수들의 합 4 - Java
[백준] 2015 수들의 합 4 - Java
2022.07.28이중 for문을 돌면 당연히 시간 초과가 난다 -_- 먼저 입력받은 수들에 대해 누적 합 배열을 만들고 시작한다. 해시 맵은 누적 합 배열을 돌면서 해당 값이 나온 횟수를 저장하고, 현재 값 - 목표 값을 확인해 답을 갱신할 때 사용한다. 일단 누적 합 배열을 만들어놓으면 sum_arr[6] - sum_arr[3] == arr[4] + arr[5] + arr[6] 이렇게 사용할 수 있으니.. 누적 합 배열을 돌면서 배열의 값이 찾으려는 값과 같으면 ans 1 증가. 나머지는 위에서 설명한 대로. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ B..
[백준] 25395 커넥티드 카 실험 - Java
[백준] 25395 커넥티드 카 실험 - Java
2022.07.28bfs돌려서 푸는데.. 그냥 풀면 시간 초과가 발생한다. 커넥티드 카 들의 위치를 기준으로 정렬해 처음으로 도달할 수 없는 커넥티드 카를 만나면 break;로 탈출해 빠르게 탐색하도록 했다. 나머지 내용은 그냥 bfs import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.r..
[백준] 1766 문제집 - Java
[백준] 1766 문제집 - Java
2022.07.28위상정렬 연습하기 좋은 문제.. 가능하면 쉬운 문제부터 푸는게 좋다고 하니 우선순위 큐를 사용해 낮은거부터 뽑아줬다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); in..
[백준] 9251 LCS - Java
[백준] 9251 LCS - Java
2022.07.27https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Comm..
[백준] 12865 평범한 배낭 - Java
[백준] 12865 평범한 배낭 - Java
2022.07.27dp[N+1][K+1] 행을 증가시키면서 값을 누적시켜 최적 무게를 계산한다. dp의 열 값은 해당 무게만큼 물건을 넣었을 때 가치의 최댓값이다. import java.io.*; import java.util.*; 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(s..
[백준] 2193 이친수 - Java
[백준] 2193 이친수 - Java
2022.07.26간단한 dp문제다. 이차원 dp배열을 설정해서 풀이한다. [N+1][2] : N은 자릿수 / 2는 0으로 끝나는 수와 1로 끝나는 수. 다음 자릿수의 이친수를 구할 때는 이전 자릿수의 이친수가 0으로 끝난 경우 + 1로 끝난 경우 + 0으로 끝난 경우를 계산해주면 된다.. import java.io.*; import java.util.*; 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()); long[][] dp =..
dp
dp
2022.07.25고등학교 수학1 단원에서 배운 수학적 귀납법 개념을 프로그래밍에 적용시킨게 dynamic programming이다. 초기값(base)을 설정해주고, 점화식을 구해 임의의 N에 대해 모든 값을 구할 수 있도록 설계한다. 수학적 직관이 있으면 점화식을 생각할 때 매우 유리하다. 다소 발상적인 부분도 있어 알고리즘을 처음 접하는 경우라면 연습이 많이 필요하다. 관련 문제를 많이 많이 풀어보자. 반복문과 재귀 모두 사용할 수 있다. dp에서 중요한건 설정한 값에 대한 이해와 점화식... 여기서 반복문과 재귀는 구현하기 위한 도구로만 사용된다. dp에서는 중복되는 계산을 줄이는 기법을 사용하는데, 재귀함수를 통해 dp를 구현할 때는 Memoization을 사용하고, 반복문을 통해 dp를 구현할 때는 Tabulat..
dfs와 bfs
dfs와 bfs
2022.07.25dfs는 재귀함수를 이용해서 구현한다. 관계식이 명확하게 보이기 때문인데.. 위와 같은 그래프를 dfs로 탐색한다고 하면, 노드 A에서 갈 수 있는 노드 = A + B에서가는거 + C에서가는거 이렇게 관계식이 나온다. 그래프를 탐색하는 함수를 하나 만들어놓고 ~에서 갈 수 있는 노드를 탐색할 때 그 함수를 계속해서 호출하면 되기에 재귀함수를 통해 직관적으로 구현할 수 있다. 재귀함수를 통해 깊게 깊게 파고들어서 depth first search라고 불린다. 탐색을 진행할 때는 탐색한 곳을 다시 탐색하는 경우를 피하기 위해 visit배열을 그래프와 함께 사용한다. import java.io.*; import java.util.*; public class Main { static int N, M; stati..
백트래킹
백트래킹
2022.07.22처음 접했을 때 이해하기 쉽지 않은 알고리즘이다. 재귀함수를 활용해 구현하는 경우가 많고, 함수 종료 조건 / 재귀 호출 부분 두 가지를 잘 고려해 함수를 디자인하자. 확률과통계 과목에서 수열을 나열하거나, 논리회로나 계산이론 과목에서 accept할 수 있는 언어를 찾을 때 해당하는 수 또는 단어들을 나열할 때 수형도를 사용하는데, 여기서 사용하는 수형도가 백트래킹과 깊게 연관되어있다. import java.io.*; import java.util.*; public class Main { static int N, K; static ArrayList list = new ArrayList(); public static void main(String[] args) throws Exception { Buffer..
ArrayList에서 원소 제거
ArrayList에서 원소 제거
2022.07.21ArrayList 에서 원소 제거 시 제거된 인덱스를 채우기 위해 제거된 원소 뒤에 위치한 원소들이 한 칸 씩 당겨진다. 이 부분을 잘 생각해 원소 제거 시 인덱스를 적절히 조작해야 한다. 제거 후 반복문의 변수를 1 줄인다거나.. 제거하는 인덱스를 고정시켜놓는다거나.. ArrayList에서 원소를 제거할 때 원소의 인덱스를 기준으로 제거 할 수도 있고, 원소의 내용을 기준으로 제거 할 수 있다. 인덱스로 제거하는건 쉬우니 넘어가고, 원소의 내용을 기준으로 제거 할 때는 보통 리스트에 제네릭스 타입으로 객체 타입이 들어가 있을 경우일텐데, 같은지 판단하는 기준은 객체에 정의된 equals메서드이다. class Marble{ int r, c; Marble(int r, int c){ this.r = r; t..