작심 24/7

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 일단 Core 중에서도 가장자리에 있는 것들은 전선을 연결하지 않기 때문에 고려해줄 이유가 없으므로 코어의 목록에서 제외하고 시작한다. 최대한 많은 Core에 전원을 연결해야 하기 때문에 코어의 개수를 M개라 칭하면, M개 중 M개를 뽑는 조합부터 시작하여 M - 1, M - 2, ... , 0개를 뽑는 경우까지 차근차근 생각해주어야 한다. M개 중 R개를 뽑는 조합을 구하면, 즉 R개의 Core를 사용할 때, 전선 길이의 합이 최소가 되는 경우를 구해야 한다. DFS를 사용하여 상, 하, 좌, 우 방향으로 전선을 만들 수 있는지 판단한다. → 만들 수 있는 경우..

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 시간 초과와의 싸움이었다. N번만큼 for문을 돌면서 visited 배열을 초기화해줬는데 이게 시간 초과의 주된 원인이라고 한다. 그래서 초기화는 테스트 케이스마다 한 번씩만 해주고 재귀에서 빠져나올 때마다 visited 배열의 값을 false로 바꿔주는 방식으로 대체하였다. 1. 각 원소는 무조건 어떤 원소를 가리킨다. 마지막엔 무조건 사이클로 끝나게 된다. 2. 한 번 방문한 곳은 visited, 예전에 검사가 끝난 곳은 done으로 표시할 때, done으로 표시..

11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 � www.acmicpc.net 근우 입장에서 볼 때 근우 차례 : 점수가 더 높은 카드를 갖고 감으로써 점수를 최대로 하는 플레이를 해야 함 명우 차례 : 명우 입장에선 자신이 이기기 위해 점수가 더 높은 카드를 갖고 갈 것이므로 근우는 근우의 점수를 최소로 하는 플레이를 해야 함 DP[i][j] = i번째부터 j번째 카드가 있을 때 근우가 얻을 수 있는 최대 점수 근우 차례일 땐 점수를 최대로 해야 하므로 max(왼쪽 카드 + 왼쪽 카드를 뽑고 플레이한 결과, 오른쪽 카드 + 오른쪽 카드를 ..

1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 수학적으로 풀어도 되지만 백트래킹으로 풀어보았다. 계산에 사용되는 M개의 알파벳을 모아놓고 9부터 M개의 숫자를 순열로 대입하였다. ex) ADC -> 3개의 숫자 9, 8, 7을 순열로 배치시키면 알파벳 ADC는 987, 978, 897, 879, 798, 789 이렇게 숫자가 대입될 수 있다. map을 이용해서 각 알파벳에 숫자를 대입해주고 배치가 완료되면 단어의 합을 계산해주고 최댓값을 갱신한다. 이때 stoi를 이용하여 계산을 했었는데 시간 초과 나..

16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 �� www.acmicpc.net 문자열 S를 처음부터 탐색하면서 현재 idx부터 목록 A에 있는 단어가 포함돼 있으면 재귀 호출로 (idx+단어 길이)번째부터 목록 A에 있는 단어가 있는지 탐색한다. 이때 dp[idx]가 true면 이전에 이 idx부터 시작되는 단어를 탐색해봤다는 뜻이므로 굳이 또 계산할 필요 없이 return으로 돌아온다. dp[idx]가 false면 처음 탐색한다는 뜻이므로 true로 바꿔주고 탐색하러 간다. idx와 문자열 S의 길이가 같다면 성..

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence) 문제이다. LCS(Longest Common Substring)과 같이 문자열 A, B에서 A[i]와 B[j]가 같을 때는 DP[i][j] = DP[i-1][j-1] + 1 이 되지만 A[i]와 B[j]가 다를 때는 DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + 1 이 된다. 그러면 최종적으로 DP[문자열A 끝][문자열B 끝]이 L..

14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net O(NlogN) LIS 알고리즘으로 풀어야 하는 문제이다. arr 배열엔 입력 값을 저장한다. tmp 배열의 인덱스는 수열의 길이를 나타내고 각 값은 현재 길이를 가진 수열의 마지막 원소 중 가장 작은 값의 위치를 저장한다. dp 배열엔 각 인덱스가 연결하고 있는 인덱스를 저장한다. 변수 len엔 지금까지 가장 긴 수열의 길이를 저장한다. 계산이 모두 끝나면 tmp[len]이 LIS의 마지막 원소의 위치를 가리키고 있으므로 dp[tm..

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 기본적으로 DP로 길이만 저장하는 LIS를 구하는 방법에서 조금 변화를 주어 arr 배열엔 입력 값을 저장하고 len 배열엔 길이를 저장하고 dp 배열엔 현재 위치까지에서 가장 긴 수열을 가진 위치를 저장하였다. 그러고 출력할 땐 수열의 길이가 가장 길었던 위치부터 재귀 호출하여 그 수열의 처음까지 들어간 다음 출력하면서 빠져나왔다. #include using namespace st..