알고리즘 (18) 썸네일형 리스트형 [DP/ acmicpc] 이친수 출처 : https://www.acmicpc.net/problem/2193 규칙 : 1. 처음시작은 무조건 12. 1 다음에 1이 올 수 없음2. 0 다음엔 0, 1 둘다 올 수 있음 점화식 :D[n] = D[n][0] + D[i, j][1] D[n][0] = D[n-1][0] + D[n-1][1] // n자리일때 끝이 0으로 끝날 수 있는 경우는 n-1자리일때 0, 1로 끝나는 경우의 수의 합D[n][1] = D[n-1][0] // n자리일때 끝이 1로 끝날 수 있는 경우는 n-1자리일때 1로 끝나는 경우의 수 정리 -> D[n] = D[n-1][0] * 2 + D[n-1][1] 알고리즘 문제 사이트 모음 1. sphere online judge : http://www.spoj.com/ [Algorithm / Sort] 기수정렬(Radix Sort) O(dn) 속도의 기수정렬(Radix Sort) 알고리즘이다. 아래 사진과 같이 특정한 시작점(오른쪽 또는 왼쪽)을 기준으로 점진적으로 정렬하는 것이 기수정렬이라고 한다. LSD(least significant digit) : 오른쪽을 기준 정렬MSD(most significant digit) : 왼쪽 기준 정렬 기수 정렬시 주의할 점은 각 단계는 전 단계의 정렬된 배열을 기준으로 해야한다는 것이다. [분할정복 / 정올 ] 1335 : 색종이 만들기 [원리]분할정복은 문제를 나눌 수 없을 때까지 나누어 병합하며 문제를 해결하는 방식 [분석]이 문제를 풀수 있는 방법은 아래와 같이 2가지다. -방법 1현재 범위의 종이가 색깔을 본다. 1) white인가 -> whiteCount ++2) black인가 -> blackCount ++3) 둘다 아닌가 -> 분할해서 찾아본다. 사실 분할 정복알고리즘으로 대표적인 알고리즘은 Merge Sort인데, 이 경우 정말 최소단위까지 내려가 병합하여 정렬하지만, 내 소스의 경우 Merge Sort라고 하면 이미 정렬되어있는지 먼저 검사하고 분할하여 탐색한다고 볼 수 있다. -방법 21) 일단 4분할을 한다. 2) 4분할 하여 반환된 색깔이 모두 같은 색인가?2-True) 색을 반환한다.2-False) 반환된 색깔들은 .. [ BFS / 정올 ] 1082 : 화염에서탈출 문제 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=362&sca=3040 뭐야 이 문제는!!! BFS문제로 주로 좌표관련 문제가 많이 나옵니다. 그러한 문제들을 풀기위해 특정한 알고리즘 패턴을 암기해서 푸는 경우가 대부분인데 이 문제의 경우 너비탐색으로 고려해야하는 요소가 2개가 존재합니다. [ 이동가능한 요소 ]1. 지섭이 ( 용사? ) 2. 불 [ 제약 조건 ]1. 바위에는 불이나 지섭이가 이동할 수 없습니다.2. 요새에는 불에 타지 않습니다. 위 조건들 중에서 이동가능한 요소는 다른 체스문제나 최단코스트 문제처럼 한 개가 아닌 2개가됩니다. 또한 같은 맵(차원)에서 이동하므로 서로의 위치가 겹치는 경우 또한 발생하죠. [ 예를 들어서 ].. [acmicpc/1004] 어린왕자 문제 12345678910111213141516171819202122232425262728293031323334public class Main { static class StarNode { public StarNode(int x, int y, int r) { this.x = x; this.y = y; this.r = r; } int value = 0, x = 0, y = 0, r = 0; } static Scanner sc = new Scanner(System.in); static StarNode s = null; static StarNode e = null; static StarNode[] stArr = null; static int count = 0, stNum = 0; public static void .. ㅇㅇ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 import java.util.LinkedList;import java.util.Scanner; public class Main { class Node { public Node (int numNode, Node node ){ this.numNode = numNode; this.before = node; } int numNode; Node before; } public static void main(String[] args) { Main n = new .. [DFS] 1027 : 좋은수열 12345678910111213141516171819202122232425262728293031323334353637383940414243 import java.util.Scanner;public class GoodSequence { public static void main(String[] args) { GoodSequence n = new GoodSequence(); n.goodSequence(0); n.display(); } Scanner sc = new Scanner(System.in); int deepMax = sc.nextInt(); StringBuffer sequence = new StringBuffer(); boolean isFind = false; public void goodSequen.. 이전 1 2 3 다음
