알고리즘 문제풀이/백준
-
[백준/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..
-
[백준/BOJ] 1107번 리모컨 (C++)알고리즘 문제풀이/백준 2020. 12. 7. 18:22
www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 브루트 포스(완전 탐색) 유형의 문제입니다. answer의 초기값을 '숫자 버튼을 누르지 않았을 경우', '+/- 버튼만을 누른 경우' 두가지를 고려하여 설정해주고, 0번 채널부터 1000000번 채널까지 차례대로 N번 채널로 가기 위해 숫자 버튼을 몇번 누르는지 확인합니다. 확인 후 고장난 버튼이 있으면 0을 리턴하고 고장난 버튼이 없으면 개수를 리턴합니다. '현재 채널 - N번 채널'의 절대..
-
[백준/BOJ] 11723번 집합 (C++)알고리즘 문제풀이/백준 2020. 12. 7. 16:22
www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 처음에 set을 이용하여 풀었는데 시간초과가 발생!. 문제를 자세히보니 메모리가 4MB로 제한되어 있었고, 입력값도 최대 3백만으로 꽤 컸기에 단순히 set을 이용해 푸는건 불가능하다는 것을 알게됨 bool형 배열을 하나두고 값이 있는지 없는지만 확인, toggle 연산 시 XOR 연산을 활용, 마지막으로 반복문에서 문자열이랑 숫자를 각각 입력받을 때 cin을 쓰면 뭔가 엉키는 것 같으므로 안전하게 scanf를 사용! #include #inclu..