알고리즘 검색 결과

해당 글 13건

동적계획법의 기초

동적 계획법이 왜 쓰이는지에 대해 궁금한 사람들을 위해 작성합니다. 동적 계획법이란, 이미 계산돼있는 값을 추후에 다시 계산하지 않고 가져다쓰기 위함입니다. 답을 재활용한다고 생각하시면 편합니다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. 팩토리얼을 이용한 동적 계획법은, 둘다 시간 복잡도가 log(N) 이기 때문에 적합하지 않습니다. 조금 더 자세한 예를 위해 피보나치 수열 문제를 가져왔습니다. https://www.acmicpc.net/problem/2747 백준 2747번 피보나치 수 위와 같은 방식은 설명을 위한 재귀지, 일반적으로 사용하는 방식은 아닙니다. 시간 단위는 millisecond 입니..
알고리즘/동적계획법 2019. 8. 31. 12:58

[백준] 2231번 분해합

이번에도 생각만 잘하면 쉽게 풀 수 있는 문제입니다. 만약 숫자 256은 = 245 + 2 + 4 + 5 입니다. 그럼 생성자는 245겠지요.M이라는 숫자가 생성자이고, 셋째자리라면 M + M첫째자리 + M둘째자리 + M셋째자리 입니다.근데 각 자리수마다 올 수 있는 최댓값은 9입니다.그럼 첫번째부터 돌 필요 없이, 주어진 숫자의 자릿수 만큼 9를 빼주면 됩니다.그럼 그 숫자가 적어도 최소 시작 점이겠죠?(N을 생성하려면 M이라는 숫자 + ? 인데, ?는 최대 9밖에 올 수 없으니까요)256의 최소 시작점은 256 - 9 * 3 입니다. 사실 각 자릿수마다 토큰화시키는게 더 오래 걸린 문제;;
알고리즘/완전탐색 2019. 1. 30. 04:04

[백준] 2309번 일곱 난쟁이

브루노 포스 (완전탐색) 문제이다. 사실 브루노 포스가 뭔지 몰라서 구글에 검색해봄 ㅎ방법은 정답은 꼭 '7명' 이여야 한다는걸 노렸는데, i와 j번째 난쟁이를 제외한 나머지 난쟁이들의 키를 합친게 100 이라면그게 바로 정답이 되는 것이다. 이번문제는 간단했던것 같다. 배제할것만 배제하고 단순하게 생각하면 되겠지... 이런 문제처럼만이길..
알고리즘/완전탐색 2019. 1. 30. 01:41

[백준] 1005번 ACM Craft

분명 동적 계획법 기초에 있는 문제인데, 알고리즘 분류는 위상 정렬로 되어있다.순간 보고 멘붕해서 위상정렬에 대해서 처음부터 공부했다..물론 동적 계획법으로도 풀 수 있으나, 그 양이 방대해서 위상정렬로 푸는게 도움이 될 것 같다. 위상정렬에 대한 문제도 많으니 말이다.위상정렬에 대해 따로 정보를 주자면, 이어져 있는 노드들을 순서에 따라 정렬하는 것이다.자세한 내용은 나보단 더 설명이 잘 돼있는 블로그가 있으니 그 블로그 링크를 올리겠다. http://kks227.blog.me/220620723528 어우 이분 설명 잘하신다 진짜아무튼 위상정렬을 처음 해보는 나로써는 변수를 적어놓고 아 이걸 왜 적어줬지 어디다 쓰는거였지? 하고 계속 반복하게됐다.. 결국 풀긴 했지만 말이다... 일단 위상정렬이 됐다는..
알고리즘/정렬 2019. 1. 30. 00:20

[백준] 2156번 포도주 시식

