[백준,BOJ 1149] RGB 거리(JAVA 구현)

-내 생각 동적 프로그래밍을 풀기 전까지 백 트래킹 문제들을 풀어서 그런지 이 문제를 보자마자 백 트래킹 방식으로 풀 생각을 해버렸다.. 도저히 어떻게 풀어야 될지 모르겠어서 다른 분들의 글을 참고했다. -해법 우선 이 문제 역시 점화식을 세워주어야 한다. https://m.blog.naver.com/occidere/220785383050 [백준] 1149 - RGB거리 (2017-12-02 수정완료) 문제 링크 : https://www.acmicpc.net/problem/1149 이 문제는 아주 전형적인 DP(동적 계획법) 문제 중 ... blog.naver.com 이 분의 블로그에 잘 정리가 되어 있기 때문에 자세한 설명은 생략하겠다. import java.util.*; public class Mai..

→2019.11.26

코테/백준 온라인 저지(BOJ)

[백준,BOJ 9461] 파도반 수열(JAVA 구현)

-내 생각 이제 동적 프로그래밍 알고리즘 분류의 문제를 4문제 째 풀고 있는데, 알 수 있었던 것은 무언가 수열과 같은 규칙이 발견되면 점화식을 세우는 것이 가장 중요한 것 같다. 또한 대다수의 수열은 수가 커질수록 기하급수적으로 수가 커지기 때문에 자료타입에 신경을 많이 써야 한다는 것이다. 이번 문제의 경우에도 점화식은 자세히 보면 dp[n] = dp [n-2] + dp [n-3]이라는 점화식을 찾을 수 있다. 또 한 가지 더 찾을 수 있는데 이 부분은 다른 분들의 글을 알 수 있었다. dp [n] = dp [n-1] + dp [n-5] 역시도 성립한다는 점이다. 필자는 첫 번째 점화식을 사용하였는데 오답 처리를 받아 검색해보다가 자료 타입에 문제가 있었다는 것을 알 수 있었다. int 형이 아닌 l..

→2019.11.26

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1904] 01타일(JAVA 구현)

-내 생각 문제의 이해는 간단했다. 점화식을 찾는 것이 익숙하지 않아서 1부터 증가하면서 경우의 수를 찾아보았다. n이 1일 때 1, 2일 때 2, 3일 때 3, 4일 때 5, 5일 때 8.... 이 경우를 보면 피보나치 수열이라는 것을 알 수 있었다. 즉 점화식을 세워보면 dp [n] = dp [n-1] + dp [n-2]가 된다. 그러나 피보나치수열은 46번째 숫자부터 int의 범위를 넘어서기 때문에 dp에 저장하는 값을 미리 15746의 나머지로 저장해야 한다고 한다. -해법 import java.util.*; public class Main { static int n; static int dp[]; // 메모이제이션 public static void main(String[] args) { Scan..

→2019.11.26

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1003] 피보나치 함수(JAVA 구현)

-내 생각 처음에는 문제에서 주어진 피보나치 함수를 이용해 static 변수를 선언하여 0과 1에 도착할 때 마다 카운트를 해주어 출력방식을 사용하였는데, 오답처리를 받았고 또, 메모이제이션 기법을 사용하지 않아 시간초과 처리도 받았었다. 그래서 다른 분들의 글을 참고하였는데... 너무 어려웠다.. -해법 이 문제는 시간초과 문제를 해결하기 위해선 문제가 요구하는 알고리즘 형태는 점화식을 세워 수식의 형태로 해결하는 것이다. 그러나 점화식을 세우는 것에 익숙하지 않았기 때문에 다른 분들의 글을 참고했는데, 한 가지 점화식을 알 수 있었다. 메모리의 형태는 무엇을 사용하든 작성자 마음이지만, 이 문제에서 발견할 수 있는 규칙성은 0의 경우는 0: 1번, 1: 0번 1의 경우는 0: 0번, 1: 1번, 2의..

→2019.11.26

코테/백준 온라인 저지(BOJ)

[백준,BOJ 15651] N과 M(3) (JAVA 구현)

-내 생각 이번 문제 역시 이전의 N과 M문제들과 같은 맥락의 문제였다. 차이점은 이 문제에서는 순열 + 이미 선택한 숫자를 중복해서 선택할 수 있다는 점이다. 구현으로는 어렵지 않았다. 단순히 방문 배열을 사용하지만 않으면 됐다. 하지만 처음으로 구현 후 출력까지 확인 후 제출을 했는데 시간 초과가 나버렸다... 아직 시간 복잡도 등을 고려할 수준이 못되기 때문에 어디서 문제가 있는 것인지 찾을 수 없었는데, 검색하는 도중 자바의 경우에는 일반적인 입출력을 사용할 시 시간 초과가 날 수 있다는 글을 보고 바로 수정한 후 제출했더니 정답처리를 받을 수 있었다. -해법 자바에서 일반적으로 우리가 사용하는 입출력 라이브러리는 Scanner를 이용한 입력방법과 System.out.print();를 이용한 출력..

