코딩 공부소

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 백트래킹을 이용하는 문제로 실버 3문제입니다 해결책 문제는 간단합니다. 만약 n이 3이고 m이 2가 됬다면 2자리 수열로 모든 가능한 수를 만드는것입니다 .그러면 수열은 (1,1),(1,2)......(3,3)까지 나오게 되는거죠. 이를 이용하면 다음과 같습니다 1. 해당 노드의 자리에 노드를 놓으면, 다음엔 자리수를 줄여서 재귀함수를 호출한다. 예를 들어 n이 3이고 m이 2라고 했..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 백트래킹 알고리즘의 대표적인 문제 중 하나로, 골드 4 문제입니다. 해결책 이 문제를 해결하기 위해 백트래킹의 개념을 알아야합니다. 백트래킹은 기존 끝까지 탐사하는 DFS와 달리 만약 탐색하고 있는 값이, 옳지 않다 생각하면, 바로 전 노드 단계로 돌아가버려 그 다음 단계를 수행합니다. 그럼으로써 효율적이게 탐색을 할 수 있는것입니다. 위 그림을 보시면, 백트래킹에 대해 잘 나타내고 있습니다. 일단 해..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 실버 3이며, 동적할당을 이용해서 푸는 문제입니다 풀이 만약 n이 주어진다면 저 n을 1,2,3의 합으로 나타내는 경우를 모두 구해 주면 됩니다. 처음 생각해보면 꽤 시간이 많이 걸릴것 같지만 푸는 방법만 알면 어렵지 않습니다 동적 계획은 이전에 저장 되어있는 값을 이용해 누적해서 계산해주는 방법입니다. 때문에, 만약 n이 1..3.까지 라고 했을때, dp[1] =1, dp[2]=2, dp[3]= 4입니다. dp[0]은 0으로 둡시다. 0원을 만드는 경우의 수는 없으니까요 그러면 만약 n=4일때..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 실버 1 문제인 오르막 수 입니다. 풀이 1인 경우는 0, 1,2,3,4,5,6,7,8,9로 총 10가지입니다. 이것도 표로 구현해보겠습니다 i)길이가 1인 경우 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 ii)길이가 2인 경우 0 1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1 iii)길이가 3인 경우 0 1 ..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 DP(동적계획) 은 점화식이 중요하다. 그렇기 때문에 해당 문제의 규칙을 찾아서 점화식을 세우고 그걸 기반으로 코드를 짜야한다. 예를 들어보자 최대 3종류 사용가능하며 10을 만들어야한다. 그렇다면 먼저 1원을 사용해서 만들수 있는 가치를 살펴보자 i) 1원으로 조합 가능한 경우 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 ii) 1,2원으로 조합 가능한 경우 1 ..

https://www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net Moo 게임은 골드 5 문제로 분할 정복을 이용해서 푸는 문제입니다 Moo 게임? MOO는 길이가 무한대인 수열입니다. 그렇기 떄문에 수열을 생성하는데 규칙이 있는데 이건 다음과 같습니다 1.S(0)="m o o" 이다 2.S(k)=S(k-1)+"m"+"o * (k+2)"+S(k-1) 이다 풀이 이 문제만 보고 어? 배열로 다 만들어놓고 몇번째인지 세면 되는거 ..

https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 이 문제는 골드 3 문제로, 그리디 알고리즘, 분할정복을 이용해서 푸는 문제입니다. 그리디 알고리즘보다 분할정복 성격이 강하기에 분할정복 카테고리로 넣었습니다. 그리디 알고리즘? 그리디 알고리즘은 탐욕 알고리즘이라고도 불리는데 매 순간 최선의 선택을 하는 알고리즘이라고 생각하면 됩니다. 매 순간 최적을 선택한다는 장점은 있지만, 종합적으로 보면 제일 최선은 아닐 ..

https://www.acmicpc.net/problem/2339 2339번: 석판 자르기 첫 번째 줄에는 석판의 크기 N(1 ≤ N ≤ 20)이 들어온다. 다음 줄부터 N줄에 걸쳐서 석판의 상태가 입력으로 들어온다. 여기서 1은 불순물을 의미하며, 2는 보석 결정체, 0은 불순물과 보석결정체가 www.acmicpc.net 이 문제는 골드 1 문제로 재귀를 이용해서 푸는 문제입니다 풀이 간단한 문제 설명입니다. 석판에 있는 보석들을 하나씩 포함 할 수 있도록 석판을 자르되 불순물을 포함해서 잘라야합니다. 그때에 석판이 나눠지는 방법이 몇가지가 있는지를 알아내는 것이 이번 문제의 과제입니다. 특히, 불순물을 포함해서 자를때, 정확히 두 조각이 나눠지게 잘라야하며, 자를때 보석이 포함되어 있으면 안됩니다. ..