Algorithms/Baekjoon Algorithms (14) 썸네일형 리스트형 알고리즘 설계 - 동적계획법 (Dynamic Programming) 제목은 거창하게 '설계법'이라 했습니다만~ 자세한 내용은 책을 읽어보시길 바래요! 문제를 동적계획해서 푼다는게 무슨 소리일까요? 예를 들어서 A라는 문제를 해결하는데 그 과정을 B, C, D, E, F, G 사건으로 세분화해서 표현할 수 있다고 가정하고 각 관계가 다음 그래프와 같다고 할게요. 그럼 이 문제를 컴퓨터로 코딩하기 위해 반복문을 쓸지 재귀를 쓸지 결정할 수 있습니다. 반복문을 수행하려니 for문에 for문을 계속 넣어야할것이고...? for문 밖으로 연산이 벗어나면 한번 사용하고 말 변수를 아주 많이 선언해야합니다. 비효율적이죠! 재귀를 수행하려니 E를 수행하기위해 C와 D를 수행할것이고 F를 수행하기위해 마찬가지로 C와 D를 수행해야하고 G를 수행하기위해 E와 F를 한번씩 더 수행해야합니다.. 백준 알고리즘 2655 - 가장 높은 탑 쌓기 https://www.acmicpc.net/problem/2655 2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제는 백준 알고리즘 사이트에서 확인하세요~ 오늘 다룰 문제는 조금 복잡합니다. 문제가 원하는 답은 '가장 높게 쌓은 탑'에 사용된 벽돌의 개수와 사용된 벽돌의 번호를 나열하는 것입니다! 복잡한 문제인 만큼 조건이 까다롭네요. 그 중에서 .. 백준 알고리즘 2098 - 외판원 순회 (The Traveling Salesperson Problem) https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 문제는 백준 알고리즘 사이트에서 확인하세요~ 이번 시간에는 알고리즘의 정석이라고 불릴법한 TSP 문제를 가져왔습니다. TSP가 유명한 이유는 아직도 풀리지 않기 때문이에요 ㅜㅜ 문제가 원하는 답은 간단합니다. "모든 정점을 한번씩만 거쳐 원래의 정점으로 돌아오는 최단경로(해밀턴 회로.. 백준 알고리즘 2156 문제 - 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 문제는 백준 알고리즘 사이트에 있습니다~ 먼저 분석부터 들어가봅시다! ㅎㅎ 조건 1. 잔을 선택하면 선택한 포도주는 모두 마신다. 조.. 백준 알고리즘 2193 문제 - 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 문제는 백준 알고리즘 사이트를 참조하세요 먼저 분석과 설계를 하고 시작할게요 Pinary Number 1 - 0으로 시작하지 않는 수 2 .. 알고리즘 글을 쓰려고 합니다. 티스토리 블로그가 제일 깔끔하네요 알고리즘 카테고리에는 풀었던 문제 및 사용한 알고리즘을 소개하는 형식으로 포스팅을 하려 합니다 모름지기 백문이 불여일타 아니겠습니까 ㅜㅜ 그럼 다음에 만나요. 이전 1 2 다음