→2019.11.17

코테/백준 온라인 저지(BOJ)

[백준,BOJ 15649] N과 M(1) (JAVA 구현)

-내 생각 우선 알고리즘 공부를 시작하고 순열 문제를 처음 접했다. 여러 글을 읽어보던 중 순열과 조합의 차이를 알 수 있었고, 이번 문제는 그 순열에 관한 문제였다. DFS와 백트래킹을 이용하라고 하는데 아직까지는 개념이 잡히질 않는다. DFS의 경우에는 한 가지를 고정한 후 가능한 경우의 수를 찾고 또 그 경우의 수에서 한 가지를 고정하고 하위 경우의 수를 찾고... 갖은 개념으로 알고 있으며 백트래킹은 이러한 과정에서 어떠한 조건에 걸리지 못하면, 다 배제를 해버리는 탐색으로 완전 탐색과는 다른 개념으로 알고 있다. 문제의 이해는 쉬웠지만 어떻게 구현해야 할지 감이 잡히질 않아서 다른 분들의 블로그 글들을 많이 참고했다. -해법 dfs메서드에 반복 횟수를 인자로 전달한다. 0번부터 전달하는 이유는 ..

→2019.11.16

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2606] 바이러스(JAVA 구현,추가풀이)

-내 생각 단계별로 풀어보기 DFS, BFS로 분류되어 있는 백준 2606 바이러스 문제이다. 이전 단계에 백트래킹 알고리즘 단계가 있었는데 일반적으로 백트래킹의 경우 DFS를 기반으로 푼다는 글을 보고 우선 DFS와 BFS를 먼저 공부하기로 마음먹고 만난 문제다.(물론 이전에 DFS와 BFS 문제가 있었지만 단순한 개념 수준의 문제) 문제를 이해하는데 어려움은 없었고, 해법으로 처음 생각한 것은 단순히 인접 행렬로 그래프를 구성 후, 완전 탐색 방식인 DFS 또는 BFS를 사용하면 될 것 같았다. 그렇다면 DFS와 BFS 중 무엇을 사용해야 할지 선택해야 했는데, 문제 상으로는 바이러스에 감염된 컴퓨터와 인접한 컴퓨터부터 차례대로 감염된다는 언급이 있었기 때문에 한 노드의 인접한 노드를 모두 방문하는 ..

→2019.11.12

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1260] DFS와 BFS(JAVA 구현)

-내 생각 저번 게시글에서 공부했던 그래프의 순회 기법의 두 가지인 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)이다. 그래프의 구현은 인접 행렬을 이용하여 간단하게 구현할 수 있었고, DFS와 BFS의 구현의 경우에 DFS는 재귀 호출 형태로 구현이 쉬웠지만, BFS는 재귀나 스택이 아닌 큐만을 이용한다는 점을 간과해버리고 BFS도 재귀로 구현할 뻔했다.. 저번의 코드를 참고해서 작성할 수 있었다. -해법 코드를 보면서 이해해보자. import java.util.*; public class Main { static int node[][]; // 인접행렬 배열 static int check[]; // 노드의 방문여부 표시 배열 static Queue queue = new LinkedList(); /..

→2019.11.12

코테/백준 온라인 저지(BOJ)

[백준,BOJ 10814] 나이순 정렬(JAVA 구현,재풀이)

-내 생각 정렬로 분류되어 있는 문제로 다른 정렬 문제들과 마찬가지로 풀면 되는데 처음에는 2차원 배열을 사용할 때 나이, 이름값뿐만 아니라 별도의 가입 순 값을 저장해서 나이가 같으면 해당 값을 기준으로 정렬을 수행한 결과를 제출했는데, 계속 오답처리가 나서 다른 분들의 풀이를 살짝 봤더니 문제점을 알았다.... -해법 우선 별도의 가입 순 데이터를 저장할 필요가 없는 게, 애초에 입력을 가입 순으로 한다고 명시되어 있기 때문에 결국 모든 데이터가 입력된 2차원 배열의 데이터들은 가입 순으로 정렬이 되어있는 것이나 마찬가지다. 그러므로 나이순으로만 정렬을 해준다면, 나이가 같을 경우 별도의 조작이 필요 없는 것이었다. import java.util.*; public class Main { public ..

→2019.11.12

코테/백준 온라인 저지(BOJ)

[백준,BOJ 11651] 좌표 정렬하기 2(JAVA 구현)

-내 생각 이번 문제는 11650인 좌표 정렬하기 문제에서 정렬 기준만을 변경한 것이므로 Comparator인터페이스 오버라이딩 부분만 수정해주면 간단하게 해결할 수 있었다. -해법 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n= sc.nextInt(); int arr[][]=new int[n][2]; for(int i=0;i

→2019.11.12

티스토리툴바