문제 URL: https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 다음 문제는 비어있는 공집합 S가 주어졌을 때, 연산을 수행하는 프로그램을 작성하는 문제로 연산의 종류는 아래와 같다. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) ..
문제 URL: https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 다음 문제는 숫자 N이 주어졌을 때, 나선에 있는 정삼각형의 변의 길이인 파도반 수열 P(N)을 구하는 문제이다. 이 문제를 처음 봤을 때 파도반 수열의 규칙이 존재한다고 예상할 수 있었는데 그 규칙을 찾기까지 시간이 걸렸다. 다음 그림을 언뜻 보면, P(1) = 1 P(2) = 1 P(3) = 1 P(4) = 2로 4번째 삼각형부터 DP[i] = DP[i-3] + DP[i-1]과 같은 ..
문제 URL: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 다음 문제는 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제로, 다이나믹 프로그래밍을 사용하여 문제를 풀었다. 현재 숫자가 n일 때 n은 1+(n-1) 2+(n-2) ... (n-3)+3 (n-2)+2 (n-1)+1 다음과 같이 만들어 질 수 있다. 이때, 1, 2, 3만을 이용하여 n을 만들어야하기 때문에 1, 2, 3을 이용하여 n-1, n-2, n-3을 만드는 각각의 경우의 수(DP)를 모두 더해주면 1, 2, 3을 이용하여 n을 만드는 방법의 수를 구할 ..
문제 URL: https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 각각의 사람들이 돈을 인출하는데 필요한 시간 합의 최솟값을 출력하는 문제로, 인출 시간이 짧은 사람부터 긴 사람 순으로 정렬을 한 뒤 각 사람들의 인출 소요 시간을 더해주면 인출 소요 시간의 최소값을 구할 수 있다. #include #include #define MAX 1000 using namespace std; int N; int person[MAX]; int time = 0; int main() ..
문제 URL: https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 이 문제는 동적계획법으로 분류된 문제로 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 문제이다. 인접한 페이지끼리 합치는 과정을 반복하면서 가장 최솟값을 찾아야 했다. 이 과정에서 다이나믹 프로그래밍이 사용되었다. #include #include using namespace std; #define INF 1000000000 #define MAX 501 int T..
문제 URL: https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 다음 문제는 크기가 N×N인 종이를 규칙대로 잘랐을 때 만들어지는 하얀색과 파란색 종이의 개수를 출력하는 문제로, 분할정복을 이용하여 푸는 문제였다. 현재 위치의 좌표 색상을 current로 설정하고 현재 좌표가 속해 있는 사분면을 탐색하는데 이때, 다른 색상이 존재한다면 current를 -1로 설정하여 다시 사분면을 탐색한다. 다른 색상이 존재하지 않는다..
문제 URL: https://www.acmicpc.net/problem/1411 1411번: 비슷한 단어 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 각각의 단어는 모두 다르며, 알 www.acmicpc.net 다음 문제는 단어가 여러 개 주어졌을 때, 숌스러운 단어끼리 몇 개의 쌍이 비슷한지 구하는 프로그램으로 어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다. 그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없지만, 자기 자신으로 바꾸는 것은 가능하다. 이 문제는 각 ..
문제 URL: https://www.acmicpc.net/problem/1325 > n >> m; //b를 해킹하면, a도 해킹할 수 있기 때문에 B->A로 연결 리스트로 구현 for (int i = 0; i > a >> b; vec[b].push_back(a);//단방향 그래프 } for (int i = 1; i maxCN) {//해당 노드의 해킹 가능한 컴퓨터 개수가 현재 max 값보다 크다면 answer에 값 추가 answer.clear(); answer.push_back(i); maxCN = hackingCNum; } else if(hackingCNum == maxCN) answer.push_back(i); } for (int n : answer) cout
문제 URL: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 다음 문제는 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램으로 정점 번호는 1번부터 N번까지지 존재하며 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다. 이 문제에서 DFS는 재귀호출을, BFS는 큐를 이용하여 구현하였다. #include #include #include #include ..
문제 URL: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 다음 문제는 주어진 식에 괄호를 적절히 쳐서 식의 값을 최소로 만드는 문제로, 벡터에 숫자들을 저장하고 그 숫자들을 이용해 계산을 하는 방식으로 문제를 풀었다. 이 문제에서 (-) 부호 뒤에 양수가 있다면 괄호로 뒤이어 오는 양수들을 모두 묶어 한 번에 음수로 만들어 주어야 주어진 식이 최소가 될 수 있다. 위의 원리를 이용해 코드를 작성하였는데 과정은 다음과 같다. 문자열 s를 입력받고 문..
