알고리즘 문제풀이
-
[백준/BOJ] 2469번 사다리 타기 (C++)알고리즘 문제풀이/백준 2020. 12. 12. 16:12
www.acmicpc.net/problem/2469 2469번: 사다리 타기 첫 줄에는 참가한 사람의 수 k가 나온다(3≤k≤26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3≤n≤1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정된 참 www.acmicpc.net 시작 알파벳에서 '?' 전까지, 결과 알파벳에서 '?' 전까지 알파벳의 순서를 계속 수정합니다. 위의 예시에선 최종적으로 '?' 전의 시작 알파벳과 '?' 전의 결과 알파벳은 다음과 같이 만들어집니다. 시작 알파벳 : [C, A, D, B, E, G, F, H, I, J] 결과 알파벳 : [C, A, B, D, G, E, F, H, J, I] 두 결과를 비교하여 문자가 같다면 '*', 순서가 ..
-
[백준/BOJ] 1049번 기타줄 (C++)알고리즘 문제풀이/백준 2020. 12. 12. 01:41
www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 간단한 수학(?) + 구현 문제입니다. 패키지와 단품 가격의 최소값을 구해 따로 저장하고 이를 이용하여 다음과 같이 가격을 구합니다. 1. 단품만 구매하는 경우 2. 단품 + 패키지를 구매하는 경우 3. 패키지만 구매하는 경우 세 가격 중 최소값을 구하면 됩니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); ..
-
[백준/BOJ] 3085번 사탕 게임 (C++)알고리즘 문제풀이/백준 2020. 12. 11. 17:24
www.acmicpc.net/problem/3085 3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net 입력값이 최대 50이므로 완전 탐색으로 어렵지 않게 해결할 수 있는 문제입니다. 가로와 세로 각각 인접한 사탕이 다른 경우 자리를 교체해가면서, 전체 영역의 가로 세로를 탐색하면 됩니다. 다만 eat() 함수 부분에서 한 줄이 모두 같은 경우 최대값 갱신 처리를 따로 처리해줘야 하는 것을 조심해야합니다. #include #include using namespace std; vector map(53); int n, answer; void eat() { // 가로 사탕 먹기 for(int i = 0; i < n; i++) { int sum =..
-
[백준/BOJ] 10994번 별 찍기 - 19 (C++)알고리즘 문제풀이/백준 2020. 12. 11. 13:42
www.acmicpc.net/problem/10994 10994번: 별 찍기 - 19 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 재귀를 이용하는 별 찍기 문제입니다. 각각의 패턴마다 양 옆, 위 아래의 *의 개수가 1, 5, 9, 13 ... 으로 증가하는 규칙을 가집니다. 이를 통해 4n - 3 이라는 점화식을 얻어낼 수 있습니다. 또한 각 패턴마다 '*'이 시작되는 지점은 2씩 차이가 납니다. 2차원 배열을 선언 후 ' '로 초기화하고, 위의 규칙을 이용해 재귀적으로 '*'을 채워갈 수 있습니다. #include using namespace std; char map[401][401]; void R(int x, int y, int n) { if(n == 1) { m..
-
[백준/BOJ] 2448번 별 찍기 - 11 (C++)알고리즘 문제풀이/백준 2020. 12. 11. 13:39
www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 재귀를 이용하는 별 찍기 문제입니다. 입력값으로 24가 들어왔을 때의 패턴을 보면 다음과 같은 규칙을 가지는 프랙탈 구조라는 것을 확인할 수 있습니다. n == 24의 삼각형 : n == 12의 삼각형 3개로 구성 n == 12의 삼각형 : n == 6의 삼각형 3개로 구성 n == 6의 삼각형 : n == 3의 삼각형 3개로 구성 n == 3의 삼각형 : 더 이상 쪼개질 수 없는 가장 작은 삼각형 따라서 삼각형을 그릴 시작 좌표와 n의 크기를 매개변수로 재귀함수..
-
[백준/BOJ] 14501번 퇴사 (C++)알고리즘 문제풀이/백준 2020. 12. 10. 17:44
www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 삼성 역량 테스트 기출 문제 : DP or DFS 입력값의 범위가 크다면 DP를 이용해야겠지만, 최대 15이기 때문에 DFS를 이용한 완전 탐색으로 모든 경우의 수를 구하고 그 중에 최대인 경우를 구하는 것도 가능합니다. 둘다 핵심은 상담 날짜를 예약하는 경우와 예약하지 않는 경우 두 가지 케이스를 고려하는 것입니다. #include #include using namespace std; int n, answer; vector v; void DFS(int day, int sum) { if(day == n + 1) { answer = max(answe..
-
[백준/BOJ] 5430번 AC (C++)알고리즘 문제풀이/백준 2020. 12. 9. 23:51
www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 많은 시행착오를 겪은 문제, 자료구조의 기본개념과 시간복잡도 고려의 중요성을 깨닫게 해준 아주 좋은 문제였습니다. 숫자가 두자리 이상일 수 있다는 점과 reverse 함수를 사용할 시 시간복잡도가 100,000 * 100,000 = 10,000,000,000 로 1초가 넘어가기 때문에 시간오류가 발생할 수 있다는 점을 주의합시다. 이러한 시간 초과를 해결하기 위해서 먼저 덱을 선언하여 입력받은 문자열에서 숫자만 따로 파싱하여 저장했습니다. 그리고 정방향과 역방향을 나..
-
[백준/BOJ] 14888번 연산자 끼워넣기 (C++)알고리즘 문제풀이/백준 2020. 12. 8. 17:27
www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 삼성 역량 테스트 기출 문제 : DFS(순열, 조합) DFS 또는 next_permutation()을 이용해 연산자의 순열을 구해야합니다. DFS를 사용할 시 조건문 쪽에서 else if를 쓰지 않도록 주의합니다. #include using namespace std; int a[12], op[4]; int n, ansMax = -2147000000, ans..