이 문제도 진짜 어려웠다. 계단 오르기 처럼 하면 될 줄알았는데, 예상외로 변수가 많았다. 일단 잔이 1개 있다면, 그 1잔이 바로 최댓값이다. dp[1] = arr[1]잔이 2개있다면 2개를 마시는게 최댓값이다. dp[2] = arr[1] + arr[2]잔이 3개있다면? 여기서부터 문제인데 바로 연속으로 3잔은 마실 수 없는것이다.이제 점화식을 풀어보자 1) N번째로 마시는 포도주를 안마시겠다면?N번째 포도주가 양이 적어 건너뛰는게 나을 수도있다.이럴땐 dp[N] = dp[N-1] (N번째를 마시지 않았으므로) 2) N번째로 마시는 포도주가 1번 연속이라면?1번 연속이다라는건 앞의 포도주를 건너뛰고 처음으로 마셨다는 뜻이다그럼 n-1번째는 절대 마시면 안된다. 대신 n-2번째는 마시든 말든 상관없다.이..
알고리즘/동적계획법 2019. 1. 29. 01:33

[백준] 1912번 연속합

사실 이걸 올려야하나 말아야하나 고민 많이했는데.. 구하는 방법이라도 알 수 있으니 그냥 올렸다.dp보다는 변수2개로 둬서 구했는데.. dp로 구해도 되긴 된다.. 원리는now와 max를 두고arr[2]번째부터 now에 계속 더해주는 것이다. (2번째부터 도는 이유는 첫번째는 무조건 자기 자신이 최대값이기 때문)그리고 더해준 now 와 max를 비교해 둘 중 더 큰값을 MAX 값으로 두면 된다.그리고 now가 더해져 가면서 만약 0보다 작아진다면? 그땐 now를 0으로 (초기화) 시켜주면 된다. 왜냐면 now가 -가 된다면 최대값이 될 수 없다.예외가 있다면 음수들만 arr에 들어온다는 것인데그런 경우엔 arr 중에서 가장 작은 값이 최대 값이다.예를 들어 arr에 5개의 숫자가 들어있고 -1,-2,-3..
알고리즘/동적계획법 2019. 1. 26. 03:58

[백준] 1932번 정수 삼각형

역시나 점화식을 짜놓고, 오류 고친다고 오히려 시간을 더 사용한 문제다...일단 점화식을 짜보자 경로는 무조껀 왼쪽 대각선 혹은 오른쪽 대각선이다. 그렇담 7에서 나가는 3 과 8을 경로로 잡는다고 하면, 7->3(10), 7->8(15) 이다.가운데의 1에 갈 수 있는 방법은 7->3->1 또는 7->8->1 그러나 7->8->1 이 더 크기 때문에 7->3->1 은 무시한다.또한 또하나의 법칙이 있는데, 좌측 제일 하단의 4와 우측 제일 하단의 5가 보이는가?저 길까지 가는 방법은 무조건 첫번째 배열에서 좌측 대각선으로 가거나, 우측 대각선으로 가는 방법밖엔 없다.예) 7에서부터 시작해서 좌측 하단의 4까지 거리를 만드는 방법은7->3->8->2->4 순으로 가는 방법밖엔 없다.우측 또한 마찬가지다...
알고리즘/동적계획법 2019. 1. 26. 01:38

[백준] 1149번 RGB거리

이것도 하나하나 탐색해가며 찾으면 될 것같다. 저번 타일링 문제 처럼 말이다.일단 점화식부터 세워야 하는데 기본적으로 모든 값중 최솟값을 찾는 점화식부터 세워보자N이 0일땐, 아무것도 채워넣을 수 없다. 그러므로 dp[0]은 0,일단 예제에서 N 이 1일땐, 0번째는 26 1번째는 40 2번째는 83이다. 이중 최솟값은 26이니 dp[1]는 26,N이 2일땐 0번째는 49 1번째는 60 2번째는 57이다. 이중 최솟값은 49이니 dp[2]는 dp[1]까지 합친 값인 75그럼 점화식은 결국 dp[i] = dp[i-1] + arr[i]; 이다. (arr[i] 는 현재 N값중 가장 작은 값이다.) 이제 제약조건인 이웃이 이미 칠한 색깔은 칠 할 수 없다 를 풀어보자일단 arr와 dp를 모두 2차원 배열로 설정..
알고리즘/동적계획법 2019. 1. 25. 01:26