알고리즘 문제147 [알고리즘 문제] 백준11726 - 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 자주 접하는 dp문제이다. dp[n]는 2 x n 크기의 직사각형을 채우는데 필요한 타일의수가 들어간다. 대부분 피보나치수열과 같은 방식으로 문제를 푸는데, 왜 이렇게 푸는지 생각해 보았다(사실 같은 문제를 몇번 푼 것 같은데 그냥 공식으로만 풀었고 왜? 그렇게 되는지는 생각해보지 않았다...) 먼저 순열에 대해 생각해보자. 뜬금없지만 문제를 푸는데 도움이 된다. 일단 한번 짚어보고 가자. [1,2,3,4]으로 만들 .. 2020. 3. 31. [알고리즘 문제] 백준1463 - 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 비슷한 문제를 코딩테스트에서 본 적 있는데 당시에 못 풀었는데, dp로 접근하면 될 것 같습니다. bottm-up 방식으로 풀었고, dp[n]에는 n을 1로 만드는 최소 횟수가 들어가 있습니다. 해결하는 방법은 전형적인 dp방법으로 이전에 계산했던 최소값을 현재 n을 구하는데 사용합니다. dp[n]에는 n숫자를 1로 만드는데 최소 횟수가 들어가 있다고 했습니다. 먼저 처음 dp[1]은 0로 초기화 해줍니다. 어떤 연산도 할 필요 없기 때문이죠. 그렇다면 이제 2부터 1~3번째 연산을 모두 해봅니다. 1~3연산을.. 2020. 3. 30. [알고리즘 문제] 백준1759 - 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 보통 재귀에서 사전적 순서라는 문제가 나오면 for문에서 시작하는 index값을 매개변수로 넘겨주어 이전값이 등장하지 못하도록 하는 방법을 사용합니다. 단, 먼저 입력받은 알파벳이 정렬되어 있어야 합니다. 먼저 temp[]배열에 입력받은 알파벳을 모두 넣고 정렬해 줍니다. 그리고 재귀를 돌리는데 인자로 index와 depth를 사용합니다. index는 사전적 순서를 만족하기 위해 for문의 시작값을 .. 2020. 3. 28. [알고리즘 문제] 백준1525 - 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 먼저 퍼즐을 움직인 최소 횟수를 구하는 문제이기 때문에 bfs를 사용했습니다. 그리고 현재 퍼즐의 상태를 관리를 어떻게 할까 생각을 했는데, 그냥 2차원 자료구조로 저장하여 que에 넣어 bfs를 하면 메모리 초과가 날 것 같았습니다. 메모리 제한이 32 MB 이더라구요. 그래서 퍼즐을 문자열로 관리하였습니다 3x3이기 때문에 길이가 9인 문자열이 됩니다. 그리고 문자열에서 '0'의 index값을 찾아서 좌우상하(-1,1,-3,3)위치로 움직일 수 있으면 해당 문자열에서 s.. 2020. 3. 23. 이전 1 ··· 10 11 12 13 14 15 16 ··· 37 다음
