삼성 SW Expert Academy에 괜찮은 문제들이 많이 있는 것 같아 요즘 몇 문제 풀어보았습니다. 문제는 삼성 SW Expert Academy 가입 후 확인 가능하여 따로 올릴 수 없습니다. 문제 내용은 간단하다. 보급로가 주어져있을 때 어떤 경로로 가장 빨리 갈 수 있는가입니다. 댓글을 보니 dfs로 풀거나 다익스트라로 푸신 분들도 계셨지만, 저는 bfs와 dp를 섞어서 풀었습니다. 주의할 점은 해당 지점을 들렀다하더라도, 다른 경로에서 더 빠른 케이스가 있을 수 있기 때문에 이를 체크해야 합니다. 코드는 다음과 같습니다. #include #include #include #include #include #include using namespace std; int n; int board[101][..
www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net kmp 알고리즘 중 pi 배열을 이용하는 문제입니다. pi 배열은 접두사, 접미사가 같은 최대 길이를 저장하는 역할을 합니다. pi[len]는 문자열의 0~len까지의 부분 문자열 중 접두사와 접미사 같은 것의 최대 길이를 의미합니다. 예를 들어, ababab의 경우, pi[0] = 0, pi[1] = 0, pi[2] = 1 (a), ... , pi[5] = 4 (abab) ..
www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 이전에 푼 우수 마을 문제와 유사한 문제이다. i 번 노드가 독립집합의 원소가 아니면, i번 노드의 자식 노드는 독립집합의 원소가 되든 안 되든 상관 없고, i번 노드가 독립집합의 원소라면, 자식 노드는 독립집합의 원소가 될 수 없다. i번 노드가 독립집합의 원소이고 루트로 하는 서브트리에서의 가능한 최댓값을 dp[i][1], 독립집합이 아닐 때를 dp[i][0]로 잡으면 dp[..
www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 트리 구조로 이루어진 마을에서 우수마을을 주민의 최대값으로 고르는 문제입니다. 조건은 다음과 같습니다. 1. 우수마을의 주민의 수 합을 최대로 한다. 2. 우수마을끼리는 인접이 불가하다. 3. 우수마을이 아닌 마을은 적어도 하나의 우수마을과 인접하다. 처음에 풀 때는 3번의 적어도라는 조건을 안 보고 풀어 그냥 depth별로 홀,짝 구분해서 합이 최대치인 것을 뽑으면 될 줄 알았지만, 적어도 하나의 우..
www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 전형적인 위상정렬 문제였습니다. 위상정렬은 일의 순서를 어기지 않으면서 노드를 정렬하는 알고리즘입니다. 설명한 내용은 ghqls0210.tistory.com/96 에 있습니다. 상위 노드가 완료된 노드면 하위 노드의 결과는 상위 노드 결과 + 하위 노드의 가중치 중 최댓값임을 쉽게 이해할 수 있습니다. 코드는 다음과 같습니다. #include #include #include #include #include..