목록PS (176)
득이공간
해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 3-1 * Dynamic Programming - Multistage decision proccess * Dynamic - multistage, time-varying * Programming - 훈련과 병참지원을 위한 military schedule의 optimal program을 구하는 방법을 program이라고 했음. * 동적계획 - divide-and-conquer 알고리즘은 하향식(top-down) 해결법 - dynamic programming은 상향식(bottom-up approach) 해결법 - 작은 문제 -> 큰 문제 순서로 해결한다. - 인덱스를 조정해서 중복된 계산을 피한다. - 작..
해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 2-1 * 분할정복(Divide-and-Conquer)식 설계 전략 - 분할(Divide) : 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다. - 정복(Conquer) : 나눈 작은 문제를 각각 해결한다. - 통합(Combine) : (필요하다면) 해결된 해답을 모은다. - 이러한 문제 해결 방법을 하향식(top-down) 접근방법이라고 한다. * 이분검색(binary search) : 재귀적방식 - 문제 : 크기가 n인 정렬된 배열 S에 x가 있는가? - 입력 : 양수 n, 배열 S[1..n], 키 x - 출력 : x가 S의 어디에 있는지의 위치. 만약 없으면, 0. index locati..
해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 1-1 * 알고리즘 기원 - 페르시아의 수학자, 천문학자, 지리학자 알코와리즘 * 알고리즘 - 문제를 해결할 수 있는 잘 정의된(well defined) 유한(finite) 시간 내에 종료되는 계산적인(computational) 절차(procedure) - 확률적(probabilistic) 알고리즘은 무작위성을 포함한다. * 알고리즘 사용 예시 - 자율주행, 인공지능, 로봇, 메타버스, 암호화폐, NFT * 알고리즘 학습 목표 - Design(설계), Analysis(분석), Computational Complexity(계산복잡도), Application Capability(응용력) * 문제 분야 -..
2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net #include #include #include using namespace std; int A[1001]; int B[1001]; vector ASum; vector BSum; void Init() { int N, M; cin >> N; for (int i = 0; i > A[i]; } cin >> M; for (int i = 0; i < M; ++i..
1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net #include #include using namespace std; bool Prime[4000001]; vector Sequence; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; for (int i = 2; i
20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net #include using namespace std; int Root[500000]; int Find(int Node) { if (Node == Root[Node]) { return Node; } return Root[Node] = Find(Root[Node]); } bool Cycle(int NodeA, int NodeB) { int RootA = Find(NodeA); int RootB = Find(NodeB); if (RootA == RootB) { r..
10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net #include using namespace std; int Num[2000]; bool DP[2000][2000]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; for (int i = 0; i > Num[i]; } for (int i = 0; i < N; ++i) { DP[i][i] = true; if (i < N - 1) { DP[i][i + ..
9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net #include #include using namespace std; int DP[1001][1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string A, B; cin >> A >> B; int N = A.size(); int M = B.size(); for (int i = 1; i 0) { if (DP[i][j] =..
2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net #include #include #include using namespace std; const int MaxSize = 9; bool bFound; int Solution[MaxSize][MaxSize]; int Board[MaxSize][MaxSize]; bool CheckRow[MaxSize][MaxSize + 1]; bool CheckCol[MaxSize][MaxSize + 1]; bool CheckArea[MaxSize][MaxSize + 1]; ..