#문제 9663번: N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 모든 경우의 수를 구하는 백트래킹 기법으로 접근하면 된다. #풀이 #include int n,ans; intcol[15],updia[29],downdia[29]; void NQueen(int x){ for(int i=0;i
#문제 9251번: LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net #접근방법 이전 배열의 값을 이용하는 동적계획법으로 접근하면 된다. #풀이 #include #include #include #include using namespace std; int arr[1005][1005]; int main(){ string a,b; int ans = 0; cin >> a >> b; for(int i=1;i
#문제 1916번: 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net #접근방법 이 문제는 어제 푼 문제랑 똑같은 문제이다. 다익스트라 알고리즘으로 최단비용을 구하면 된다. https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-1753%EB%B2%88-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-CC [백준] 1753번 : 최단경로 [C..
#문제1753번: 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net #접근방법최단경로 알고리즘은 여러가지가 있다.다익스트라벨만 포드플로이드 워셜이 문제는 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이므로 다익스트라 알고리즘을 사용하는 것이 적절하다. 다익스트라 알고리즘은 배열을 사용하는 방법과 우선순위 큐(힙 구조)를 사용하는 방법이 있다. 배열을 사용하는 ..
#문제 16953번: A → B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net #접근방법 A를 B로 바꾸려고 할 때 아래 2가지 연산을 하여 A를 B로 바꾸는데 필요한 연산의 최솟값을 구해야 한다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. 자료구조 queue를 사용하여 경우의 수를 구하면 풀 수 있다. #풀이 #include #include using namespace std; int main(){ int A,B; int ans = -1; queue q; scanf("%d %d",&A,&B); q.push(make_pair(A,1)); while(!q.emp..
#문제 11660번: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net #접근방법 n*n의 배열에 숫자값이 있을 때, (x1,y1), (x2,y2)의 좌표가 들어오면 O(1)번만에 정답을 구해야 시간초과가 걸리지 않는다. 누적합을 시킨 뒤, 적절한 연산을 해주면 쉽게 풀 수 있다. #풀이 #include int arr[1030][1030]; int main(){ int n,m; int..
#문제 9465번: 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net #접근방법 2*n크기의 점수가 매겨져있는 스티커가 있다. 스티커를 때면 상 하 좌 우에있는 스티커들을 못쓰게 될 때, 땔 수 있는 스티커 점수의 최대값을 구하는 문제이다. 다이나믹 기법을 사용하면 풀 수 있다. #풀이 #include #include using namespace std; int arr[2][100005]; int main(){ int T,n,a..
#문제 5639번: 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net #접근방법 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 이진 검색 트리를 전위 순회한 값이 입력값으로 들어올 때, 후위 순회한 결과를 출력해..
#문제 9498번: 시험 성적 https://www.acmicpc.net/problem/9498 9498번: 시험 성적 시험 점수를 입력받아 90 ~ 100점은 A, 80 ~ 89점은 B, 70 ~ 79점은 C, 60 ~ 69점은 D, 나머지 점수는 F를 출력하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 정수 값을 입력 받고 적절한 조건문으로 시험 성적을 출력하면 된다. #풀이 #include int main(){ int x; char ans; scanf("%d",&x); if(x>=90) ans = 'A'; else if(x>=80) ans = 'B'; else if(x>=70) ans = 'C'; else if(x>=60) ans = 'D'; else ans = 'F'; prin..
