Algorithm/Theory && Tip
N+1차원 dp
N+1차원 dp
2022.08.31N차원 배열만으로는 문제풀이에 부족한 경우가 생긴다. 이럴 때 N+1차원 배열을 사용해 dp를 적용할 수 있는데.. 아무래도 N차원 dp보다는 생각하기 쉽지 않다. 핵심은 N차원으로는 해결할 수 없으니 이차원으로 메모리를 확장하는 부분이다. 확장한 메모리를 어떻게 사용할 지는 문제마다 다르니, 역시 많이 풀어서 감을 잡는게 중요하다. https://www.acmicpc.net/problem/1495 boolean dp[i][j] = i번째 곡에서 j볼륨을 사용할 수 있는가? https://www.acmicpc.net/problem/14852 빠른 계산을 위해 이차원 배열을 도입해서 이 전까지의 값을 저장한다. https://www.acmicpc.net/problem/14722 dp[r][c][n] = r..
백트래킹 정리
백트래킹 정리
2022.08.191 ~ N 중 M개를 뽑아야 한다. 1. 중복 없이 뽑아보자. for(int i=1; i
최소 신장 트리
최소 신장 트리
2022.07.29그래프에서 일부 간선을 선택해서 만든 트리를 신장 트리 (Spanning Tree)라고 한다. 트리라서 사이클이 있으면 안되니 n개의 정점이 있으면 정점을 모두 잇는 트리의 간선은 n-1개이다. 최소 신장 트리는 신장 트리에서 간선에 가중치가 있다고 할 때 가중치의 합이 최소인 트리를 말한다. 활용 분야는 통신, 회로 등 여러 군데가 있을 수 있고 생각해보면 더 많이 있을 것 같다.. 하지만 나한테는 활용 분야보다 최소 신장 트리를 활용하는 알고리즘 문제가 나온다는거다. 가중치가 있는 그래프가 주어졌을 때 최소 신장 트리를 어떻게 구할 수 있을까? 최단 거리를 구할 때 사용하는 알고리즘인 크루스칼, 프림 알고리즘을 사용할 수 있다. https://chanhuiseok.github.io/posts/algo..
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..
격자 탐색
격자 탐색
2022.07.21시뮬레이션 유형에서 많이 등장하는 내용이다. dr = {-1, 1, 0, 0} dc = {0, 0, -1, 1} dr dc배열을 선언하고 탐색 시 사용한다. (문제에 따라 숫자를 넣는 순서는 바뀔 수 있다..) ex.1) 배열에 그림과 같이 숫자를 넣는 경우를 생각해보자. import java.io.*; import java.util.*; public class Main { static int[] dr = {1,0,-1,0}; static int[] dc = {0,-1,0,1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System..
row, column / x, y
row, column / x, y
2022.07.12이차원 배열을 설정하고 좌표평면을 탐색할 때 r,c로 탐색할지 / x,y로 탐색할지.. 사실 두 가지 모두 같은 말이긴 하다. 문제에 따라서 다른 방법으로 접근하면 좋다. 수학에서 그래프 그리듯 접근할 때는 x y를 사용하고, 행렬 느낌으로 접근할 때는 r c를 사용하면서... 이에 따라서 탐색에 유용한 dx dy dr dc배열도 새롭게 정의해 줄 수 있다. 나는 r,c를 자주 사용하긴 하지만 문제에 따라서는 x,y로 보고 풀어야 할 때도 있다.
dp팁
dp팁
2022.07.09당연한거지만.. 문제 많이 풀어보는게 정말 많이 도움 됨. 점화식 잘 안나오면 하나하나 종이에 하나하나 해보기. 수능수학에서 수열 문제 풀듯.. 일단 적은 후 규칙 찾는 방법 괜찮음. 규칙이 대충 보이면 dp배열 디자인하기.
Dynamic Programming
Dynamic Programming
2022.06.29문제의 크기를 변화시켜 작은 문제의 결과를 이용해 큰 문제의 정답을 계산하는 알고리즘이다. 우선은 완전탐색으로 풀 수 있는지 확인하고, 시간을 줄일 때 다이나믹 프로그래밍 방법을 적용하는걸 고려해 보자. 1. 작은 문제 정의하기 전체 문제를 바탕으로 좀 더 쉽게 구할 수 있는 작은 문제를 정의한다. 2. 검증 작은 문제가 전체 문제를 해결할 때 도움이 되는지 확인한다. 3. 정의한 작은 문제를 해결할 때 사용되는 초기값을 설정하자. 몇 가지 값들은 쉽게 구할 수 있다. 4. 규칙을 찾아 점화식을 작성한다. 초기값을 이용해 값들의 규칙을 찾고, 이를 식으로 표현해 모든 값들에 대해 답을 얻는다. 5. 큰 문제 해결하기 여기서 점화식을 작성하는게 까다로운데.. 유형이 그렇게 다양하지 않다. 여러 문제를 풀어..
최단 거리
최단 거리
2022.06.27BFS와 다익스트라 알고리즘을 통해 그래프에서 특정 노드까지의 최단 거리를 구할 수 있다. BFS를 통해 계산하는 경우는 한 번 이동할 때 카운트를 하나씩 늘려가면 되고.. 해당 개념을 사용해 문제도 좀 풀어봐서 익숙하다. 이 때, 간선의 가중치는 1만 가능하다. 다익스트라 알고리즘은 간선의 가중치가 0이상 일 때 사용할 수 있다. 다익스트라 알고리즘에 대해 자세히 알아보자. Dijkstra 그래프 자료구조와 시작 노드가 주어지고, 시작점에서 모든 노드까지의 최단 거리를 출력하는 알고리즘이다. dist[] : 시작점에서 특정 정점까지의 최단 거리를 담는 배열이다. (다익스트라의 결과를 담는 배열) D (v, d) : 시작점에서 v까지 가는데 d만큼이 사용된다. 1. 시작점을 S라고 하자. dist[i]에..