www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net map check를 통해 (문자, 개수)를 저장하여 투 포인터(두 포인터)를 이용해 문제를 해결했다. 코드 #include #include #include #include #include #include #include #include using namespace std; int n; string input; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); ..

www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 트리를 만들어서 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n; struct node { string food; vector children; }; bool cmp(node* a, node* b) { return ((a->food) food)); } void Insert(node* parent, v..

www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 1번 컴퓨터에서 각 컴퓨터까지 다익스트라로 최소 시간을 구하면서, 그때 come_from[there] = here을 통해 there에 어디서 왔는지 저장을 한다. 이렇게 만들어진 come_from을 통해 선을 구한다. 선은 pair(숫자 작은것, 숫자 큰 것)으로 나타냈으며 중복되지 않게 set에 저장하였다. 이 문제에서 주의해야 될 점은 다익스트라를 통해 스패닝 트리 구성이 가능하다..

www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계 www.acmicpc.net basket에 체크하며 괄호를 칠 수 있는 경우를 모두 확인하고, 수식의 계산은 괄호 부분, 곱하기 부분, 남은 부분 순서로 계산을 하는데, 우선 괄호 부분 계산은 괄호의 범위가 아닌 것들은 result1에 넣고 괄호의 범위인것들은 계산을 하여 result1에 넣었다. 그리고 곱하기 부분 계산은 곱하기가 아닌 부분은 result2에 넣고 곱하기를 만나면 result2의 마지막 수와 곱하기 다음 ..

www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net Long_len함수를 통해 start에서 dest까지 다익스트라 알고리즘을 활용하여 최장거리(최장 시간)를 구한다 그때, come_from[there]을 상황에 따라 추가하거나, 지우고 추가하는 방식으로 경로를 저장한 뒤, Count함수에서 이렇게 만들어진 그래프를 통해 포함된 도로의 수를 구한다. 코드 #include #include #include #include #include ..

www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net KMP알고리즘을 이용하여 문제를 해결했다. pi에 해당 길이까지 접두사도 되고, 접미사도 되는 문자열의 최대 길이를 저장하고, s.size() - pi[s.size() - 1]를 통해 a의 길이(a_size)를 구한뒤, s.substr(0, a_size)를 통해 a를 구하고, 여기서 구한 a로 s=a^n가 가능한지 판단하고(불가능하다면 a는 s이다), 문제를 해결했다. 코드 ..