본문 바로가기

분류 전체보기

(62)
[백준/C++] 알고리즘 14501번 - 퇴사1 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘14501번 - 퇴사 를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [문제 접근] 시간제한은 2초이고 N은 15이하이기 때문에 완전탐색이 가능합니다. 상담기간을 텀으로 상담을 하기 때문에 DFS로 접근했습니다. 이후에 다이나믹프로그래밍으로도 풀 수 있다고하여 시도했습니다. 그렇지만 만약 시험장에서 이 문제를 마주쳤다면 다이나믹프로그래밍보다 DFS로 먼저 떠오를 거 같네요. [풀이 전략] DFS 풀이 1. dfs 함수를 생성합니다. - 만약 cnt가 n이면 지금까지의 상담 금액과 최대 상담 금액을 비교..
[백준/C++] 알고리즘 10844번 - 쉬운 계단 수 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 10844번 - 쉬운 계단 수 를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [문제 접근] 이전 상황을 이용하여 현재 상황을 이루는 문제이기 때문에 다이나믹 프로그래밍으로 접근했습니다. 패턴을 찾기 위해 처음에는 곧이곧대로 n = 1,2,3일 때를 모두 종이에 써가며 확인했습니다. 자연스럽게 상황마다 0~9까지의 숫자의 개수를 세기 시작했고, 이전 상황의 숫자들의 개수와 현재 상황의 숫자들의 개수의 연관성이 보였으나 패턴을 못 찾았습니다. 그래서 0~9까지의 개수를 n = 1..
[백준/C++] 알고리즘 9146번 - 파도반 수열 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 9146번 - 파도반 수열을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net [문제 접근] 반복성이 보이고, 패턴을 발견할 수 있다는 생각을 가지고 다이나믹 프로그래밍으로 접근했습니다. 이미 문제에서 점화식의 정의를 주어졌기 때문에 점화식만 구하면 됩니다. p[i] = p[i-1] + p[i-5]임을 찾아낼 수 있습니다. [풀이 전략] 1. p[1] ~ p[5]까지 초기..
[백준/C++] 알고리즘 18809번 - Gaaaaaaaaaarden 안녕하세요! 테크지니어22입니다. 오늘은 백준 18809번 - Gaaaaaaaaaarden 를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net [문제 접근] 초록색 배양액과 빨간색 배양액이 배양액을 뿌릴 수 있는 땅에 임의로 위치시키고 가장 많이 꽃이 피는 개수를 찾는 문제이기 때문에 모든 경우를 고려해야 합니다. 시간제한은 2초이고, n은 50이하로 넉넉하므로 ..
[백준/C++] 알고리즘 11053번 - 가장 긴 증가하는 부분 수열 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 11053번 - 가장 긴 증가하는 부분 수열 을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [문제 접근] 바로 이전 글에서 풀었던 가장 큰 증가하는 부분 수열과 문제 접근 방식이 동일해서 생략합니다. 아래 글을 참고해주세요. https://techgineer22.tistory.com/..
[백준/C++] 알고리즘 11055번 - 가장 큰 증가하는 부분 수열 안녕하세요! 테크지니어22입니다.오늘은 백준 알고리즘 11055번 - 가장 큰 증가하는 부분 수열을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/11055 [문제 접근]제한시간은 1초이고 n은 1000이하입니다. 완전탐색은 합까지 포함해서 대략 O(N^3)으로 10억의 연산이 필요하기 때문에 불가능합니다.연속하는 것이 아니기 때문에 투 포인터를 사용하는 것도 어렵습니다. 다시 문제를 살펴보면 수열의 크기가 n일 때와 n-1일 때와 비교해보면 1. 같다.2. n이 a[n-1]만큼 더 크다.임을 알 수 있습니다. 즉 n 상황과 n-1상황이 서로 관계가 있음을 파악할 수 있고, 이를 통해 다이나믹 프로그래밍 풀이를 생각해볼 수 있습니다. 그럼 배열을 정의하고 점화식을 세우..
[백준/C++] 알고리즘 1912번 - 연속합 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 1912번 - 연속합을 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net [문제 접근] 시간 제한은 1초이고 n의 범위가 10만이기 때문에 완전탐색은 불가능합니다. 연속 합을 구하는 거여서 투 포인터로도 O(N)으로 줄이기 어렵다고 판단했습니다. 그럼 마지막으로 떠오르는 건 다이나믹 프로그래밍입니다. 그런데 아직 다이나믹 프로그래밍에 익숙하지 않아서 정의를 내리기가 무척이나 어려..
[백준/C++] 알고리즘 11967번 - 불 켜기 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 11967번 - 불 켜기를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net [문제 접근] N이 작기 때문에 완전탐색이 가능합니다. 인접하고 불이 켜진 방으로 이동할 수 있다는 조건 하에 다차원 배열을 순회하기 때문에 BFS를 생각했습니다. [풀이 전략] 1. 현재 방에서 원격으로 스위치를 불을 킵니다. 2.현재 방..
[백준/C++] 알고리즘 2193번 - 이친수 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 2193번 - 이친수를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net [문제 접근] 0과 1로만 다음 자리수를 결정하기 때문에 패턴을 발견할 수 있음을 예상할 수 있습니다. 즉 다이나믹 프로그래밍이라는 문제를 파악하고, 점화식을 정의했고, 다음과 같이 발견했습니다. dp[i][j] : 끝자리가 j인 i자리 이친수의 개수. dp[i][0] = dp[i-..
[백준/C++] 알고리즘 11727번 - 2×n 타일링 2 안녕하세요! 테크지니어22입니다. 오늘은 백준 알고리즘 11727번 - 2×n 타일링 2 를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 22×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.www.acmicpc.net [문제 접근] 패턴을 찾아내는 문제라고 생각하여 다이나믹 프로그래밍으로 접근하였습니다. d[n]은 2xn타일링을 채우는 방법의 수라고 정의했습니다. d[n+2] = d[n+1] + 2*d[n]이라는 점화식을 발견했습니다. 발견하는 과정은 그림과 같습니다. [풀이 전략] 1. dp배열 초기값을 설정합니다. 2. fo..