거창한 시작

www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 알고리즘 종류 자료구조 스택 사고 과정 스택을 이용해서 풀 수 있습니다. 문제에서 제시된 예시를 손으로 풀어보면 나중에 나온 연산자가 알파벳 뒤에 먼저 붙는 것을 알 수 있습니다. 그리고 문자는 그대로 출력되는 것을 알 수 있습니다. 그래서 문자는 그대로 출력하고 연산자만 스택에 넣어서 해결하면 될 것 같습니다. 조건이 몇 가지 있습니다. 1. 괄호로 인해서 우선순위가 바뀔 수 있습니다. 그래서 괄호도..

www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 알고리즘 종류 구현 사고 과정 next_permutation으로 해결하면 너무 쉽게 해결할 수 있다는 것을 알았습니다. next_permutation을 이용하면 순열을 쉽게 구할 수 있습니다. 이 문제의 경우 순열에서 2번째로 생성된 것을 출력하면 됩니다. 1번째는 자기 자신입니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2..

www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 알고리즘 종류 구현 문자열 사고 과정 비트마스크를 사용하지 않고 구현하면 제출이 되었지만, 시간이 오래 걸렸습니다. 비트마스크를 사용하면 어떤 알파벳이 있는지 쉽게 알 수 있습니다. 1. 처음에는 모든 알파벳을 기억한다고 했으니 or 연산으로 모든 알파벳을 기억합니다. 2. 단어를 입력받으면, dict 배열에서 단어의 문자를 or 연산으로 기억합니다. 3. 쿼리르 입력 받으면, And와 or 연산을 이용해서..

www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 알고리즘 종류 완전탐색 사고 과정 읽을 수 있는 최대 단어의 개수를 찾아야 합니다. 시작 글자와 끝 글자를 제외하고 중간에 남는 글자들에서 중복을 제외해야 한다고 생각했습니다. 그리고 a~z중에서 k-5개를 선택해서 남은 글자들을 커버할 수 있는지 확인하면 될 것 같습니다. k가 5미만이면 무조건 0개의 단어를 읽을 수 있습니다. 1. 기본으로 선택된 글자들은 미리 선택되게 합니다. 그리고 DFS를 이용..

www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 알고리즘 종류 완전탐색 사고 과정 DFS로 풀려고하니 +과 같은 교차하는 것을 확인할 수 없었습니다. BFS로 하려고 하니 재방문 확인을 할 수 없었습니다. 그래서 25개의 공간에서 7개를 선택하여 확인하는 방법을 사용하기로 했습니다. 1. DFS를 이용해서 조합으로 7개의 위치를 선택합니다. 2. 7개의 위치를 골랐다면, 이다솜파가 4명이상인지 확인합니다. 3. BFS로 7개의 공간이 서로 붙어있는지 확인합니다...

www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 알고리즘 종류 DP 사고 과정 최댓값이 만들어지는 과정을 보고 DP같다라는 생각을 했습니다. 제가 DP를 해결하는 방법은 과정을 깔끔하게 나열하고 규칙을 찾는 것입니다. 최솟값을 나열하기로 했습니다. n을 20까지 나열해 보니 규칙이 보이기 시작했습니다. 성냥개비 2배부터 8개까지를 뒤에 붙이는 식으로 숫자가 생성되었습니다. 예를 들어, n=10이면 다음의 경우가 나옵니다. 8,2 / 7,3 / 6.4 / 5,5 / ..

www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 알고리즘 종류 트리 LCA 사고 과정 1. 인접행렬로 노드 쌍을 받아습니다. 그리고 depth과 parents 배열로 트리를 만들어 줍니다. 2. 공통 부모를 찾을 두 노드를 받습니다. 두 노드의 깊이가 같아질 때까지 부모를 타고 올라갑니다. 두 노드가 같은 깊이에 도달하면, 동시에 타고 올라가면서 공통 부모가 될때까지 올라갑니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 알고리즘 종류 다익스트라 DP 사고 과정 이 문제는 노드에 비용과 간선의 거리가 존재합니다. 이 2가지를 고려해야 합니다. 이 문제를 간단하게 생각해 보겠습니다. 노드가 그물형으로 연결된 것이 아닌 선형으로 연결되어 있다고 가정하겠습니다. 상태가 아래와 같을 때, 1번노드에서 2번 노드로 가는 비용은 20 * 거리가 됩니다. 이제 2번 노드에서 3번으로 가겠습니다. 비용 30과 비교했을..

www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 알고리즘 종류 다익스트라 DP 사고 과정 1번 노드에서 N번 노드로 가는 최소비용을 구하는 문제입니다. 이때, 도로를 포장하거나 하지 않을 수 있습니다. 접근하기 전에 가장 일반적인 다익스트라 문제를 생각해 보겠습니다. 이 문제를 기본적인 다익스트라 문제로 바꿔본다면, 모든 도로를 포장하지 않고 1번 노드에서 N번 노드로 이동하는 최소 비용을 구하는 문제가 될 것입니다. 그러..

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 알고리즘 종류 부분 집합 자료 구조 사고 과정 부분 집합을 할 parents 배열을 만듭니다. 그리고 몇 명이 연결되어 있는지 기록할 state라는 배열을 만듭니다. 이후 union_find으로 해결하면 됩니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..