알고리즘 풀이16 [백준][C++] 10845번: 큐 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 정수를 저장하는 큐를 구현한 후 입력된 명령을 처리하는 문제이다. 큐 라이브러리를 통해 내장 함수로 풀 수도 있지만 그것 보단 직접 큐를 구현해 풀어보는 것이 의미 있겠다 싶어서 직접 큐를 구현해 풀어보았다. 큐의 기능을 구현하기 위해 배열을 사용하였고 s(start)와 e(end) 두 개의 인덱스를 통해 문제의 출력만 만족하도록 구현해봤다. #include using namesp.. 2024. 3. 29. [백준][C++] 11725번: 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 문제이다. 입력으로 트리 상에서 연결된 두 정점이 주어지는데 이를 통해 노드들을 탐색하면서 연결된 노드가 방문 처리가 안 됐으면 타고 온 노드의 자식 노드이기에 완전 탐색과 깊이탐색 두가지로 풀어보았다. 먼저 완전 탐색부터 보면 1. 주어진 연결 정점 쌍을 통해 그래프를 만든다. 2. 루트 노드가 1이므로 1부터 큐에 삽입 3. 삽입된 노드와 인접한 노드를 탐색하며 방문 되지 않았다면 인접한 노드를 .. 2024. 3. 29. [백준][C++] 1766번: 문제집 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제를 푸는 순서에 대한 조건이 주어지고 문제를 푸는 순서를 출력하는 문제이다. 문제를 푸는 순서가 조건으로 '정해져 있기'때문에 '순서가 정해져 있는 작업'을 차례로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 위상 정렬을 사용하여 풀어보았다. https://blog.naver.com/ndb796/221236874984 25. 위상 정렬(Topology Sor.. 2024. 3. 27. [백준][C++] 9251번: LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 전에 풀었던 가장 긴 증가하는 부분 수열을 구하는 문제와 비슷한 문제로 두 수열 A,B이 주어졌을 때 공통으로 가지는 부분 수열 중 가장 긴 것을 찾는 문제이다. 이 문제 또한 동적 프로그래밍 방법으로 풀어보았다. 먼저 점화식을 찾기 위해 입력 예제를 통해 규칙을 찾아봤다. DP[i][j]를 A[i]까지와 B[j]까지의 최장 공통 부분 수열의 길이로.. 2024. 3. 26. 이전 1 2 3 4 다음
