코딩테스트
-
[문제] https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net [문제 풀이] 백트래킹 문제인데 n과 m과 비슷한 형식이 아닌 처음으로 접한 유형이라서 많이 헤맸었다. 1,2,3 을 더해야 하니 1부터 3까지 3개만을 돌리면서 백트래킹을 한다는건 쉽게 유추가 가능한데 그 뒤의 구현 단계가 힘들었다. 풀이 자체는 어렵지 않았음. 백트래킹 함수의 매개변수에 1,2,3 을 더해서 만일 해당값이 n을 초과한다면 return을 하고(11~12) 만일 해당값이 n과 일치한다면(13~) count..
[C++][백준 12101] 1, 2, 3 더하기 2[문제] https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net [문제 풀이] 백트래킹 문제인데 n과 m과 비슷한 형식이 아닌 처음으로 접한 유형이라서 많이 헤맸었다. 1,2,3 을 더해야 하니 1부터 3까지 3개만을 돌리면서 백트래킹을 한다는건 쉽게 유추가 가능한데 그 뒤의 구현 단계가 힘들었다. 풀이 자체는 어렵지 않았음. 백트래킹 함수의 매개변수에 1,2,3 을 더해서 만일 해당값이 n을 초과한다면 return을 하고(11~12) 만일 해당값이 n과 일치한다면(13~) count..
2022.09.01 -
[문제] https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net [문제 풀이] 백트래킹을 사용하는 도중에 모든 경우에 500이하가 되는지 아닌지를 확인해주자. 벡터에 n만큼 숫자가 찼을 경우에 (16~) 벡터 크기만큼 돌려서 현재 벡터에 저장되어있는 숫자를 더하고 k만큼 뺐을때 500이 넘는지 아닌지 확인해주자. (20~27) 만일 숫자가 계속해서 500을 넘는다면 answer의 카운트를 올려주자. (28~30) n만큼 돌렸을때 위치를 방문..
[C++][백준 18429] 근손실[문제] https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net [문제 풀이] 백트래킹을 사용하는 도중에 모든 경우에 500이하가 되는지 아닌지를 확인해주자. 벡터에 n만큼 숫자가 찼을 경우에 (16~) 벡터 크기만큼 돌려서 현재 벡터에 저장되어있는 숫자를 더하고 k만큼 뺐을때 500이 넘는지 아닌지 확인해주자. (20~27) 만일 숫자가 계속해서 500을 넘는다면 answer의 카운트를 올려주자. (28~30) n만큼 돌렸을때 위치를 방문..
2022.09.01 -
[문제] https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net [문제풀이] 2차원 배열을 만들어서 풀 경우에 점화식 DP[i][j] = DP[i-1][j-1] + DP[i-1][j] 로 풀 수가 있다. j의 값이 0이거나 i와 같아질 경우에는 1이 되게 만들자.(16~19) [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ..
[C++][백준 16395] 파스칼의 삼각형[문제] https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net [문제풀이] 2차원 배열을 만들어서 풀 경우에 점화식 DP[i][j] = DP[i-1][j-1] + DP[i-1][j] 로 풀 수가 있다. j의 값이 0이거나 i와 같아질 경우에는 1이 되게 만들자.(16~19) [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ..
2022.09.01 -
[문제] https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net [문제 풀이] 계속해서 반복하는 부분은 "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어." 라고 답변하였지. 가 반복되는데 라고 답변하였지는 가장 밑의쪽에..
[C++][백준 17478] 재귀함수가 뭔가요?[문제] https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net [문제 풀이] 계속해서 반복하는 부분은 "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어." 라고 답변하였지. 가 반복되는데 라고 답변하였지는 가장 밑의쪽에..
2022.08.31 -
[문제] https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net [문제 풀이] nCm 의 경우에는 2차원 배열 DP를 이용해서 풀어보면 쉽게 답이 나오는 것을 알 수가 있다. 그러므로 우리는 범위를 넘어서는 문제에 대해서 고민을 해보면 된다. 어떠한 정수형 자료형을 주더라도 범위를 넘어서기 때문에 이 같은 문제를 풀때는 string 을 이용해서 풀도록 하자. string으로 두개의 변수를 받은 뒤에 가장 큰 변수크기에 양쪽을 맞춰주고(11~15) string 크기 값에 맞춰서 뒤에서 부터 계속해서 더해주도록 하자.(24~36) 만일 해당 값의 가장 앞이 10의 범위를..
[C++][백준 2407] 조합[문제] https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net [문제 풀이] nCm 의 경우에는 2차원 배열 DP를 이용해서 풀어보면 쉽게 답이 나오는 것을 알 수가 있다. 그러므로 우리는 범위를 넘어서는 문제에 대해서 고민을 해보면 된다. 어떠한 정수형 자료형을 주더라도 범위를 넘어서기 때문에 이 같은 문제를 풀때는 string 을 이용해서 풀도록 하자. string으로 두개의 변수를 받은 뒤에 가장 큰 변수크기에 양쪽을 맞춰주고(11~15) string 크기 값에 맞춰서 뒤에서 부터 계속해서 더해주도록 하자.(24~36) 만일 해당 값의 가장 앞이 10의 범위를..
2022.08.31 -
[문제] https://www.acmicpc.net/problem/11051 [문제풀이] DP를 풀듯이 2차원 배열을 만들어서 풀자. 시간 복잡도는 N^2이기 때문에 1000x1000 배열에서는 1초 안으로 풀 수가 있다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #include #define endl "\n" using namespace std; long long result[1001][1001]; void combination(int n,int k){ for(int i = 0;in>>k; combination(n,k); cout
[C++][백준 11051] 이항 계수 2[문제] https://www.acmicpc.net/problem/11051 [문제풀이] DP를 풀듯이 2차원 배열을 만들어서 풀자. 시간 복잡도는 N^2이기 때문에 1000x1000 배열에서는 1초 안으로 풀 수가 있다. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #include #define endl "\n" using namespace std; long long result[1001][1001]; void combination(int n,int k){ for(int i = 0;in>>k; combination(n,k); cout
2022.08.31