코딩테스트
-
[문제] https://www.acmicpc.net/problem/2902 2902번: KMP는 왜 KMP일까? 입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드 www.acmicpc.net [문제 풀이] String을 이용해서 '-'이 나온 뒤에 char를 벡터에 계속해서 추가해주자. [코드] 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 #include #include #include #define endl "\n" using namespace std; void so..
[C++][백준 2902] KMP는 왜 KMP일까?[문제] https://www.acmicpc.net/problem/2902 2902번: KMP는 왜 KMP일까? 입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드 www.acmicpc.net [문제 풀이] String을 이용해서 '-'이 나온 뒤에 char를 벡터에 계속해서 추가해주자. [코드] 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 #include #include #include #define endl "\n" using namespace std; void so..
2022.09.06 -
[문제] https://www.acmicpc.net/problem/2744 2744번: 대소문자 바꾸기 영어 소문자와 대문자로 이루어진 단어를 입력받은 뒤, 대문자는 소문자로, 소문자는 대문자로 바꾸어 출력하는 프로그램을 작성하시오. www.acmicpc.net [문제 풀이] 아스키코드값으로 알파벳 소문자와 대문자는 32만큼의 차이가 나니 'a' 보다 작으면 32를 더해주고 'a' 보다 같거나 크면 32를 빼주자. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #define endl "\n" using namespace std; void solve(string s){ for(int i = 0;i
[C++][백준 2744] 대소문자 바꾸기[문제] https://www.acmicpc.net/problem/2744 2744번: 대소문자 바꾸기 영어 소문자와 대문자로 이루어진 단어를 입력받은 뒤, 대문자는 소문자로, 소문자는 대문자로 바꾸어 출력하는 프로그램을 작성하시오. www.acmicpc.net [문제 풀이] 아스키코드값으로 알파벳 소문자와 대문자는 32만큼의 차이가 나니 'a' 보다 작으면 32를 더해주고 'a' 보다 같거나 크면 32를 빼주자. [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #define endl "\n" using namespace std; void solve(string s){ for(int i = 0;i
2022.09.05 -
[문제] https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net [문제 풀이] 연산자 끼워넣기 1과 비슷하나 입력에서 조건이 추가되었다. 입력 연산자의 합이 N-1 보다 크거나 같고 4N보다 작거나 같다는 조건이 추가되었는데 만일 숫자가 10개고 연산자가 40개가 될 경우에 연산자 끼워넣기 1에서 풀었던 것처럼 벡터에 모든 연산자를 넣고 하나하나씩 연산자를 푸는 방식으로 한다면 40^10 이 되어서 시간을 아..
[C++][백준 15658] 연산자 끼워넣기 (2)[문제] https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net [문제 풀이] 연산자 끼워넣기 1과 비슷하나 입력에서 조건이 추가되었다. 입력 연산자의 합이 N-1 보다 크거나 같고 4N보다 작거나 같다는 조건이 추가되었는데 만일 숫자가 10개고 연산자가 40개가 될 경우에 연산자 끼워넣기 1에서 풀었던 것처럼 벡터에 모든 연산자를 넣고 하나하나씩 연산자를 푸는 방식으로 한다면 40^10 이 되어서 시간을 아..
2022.09.03 -
[문제] https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [문제풀이] 유명한 백트래킹 응용문제 n 퀸인데 기존에 백트래킹을 많이 풀어봤다면 충분히 풀 수 있을만한 문제다. 체스판에서 N만큼 퀸이 존재하는 경우를 요구하는 문제인데 체스판에 퀸이 N만큼 존재할려면 모든 줄에 퀸이 1개씩은 존재해야 한다. 다만, 이미 방문했던 위치를 true나 false로 둘 경우 다시 원상복귀할때 원하지 않는 부분까지 반환을 해주는 경우가 생기기에 2중배열 visit을 int로 ..
[C++][백준 9663] N-Queen[문제] https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [문제풀이] 유명한 백트래킹 응용문제 n 퀸인데 기존에 백트래킹을 많이 풀어봤다면 충분히 풀 수 있을만한 문제다. 체스판에서 N만큼 퀸이 존재하는 경우를 요구하는 문제인데 체스판에 퀸이 N만큼 존재할려면 모든 줄에 퀸이 1개씩은 존재해야 한다. 다만, 이미 방문했던 위치를 true나 false로 둘 경우 다시 원상복귀할때 원하지 않는 부분까지 반환을 해주는 경우가 생기기에 2중배열 visit을 int로 ..
2022.09.03 -
[문제] 10974번: 모든 순열 (acmicpc.net) 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net [문제 풀이] 백트래킹을 이용해서 모든 순서를 파악하자. 숫자 1부터 n까지를 넣어야 하고 반복되는 숫자는 없어야 한다.(19~22) 만약에 1번이라도 넣었으면 해당 숫자를 방문했다고 체크해주자(23) answer에 넣은 뒤 재귀를 이용해 다시 반복하자(24~25) 해당 재귀가 끝나면 마지막에 넣은 숫자를 뺀뒤에 방문표시를 다시 false로 바꾸자.(26~27) [코드] 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 2..
[C++][백준 10974]모든 순열[문제] 10974번: 모든 순열 (acmicpc.net) 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net [문제 풀이] 백트래킹을 이용해서 모든 순서를 파악하자. 숫자 1부터 n까지를 넣어야 하고 반복되는 숫자는 없어야 한다.(19~22) 만약에 1번이라도 넣었으면 해당 숫자를 방문했다고 체크해주자(23) answer에 넣은 뒤 재귀를 이용해 다시 반복하자(24~25) 해당 재귀가 끝나면 마지막에 넣은 숫자를 뺀뒤에 방문표시를 다시 false로 바꾸자.(26~27) [코드] 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 2..
2022.09.03 -
[문제] https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net [문제풀이] 연산자를 백트래킹을 통해 모든 경우를 파악하자. 사칙연산을 int 값으로 받아온뒤 해당 값만큼 벡터에 저장해주자.(59~76) visit을 통해 방문을 했는지 아닌지 파악한뒤 방문하지 않았다면 해당 사칙연산을 저장해주자.(42~51) 저장해둔 사칙연산의 연산을 이용해서 마지막 값을 파악한다.(19~32) max값과 min..
[C++][백준 14888] 연산자 끼워넣기[문제] https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net [문제풀이] 연산자를 백트래킹을 통해 모든 경우를 파악하자. 사칙연산을 int 값으로 받아온뒤 해당 값만큼 벡터에 저장해주자.(59~76) visit을 통해 방문을 했는지 아닌지 파악한뒤 방문하지 않았다면 해당 사칙연산을 저장해주자.(42~51) 저장해둔 사칙연산의 연산을 이용해서 마지막 값을 파악한다.(19~32) max값과 min..
2022.09.02